Homework 1
Important: Write Name and Unity ID on every submission file. Name the submission file correctly as asked for.
- (0 points)
Get a D-Wave account, download and install D-Wave Ocean as follows:
- (15 points, 5+15) Similar to the example with the 3-qubit
solution of the 3-qubit OR,
create a NOR relation (the opposite of an OR relation):
- Create a solution in the
Quantum Apprentice spreadsheet with the correct
weights and strengths in the 3-qubit tab. Hint: Unlike the slide in the lecture,
you'll need to have each true statement be the same negative number.
- Create a 4-qubit embedding in the corresponding tab of the same
spreadsheet, but ensure that q1-q4 and q2-q3 connections remain
unused (weight 0). This reflects the bipartite graph that has no
connections between these qubits on Dwave's machine. Ask yourself:
- How do you replicate a qubit in terms of weight and strengths?
- How do you connect the replicated qubits using the "equal"
relation?
The solution should have 4 ground states (lowest energy in blue)
for the same qubit combinations as in the 3-qubit solution, higher
energy states are results that are not considered (as the truth),
i.e., notice that we ignore duplicate (input) states with a higher
energy (output state). Remember: The analogy to input/output
states is misleading, this is only a mental bridge to classical
circuits for us. (There is no input/output, just an
equation/relation/state that we observe and interpret, usually in
classical terms.)
Turn in a screen shot of both tabs of spreadsheet as file nor.pdf
- (30 points, 15 each)
Create an Ocean program for the NOR relation in simulation and on actual hardware.
- Start with the simulated AND solution (see slides). Modify it to reflect the
3-qubit Qubo from the previous problem. Make sure it runs and
outputs the correct answers with lowest energy. Annotate the
output as a comment (see AND solution).
- Start with the hardware AND solution (see slide). Modify it to reflect the
4-qubit Qubo from the previous problem. Make sure it runs and
outputs the correct answers with lowest energy. Annotate the output
as a comment (see AND solution).
Turn in files nor-sim.py and nor-hw.py
- (20 points) Generalize D-Wave's factoring example to return 4-bit
factors.
D-Wave
factoring tutorial provides a rough idea of the problem.
The Jupiter Notebook
(Factoring Example) gives more details.
- Download the
factoring
example:
git clone https://github.com/dwave-examples/factoring.git
cd factoring
- Consult the following files:
demo.py
factoring/interfaces.py
https://github.com/dwavesystems/dwavebinarycsp/blob/master/dwavebinarycsp/factories/csp/circuits.py
and read the
factoring
paper, which explains how to express factoring as a binary CSP.
- Test demo.py and interfaces.py to factor the number 56:
python demo.py
- Verify that your results are correct. Notice that only 3-bit
factors are being considered.
- Modify demo.py and factoring/interfaces.py to use 4
bits for each factor and 8 bits for the product. Then factor
the number 56 again.
- Verify that your results are correct, i.e., you should now see
4-bit factors as well (every now and then, you may have to run repeatedly).
- Hints:
- Change the number of reads to 2000 (more than 50 samples needed)
- Change the output to be 8 bits (p0..p7) and inputs to be 4
bits (a0..a3, b0..b3).
- Change the multiplication_circuit to operate on 4 bits.
- Modify demo.py to invoke factor with a 2nd parameter of False to
indicate that no prior embedding exists.
- Change the chain strength in dimod.embed_bqm().
3.55 worked best based on trial and error some time ago. This
may have changed...
- Augment the sample output to include a new field
'energy'. Notice: Without this energy field, you may not see
the correct output, which are the values with lowest energy.
Turn in files demo.py and interfaces.py
- (20 points) Prove that there is no solution of XOR with only 3
qubits. (You can experiment with the quantum apprentice worksheet to
gain some intuition why there is no solution, but the proof has to
be formal.)
Submit proof.pdf
- (15 points) Construct a correct 4 qubit XOR Hamiltonian
utilizing 1 ancilla qubit and assuming qubits to be either
in state 0 or 1 by
- writing down the constraints for your target ground states and
then all other states,
- reducing these constraints where possible,
- trying to find the correct values (by trial and error or
systematically, up to you), and
- verifying your solution in the Quantum Apprentice
spreadsheet.
Notice that adding an ancilla is similar to creating a 4-qubit
embedding for a 3-qubit problem --- in that you add a qubit. It
differs in that you don't create an alignment (equal) between two
qubits, i.e., the ancilla may have different values than any other
qubit for the correct solution (ground states). In fact, it has to
have different values or there was no point in adding the ancilla in
first place (to extend your Hamiltonian space).
Submit xor.pdf, the snapshot of the Quantum Apprentice spreadsheet.