Homework 1

1. Install Dwave's qOp on your computer, see instructions here.
2. (30 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.
   Hint: How many bits would you need? Run your program and check if the result is correct.
   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) Revisit the embedding example that takes the 3-Qbit solution (slide 5) to a 4-Qbit solution (slide 10). Fill in the 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" circuit?
   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. (40 points) Following up on the last exercise, let's try to embed the "imply" circuit from of slide 8 in a 4-Qbit subset in the spreadsheet.
   Hints:
   • Set the a-weights for q1 and q2 and the strength for b12. Notice that you already have a solution, but that's not the point. We want to learn how to embed multiple Qbits at once.
   • Split both q1 and q2 into q1+q4 and q2+q3, adjust the a-weights.
   • Connect your split Qbits with the "equal" circuit (using -2 strengths) and adjust the a-weights accordingly.
   The solution should have 3 ground states matching the ground states of slide 8. Verify that the q1+q4 values match, and that the q2+q3 match for any ground state. (If not, then you've made a mistake.)

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