Quantum Computing for Computer Science Types II

Monday , 9, December 2019

In the previous post we started to explain how to understand quantum computing from a computer science perspective, even without knowing the underlying quantum mechanics. We did so by explaining that you can consider everything in terms of the math, and we began the process of explaining what happened in the quantum entanglement program we introduced in earlier posts.

It’s a useful technique to keep explaining things in a little more depth as we go down the rabbit hole. You may have noticed that I avoided qubits that are in a state of superposition in the last post, and chose to show the CNOT gate instead of the Hadamard gate. In fact I used |0⟩ and  |1⟩ which are special cases where the qubits will collapse down to 0 and 1 with 100% probability. Qubits that have been put into a state of superposition will have a different probability distribution.

A qubit can be represented as a combination of probabilities of being in each vector state |0⟩ and |1⟩ written as: |φ⟩ = α|0⟩ + β|1⟩ where |α|2 + |β|2 = 1. Notice that when we refer to |0⟩ we mean that α=1 and β=0. These do not have to be real numbers they can be imaginary, but it certainly is easier to stick with reals. By the way, another way of writing these vectors is αβ

Recall that the Hadamard gate rotates our qubit to the “equator” of the Bloch sphere. If we collapse that onto the Z axis by taking a measure operation, it has a 50% chance of being measured as a 0 and a 50% chance of being measured as a 1 since it is equidistant from north and south poles. Below are some examples of valid vector values for qubits. Note that the first two examples are equally likely to be measured as 1 or 0, as they have been rotated to different points on the equator of our sphere. The third example will always be measured to be a 1.

    1 2 1 2             1 2 -1 2             0 -1             -1 3 2 3             1 2 3 2

This holds true for multiple qubits as well. If we have a circuit with two qubits there is a probability that each of the four possible states will be measured, and those probabilities sum to 1. It could be that the qubits will be measured and collapse down to |00⟩ with a probability of 1, and there is no chance for the other three. It could also be that each of the four possible outcomes is equally likely.

Why does this matter? Consider our friend the Hadamard gate, applied to each of two qubits. They are both in a state of superposition, and if we measure both qubits at this point all four possible outcomes have a 25% likelihood.

A system with multiple qubits is represented as a tensor product. Since the Hadamard gate puts qubits into a state where zero and one are equally likely tobe measured, if we apply it to each of two qubits in a circuit, we can depict it like this:

    H( q0, q1 ) = 1 2 1 2 1 2  ⊗  1 2 1 2   =   1 2 1 2 1 2 1 2

In this 2-qubit system, with both qubits having the Hadamard gate applied, we can see that each of the four possible states that can be measured are equally likely. Since ½ squared is ¼, and ¼ + ¼ + ¼ + ¼ = 1 we can say that there is a 25% chance each of measuring |00⟩, |01⟩, |10⟩, or |11⟩.

So you probably noticed how we chose to explain the CNOT gate used in our entanglement program first, and held off on explaining the Hadamard gate. Here’s the accurate representation of what the Hadamard gate does; again we oversimplified things earlier.

H( |0⟩ ) = 1 2 1 2 1 2 -1 2  ⊗  1 0  =  1 2 1 2           H( |1⟩ ) = 1 2 1 2 1 2 -1 2  ⊗  0 1  =  1 2 -1 2

Notice there is a slightly different result when applying the Hadamard gate to |0⟩ and |1⟩. In both cases there is an equal likelihood that we will measure a 0 or 1. The difference is noticeable on the Bloch sphere, as these two vectors are rotated to opposite points along the equator.

Again, I don’t understand the physics of quantum computing, but from the math we can also see that applying a Hadamard gate once again takes the qubit out of superposition. Hadamard is a 90° rotation (refer back to the Bloch sphere image above) that takes a qubit from a pole to the equator, and if applied again, back to a pole. Here is that same idea expressed in math instead of words:

H 1 2 1 2   =   1 2 1 2 1 2 -1 2 1 2 1 2   =   1 0    and    H 1 2 -1 2   =   1 2 1 2 1 2 -1 2 1 2 -1 2   =   0 1


So this is the way for computer science people to think about the basic mechanics of quantum computing. Qubits can be put into superposition, for example the Hadamard gate does put |0⟩ and |1⟩ qubits into an equal superposition, and it is reversible with an additonal application of the Hadamard gate. This might come in handy later, as an alternative to collapsing a state of superposition by a measure operation which leaves us unable to continue computing.

So now we’ve seen an effective way for computer scientists to think about using qubits and gates to construct circuits. You can use this conceptual model to consider parts of more complex circuits, and to have a logical representation of what is going on that does not depend on understanding the underlying physics.