Homework 1

Important: Make one submission per group. Write Names and Unity IDs on every submission file of all group members. Name the submission files correctly as asked for.

1. Download and Install qOp on your computer, see instructions here. The Download links are in the Quantum Computing Devices/Simulators section. The installation instructions are present on the Lecture Notes and Readings Page for qOp and README in the tar package.(OSX, Linux,Windows) Ignore the links for DWave, software and qbsolv.
2. (10 points) Try out the factoring-42 example:

       cd qOp
       cd examples
       cd toq
       toqSim factor42.toq
     

   As you can see, only 3-bit answers are given.
   Extend the program to return all pairs of factors of 42.
   Hint: How many bits would you need? Run your program and check if the result is correct.
   For 42 there are 6 solutions, 3 unique ones, the rest are permutations.

   A note on the side, see the comment in the factor42.toq file: "the FrontEnd solves this case alone". This means that toq uses a constrained solver for single-line asserts. If you specify multiple asserts, the D-Wave system will be used, "which finds the optimal solution to the input problem, and the results (values of the booleans) are passed back to the caller." (see TOQ.pdf documentation)

   Turn in file factor42a.toq

3. (30 points) Visit the AND gate embedding example with the 3-Qbit solution. Fill in the Quantum Apprentice spreadsheet with the correct weights and strengths, first in the 3-Qbit tab, then in the 4-Qbit tab.
   Hints:
   • For 4-Qbits, which strengths remain zero (because the bipartite graph has no connections on Dwave's machine)?
   • How do you replicate a Qbit in terms of weight and strengths?
   • How do you connect the replicated Qbits using the "equal" relation?
   The solution should have 4 ground states (lowest energy in blue) for the same Qbit combinations as in the 3-Qbit 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. (See the factoring-42 example for reversing a function, where input/output states are seemingly reversed. Bottom line: There is no input/output, just an equation/state that we observe and interpret, usually in classical terms.)

   Turn in a screen shot of the spreadsheet as file embed4.pdf

4. (30 points) In Q3, we have a solution to the "AND" logic in a 4 Qbit embedding that we tested in the spreadsheet. Have a look at slide 19 from lec 3. It is as example for half adder on a bipartite graph. Embed the half adder on the 4 qubit spreadsheet. Let's now transform this into Quantum machine instructions (QMI).

   But first, let's run some QMI code:

       cd qOp
       cd examples
       cd dw
       bash A-execute-qmi.bash
       

   Copy the file A-execute-qmi.bash to halfadder-qmi.bash, then create the same embedding as in the example for the half adder equation.
   Hints:
   • Check out D-Wave embedding (slide 20), which shows the Qbit numbering in the Bi-partite graph. The coupler (strength) indexing counts down top-to-bottom, i.e., you get the following connections:
     • Q0000 -- C0000 -- Q0004
     • Q0000 -- C0001 -- Q0005
     • Q0000 -- C0002 -- Q0006
     • Q0000 -- C0003 -- Q0007
     • Q0001 -- C0004 -- Q0004
     • Q0001 -- C0005 -- Q0005
     • Q0001 -- C0006 -- Q0006
     • Q0001 -- C0007 -- Q0007
     • etc.
     The slide represents the virtual qubit to physical Qubit mapping for a 3-bit adder. The left-most bipartite graph with 8 qubits is the half adder, where a_0 and a^~_0 are a physical embedding of logical qubit x into physical Qubits Q000 and Q004 (with an equal relation between them on coupler C000).
   Your solution should have 4 ground states (solutions with objective=0) matching the ones in the spreadsheet, but you may have to translate from the Qbit numbering of QMI to the one in the spreadsheet and perform the embedding for each virtual qubit into 2 physical Qubits. Notice: If you have more/less than 4 solutions or different ones than expected (with high probability), then your weights/strengths are wrong. "Solutions" with only a few samples (<10) our of 1000 samples can be safely discarded, they don't count. (Yes, even the simulator occasionally gives such "solutions".)

   If your embedded solution has 6 qubits or less, you can first test it in this 5/6 qubit spreadsheet before transforming it into QMI code.

   Turn in file halfadder-qmi.bash (dw program) and halfadder.pdf (spreadsheet snapshot)

5. (30 points) In Lecture 3, slide 40, there are errors in the XOR hamiltonian. The ground sets indicated in green in the previous slide for a possible solution with an ancilla bit are correct. Construct a correct XOR hamiltonian assuming qubits to be either in state 0 or 1 (notice: the XOR slides are assuming a state -1 and +1!!!) by (a) writing down the constraints for your target ground states and then all other states, (b) reducing these constraints where possible, (c) trying to find the correct values (by trial and error or systematically, up to you), and (d) verifying your solution in the Quantum Apprentice spreadsheet.

   Submit xor.pdf, the snapshot of the Quantum Apprentice spreadsheet.

6. (20 points, options, extra credit) Proof that there is no solution of XOR with only 3 qubits.

   Submit proof.pdf