Quantum Computer Simulator III

(Later there will be a challenge problem where you show that you can use even less RAM. Although it won’t be a practical algorithm, it will teach us something very important about the computational complexity of quantum computers.)

Now we'd like to combine our I and II simulators. This one will take a state and return another state without ever building a matrix (just like the last simulator). n But, it won't store the state as a long list of (amp,basisString). Instead, our state will be a big vector of size $2^w$ and we will just store the amplitude of $|000\rangle$ in the first place, the amplitude of $|100\rangle$ in the fourth spot, etc.

Write

1
2
3

    def HadamardArray(inWire,numWires,inputState):
      #do some stuff
      return outputState

where inputState and outputState are big vector, but never build a big matrix.

Consider the following quantum circuit.

We’d like to figure out what the state is at the first dotted line without building a large unitary matrix. To accomplish this we are going to use the fact that quantum mechanics is linear. What this means is that if I want to apply a gate to a quantum state, I can just go ahead and apply the gate to every basis element of the quantum state.

Therefore, if I have a quantum state that’s represented as $\sum_i \alpha_i |i\rangle$ then my new state is going to be $\sum_i \alpha_i U|i\rangle$. We know that $H|0\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ and $H|1\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$. So we should think about what the Hadamard gate on wire 2 does to every binary number. We see that

$H_2|000\rangle \rightarrow |0\rangle \otimes (H|0\rangle) \otimes |0\rangle$

which goes to

$|0\rangle \otimes \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes |0\rangle \rightarrow \frac{1}{\sqrt{2}} (|000\rangle + |010\rangle)$.

Now remember that you were applying $H_2$ to $\alpha|000\rangle$ so really you should be getting $\alpha \frac{1}{\sqrt{2}} (|000\rangle + |010\rangle)$. So in the output state you need to add in $\alpha/\sqrt{2}$ to spot 0 (i.e. binary number 000) and $\alpha/\sqrt{2}$ to spot 3 (i.e. binary number 010). You need to figure out the correct application of $H_2$ to every binary number. Once you understand how to do this, then

• loop over all the basis elements of the input state
• for each basis element, figure out what happens when you apply the Hadamard to the appropriate wire and put the amplitudes in the correct place in the output states

Once you’ve figured out how to do this for the Hadamard gate (and written the function), make sure you test. You can do that by comparing against your previous code or using the tests you’ve made there, etc.

Now you have to figure out how to go about this for all three gates. In practice the Hadamard is the hardest. The phase gate and the CNOT gate have the property that they take one basis element to another basis element (i.e. $|b_i\rangle \times |b_j \rangle$).

Notice that, for the CNOT gate, it is now trivial to apply the gate to wires that aren’t nearest neighbors.

Once you’ve figured out how to do this, then you can put everything together. Now instead of building up a big matrix, you can simply take the input state, and apply the gates in sequence.

Question: Given the simulator you’ve just built, how would you (slowly) generate the big unitary matrix? Can you use this to verify your result?

Question: How many qubits are you going to be able to simulate in your new simulator?

Once again, go ahead and test your quantum simulator in various ways. You should verify that it works.

	Grading
	Show that the new simulator works using the same suite of test. It should use the least RAM of all your methods.