Non-atomic gates

In order to build Shor's algorithm, we need a (long-range) control-phase gates. This is not part of our simulator, though. Instead, we are going to build a control-phase out of our atomic gates (H, P, CNOT). First let's worry about building a nearest-neighbor phase-gate.

Not Gate

Build a gate out of H and P which takes

$|0\rangle \rightarrow |1 \rangle$
$|1\rangle \rightarrow |0 \rangle$

	Grading
	Into your document you should paste the circuit description for the Not Gate on a single wire. It might look something like below (but it's not this..in fact as a hint convince yourself that it is silly to have two Hadamards or two Phase gates in a row).

An (incorrect) example NOT gate

INITSTATE BASIS |1>
H 0
P 0 0.3
H 0 
H 0
P 0.25
P -0.2

Also paste into your document the result of the run with the initial state being $|1\rangle$

Rz Gate

\[Z= \begin{bmatrix} 1 & 0 \\ 0 & -1 \\ \end{bmatrix} \]

and

$$R_z(\theta)=e^{-i \frac{\theta}{2} Z}$$

Build a gate out of H and P which give you a $R_z$ gate. Think about how you would do it using NOT and P gates.

	Grading
	Also, paste a description of that into your document.

Control-Rz Gate

Consider your Rz gate without the NOT in it. What gate do you have then?

Then figure out how to use this fact to build a control-Rz. You should make this work for arbitrary distance between your control and Rz but
can assume you have a long-range CNOT.

	Grading
	Also, paste a description of that into your document.

Your description should look something like this:
An (incorrect) example control-Rz gate

INITSTATE BASIS |10>
H 0
CNOT 0 1
P 1 0.3

Control-Phase Gate

Your control-Rz and control-phase should differ by a global phase if the control bit is 1. Figure out how to do modify your control - Rz to do this.

	Grading
	Also, paste a description of that into your document.

Congrats. You know have a working control-phase gate!

Swap Gates

In addition to control-phase gates you will need a swap gate. A swap gate allows you to take two wires and exchange them. This means that if there are two wires that are far apart, you can make them closer. It also means that if you wanted to reverse your wires you can do that (and you will need to!)

In terms of Dirac notation, here's an example of a swap gate:
$$ \textrm{Swap(12)}(\sqrt{0.3}|010\rangle + \sqrt{0.5}|001\rangle + \sqrt{0.2}|000\rangle = \sqrt{0.3}|001\rangle + \sqrt{0.5}|010\rangle + \sqrt{0.2}|000\rangle$$

Figure out how to construct swap gates from H, P, and CNOT.

	Grading
	Also, paste a description of SWAP(2,5) into your document

Long-Range CNOT

For the CNOT gate you were required to make it work with just nearest-neighbor gates. If you built a fancy enough simulator (II or III) you can easily implement the CNOT to work for non-nearest-neighbors. If you haven't built such a simulator figure out how to emulate this just using nearest neighbor CNOT and swap gates.

Pre-compiling

You've now figured out how to build a (long-range) control-phase and (long-range) CNOT out of elementary gates. You've also figured out how to build SWAP out of elementary gates. You could now take a circuit description like:

9
H 0
CPHASE 0 5 0.3
P 1 0.3
CNOT 4 7
SWAP 2 8

and then write a python code that takes this circuit description and generates a new circuit description which uses only H and CNOT (and only short-range ones if your simulator does only short-range CNOT). Do not modify your quantum computing simulator to do these gates! It should only eat H CNOT and P.

	Grading
	Construct an input and run your precompiler on it. Convince yourself (and us) that this is the correct answer.