An EPR pair is two entangled qubits of the form $|00\rangle + |11\rangle$ Construct a circuit which generates an EPR pair from $|00\rangle$. Write out the circuit desription as input and run it through your simulator showing that you get the correct result. Can you figure out how to do this with only single-qubit gates?

Alice and Bob and Causality

This subsection is just for fun (but if you're ahead of the game go ahead and do it)

Bob and Alice want to communicate faster then the speed of light. Here is how they are going to try to do it. They are going to first build an EPR pair. Then they are going to pause their quantum circuit for a bit. Alice is going to take her wire (the 0'th wire) and go off to Alpha Centauri. Then Bob is going to do some unitary operation on his wire (but he can only do it on his wire (the 1'st wire) because Alice's wire is far away!). Then they are going to measure, but Alice only gets to see the result of her wire. We can model this in the following way:

2
Put her the circuit description for building EPR pairs
U 1 theta phi  <---- Bob can do anything he wants to his wire. 
Measure <--- Alice only gets to see the first digit of the binary number (so just tell your code not to print the second digit out)

Technical note: You can do measurement on the wires even if the wires are far way

So then Bob wants to do is to tell Alice either "yes" or "no". So for "yes" he has to pick a certain theta and phi. For "no" he has to pick a different theta and phi. Experiment with various choices of theta and phi for "yes" and "no" and see if Bob can make this communication.

Copying Circuit

This circuit essentially takes a state and gives back two copies of the state. Can you use this circuit to communicate faster then the speed of light?

Arbitrary superposition over all binary numbers

Almost every quantum algorithm starts by generating a uniform superposition over all binary numbers. Construct a circuit which takes $|0..0\rangle \rightarrow \sum_i |i\rangle $. Write code that generates such circuits for any number of wires and run it through your simulator.

Let's learn something else about the power and limitation of quantum computers. Suppose the rest of the circuit is just made from tofelli gates which are universal for classical computing. Then you'd be able to implement an arbitrary classical function $f$ with the rest of the circuit. Therefore, at the end of the circuit you would have $\sum_i |f(i)\rangle$ (understand this statement!*). It seems that you've magically done in parallel an exponential number of calculations. Suppose you do this and then call Measure at the end of your circuit? What happens?

A single binary number

Build a circuit which generates any particular binary number. Write code that takes the input $i$ and builds a circuit description which takes $|0...0\rangle \rightarrow |i\rangle$. Test it with your simulator.

Inverting a CNOT

Suppose we only let you have CNOT whose "control bit" is less than the "not bit." Can you write a circuit description (run it through your simulator) that emulates the upside-down CNOT.

Swap gate

We are now done with arbitrary one-qubit gates. Let's build some circuits for more wires.

In various situations you will want to be able to re-arrange wires. To do this we want a swap gate which exchanges two wires. Let's start out with doing this for nearest neighbor wires. For example, if you were swapping wires two and three you might take a state $|0010\rangle \rightarrow |0100\rangle$. Then figure out how to do it at arbitrary distances. Add to your preprocessor a step which takes

1	`SWAP 0 2`

and replaces it with your universal gates. How would you use this to implement long range CNOT if you have only short range CNOT?

Some Circuits