Non-atomic gates#
In order to build Shor’s algorithm, we need a (long-range) control-phase gates. Our simulator doesn’t have these gates as part of their native set. Instead, we need to figure out how to write the control-phase gates as a combination of our atomic gates - (H,P,CNOT) - which we know can be done because those are a universal gate set. First let’s worry about building a nearest-neighbor phase-gate building it up from a series of simpler gates.
Eventually at the end of this section, we will write a “compiler” which take a description in terms of the non-atomic gates and converts them into an atomic-gate description.
Not Gate#
Build a gate out of H and P which takes
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#
and
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.