Assignment 8, due Nov. 30, 2005

Reference all your sources completely and accurately.

1. Find a paper in an APS journal that proposes a physical implementation for a qubit. Provide a full and correct citation, and describe briefly the main idea as best you can. You don't have to read the paper, of course, but try to get something out of it beyond the abstract if you can.

The gates in the remaining problems are all classical, not quantum.

2. The CNOT (Controlled NOT) gate has two inputs, say x and y, and two outputs. The first output is just a copy of x. The second output is NOT y if x = 1, and just y if x = 0. That is, the second bit is flipped if and only if the first bit is ON.

Make a CNOT using only AND, OR, and NOT gates.

3. Repeat for the CCNOT (Controlled Controlled NOT, or Toffoli) gate, which is defined as follows: It has three inputs and three outputs. The first two inputs are just copied to the respective outputs. The third input is flipped if and only if the first two input bits are both ON.

4. Prove that the CCNOT gate is universal.

5. Argue that the CNOT is not universal. Try to make your argument as close to a real proof as possible.