Homework 1

Assignments: These assignments are optional, but highly encouraged. They will not be checked.

  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: 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: 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