QUANTUM COMPUTING THE SOFT WAY

We’ve developed most of the ideas needed to do universal quantum computing. We understand qubits, quantum states, and have a repertoire of quantum gates. However, all our gates involve just a single qubit. To compute, we need some way for qubits to interact with one another. That is, we need quantum gates which involve two (or more) qubits.

An example of such a gate is the controlled-NOT (or CNOT) gate. In the quantum circuit language we have two wires, representing two qubits, and the following notation to represent the CNOT gate:

The wire with the small, filled dot on it (the top wire, in this example) is called the control qubit, for reasons which will become clear in a moment. And the wire with the larger, unfilled circle on it is called the target qubit.

Up to now I haven’t said what the possible states of a two-qubit system are, but you can probably guess. We now have four computational basis states, corresponding to the four possible states of a two-bit system: $|00\rangle$, $|01\rangle$, $|10\rangle$, and $|11\rangle$. And, for a two-qubit system, not only can we have those four states, we can also have superpositions (i.e., linear combinations) of them:

$$\alpha|00\rangle+\beta|01\rangle+\gamma |10\rangle+\delta|11\rangleα$$

Here, the amplitudes $\alpha, \beta, \gamma, \delta$ are just complex numbers, and the sum of the squares of the absolute values is 1, i.e, $|\alpha|^2+|\beta|^2+|\gamma|^2+|\delta|^2 = 1$. This is the same kind of normalization condition as we had for a single qubit.

Now, the CNOT gate is, much like the quantum NOT gate, inspired directly by a classical gate. What it does is very simple. If the control qubit is set to 1, as in the states $|10\rangle$ and $|11\rangle$, then it flips (i.e., NOTs) the target qubit. And otherwise it does nothing. Writing out the action on all four computational basis states we have:

$$\begin{aligned} |00\rangle & \rightarrow & |00\rangle \\ |01\rangle & \rightarrow & |01\rangle \\ |10\rangle & \rightarrow & |11\rangle \\ |11\rangle & \rightarrow & |10\rangle \end{aligned}$$

If you’re familiar with classical programming languages, then you can think of the CNOT as a very simple kind of if-then statement: if the control qubit is set, then NOT the target qubit. But while simple, it can be used as a building block to build up other, more complex kinds of conditional behavior.

There’s a way of summing up all four of the equations above in a single equation. Suppose x and y are classical bits, i.e., 0 or 1. Then we can rewrite the equations above in a single equation as:

$$\begin{aligned} |x, y\rangle & \rightarrow & |x, y\oplus x\rangle. \end{aligned}$$

Note the commas inserted to make this easier to read – this is pretty common in working with multi-qubit states.

The above equation makes clear that the CNOT leaves the control qubit x alone, but flips the target qubit y if x is set to 1. Note that $\oplus$ is addition modulo 2, where $1 \oplus 1 = 0$, as we would expect from the fact that the CNOT takes $|11\rangle$ to $|10\rangle$.

That’s all there is to the CNOT. It’s really a very simple idea and quantum gate. Note that it of course acts linearly on superpositions of computational basis states, as we expect for a quantum gate. So:

$$\begin{aligned} & \hphantom{ \rightarrow } \alpha|00\rangle+\beta|01\rangle+\gamma |10\rangle+\delta|11\rangle \\ & \rightarrow \alpha|00\rangle+\beta|01\rangle+\gamma |11\rangle+\delta|10\rangle \end{aligned}$$

And, though I won’t explicitly carry out the verification, the CNOT is unitary, and thus preserves the length of quantum states, as we expect.

Of course, the CNOT doesn’t just appear in two-qubit computations. It also appears in computations involving more qubits. Let’s suppose we have three qubits, for instance, and computational basis states such as $|000\rangle, |001\rangle∣000⟩$, and so on. Here’s a CNOT with the second qubit as the control qubit and the third qubit as the target:

What goes on? Well, we can write out what happens on an arbitrary computational basis state, $|x, y, z\rangle$, where x, y and z are all classical bits. Of course, the first bit x isn’t changed at all, since it’s not involved in the CNOT. The second bit y is the control bit, and so isn’t changed. But the third bit z is flipped if the control bit y is set to 1. And so we can write the action of the CNOT as:

$$|x,y,z\rangle \rightarrow |x,y, z\oplus y\rangle$$

I’ve described the CNOT as a “classical” gate, but it can be combined with single-qubit gates to do non-classical things. Let me give you an explicit example. It’s another two-qubit computation. It starts with the $|00\rangle$ computational basis state, we apply a Hadamard gate to the first qubit, and then do a CNOT:

Recall that for a single qubit the Hadamard gate takes $|0\rangle$ to an equal superposition $(|0\rangle+|1\rangle)/\sqrt{2}$. For these two qubits it doesn’t affect the second qubit at all, and so it takes $|00\rangle$ to $(|00\rangle+|10\rangle)/\sqrt{2}$.

Next we apply the CNOT gate. This leaves the $|00\rangle$ state unchanged, since the control bit is 0. And it takes $|10\rangle$ to $|11\rangle$, since the control bit is 1. And so the output from the circuit is:

$$\frac{|00\rangle+|11\rangle}{\sqrt 2}.$$

This output state is a highly non-classical state – it’s actually a type of state called an entangled state. There’s no obvious interpretation of this state as a classical state, unlike say a computational basis state such as $|00\rangle$. In fact, entangled states can be used to do all sorts of interesting information processing tasks, including quantum teleportation and fast quantum algorithms.

A point I glossed over above, but worth mentioning: in the circuit I drew $|0\rangle$ and $|0\rangle$ separately as input qubits. It’s conventional to do that kind of thing to denote a combined input of $|00\rangle$. More generally, people use $|0\rangle|0\rangle$ interchangeably with $|00\rangle$, $|0\rangle|1\rangle$ interchangeably with $|01\rangle$, and so on. Going back and forth takes a bit of getting used to, but everything works pretty much as you expect, and you just need a little practice before it seems quite natural.

More generally, if we have single-qubit states $\alpha|0\rangle+\beta|1\rangle$ and $\gamma|0\rangle+\delta|1\rangle$, then the combined state when the two qubits are put together is just:

$$\begin{aligned} & \hphantom{ = } (\alpha|0\rangle+\beta|1\rangle)(\gamma|0\rangle+\delta|1\rangle) \\ & = \alpha\gamma|00\rangle+\alpha\delta |01\rangle+ \beta\gamma |10\rangle+ \beta\delta |11\rangle. \end{aligned}$$

I said that the CNOT leaves the control qubit alone, and modifies the target qubit. That’s true in the computational basis. In fact, it’s actually possible for the target qubit to affect the control qubit. It’s worth taking a minute or two to at least understand (and, if you’re feeling energetic, attempting to solve) the following exercise:

Exercise: Can you find single-qubit states $|a\rangle$ and $|b\rangle$ so that applying a CNOT to the combined state $|ab\rangle$ changes the first qubit, i.e., the control qubit?

Let me give you an example which solves the above exercise. Suppose we introduce single-qubit states $|+\rangle$ and $|-\rangle$, defined by:

$$\begin{aligned} |+\rangle & := \frac{|0\rangle+|1\rangle}{\sqrt 2} \\ |-\rangle & := \frac{|0\rangle-|1\rangle}{\sqrt 2} \end{aligned}.$$

A mnemonic for this notation is that these are both equal superpositions of $|0\rangle$ and $|1\rangle$, but the “+” or “-” corresponds to the sign of the amplitude for the $|1\rangle$ state. The following circuit identity holds:

That is, if we put $|+-\rangle$ in, then $|--\rangle$ comes out, i.e., the target qubit isn’t changed, but the control qubit is! The proof is just to follow the definitions and the algebra through. It’s honestly not terribly enlightening to follow the algebra through at this point – it’s a lot easier once certain other facts are known to you. But, again, if you’re feeling enthusiastic it’s a good exercise to work through to become familiar with how things work.

It’s worth taking some caution from this example. It means that intuitions coming from the computational basis can sometimes be incomplete or misleading. The CNOT isn’t simply doing something to the target, conditional on the control. It’s also doing something to the control, conditional on the target.

Exercise: Show that the inverse of the CNOT gate is just the CNOT gate.

Without mentioning it explicitly, when describing the CNOT gate we have introduced one of the main protagonists of the quantum world: the Queen of Quantum, namely, entanglement. Let's listen first to a very general layperson introduction on what entanglement is by looking at this video:

Time for a Moodle entanglement survay #1! Go to Moodle and describe in your own words what the key feature of quantum entanglement is!

Quantum entanglement is a key feature of quantum systems composed by more than one particles, or degrees of freedom. In fact, it describes specific types of correlations that may exist between quantum particles but can never be observed in classical particles. This is how Prof. Monkey explains to his grandma this whole business:

To play with quantum correlations, try out the Quantum Solitaire, in which the rules of entanglement are encoded into special rules. You can play the game online here!

We are now ready to complete our journey into quantum entanglement by establishing a link between what we have learned in this section and what we have discussed in the previous section when introducing the CNOT gate. We'll give this task to Professor Artur Eckert:

And here is yet another short video by Artur to explain the CNOT gate, this is for you a repetition of what you have learnt in the previous section, something to consolidate your knowledge.

The mathematics behind quantum entanglement is explained in this document, after having built an intuition, let us look in more depth at the mathematical formalism.

Finally, we have all the ingredients needed to apply our knowledge to program quantum computers. How does a program which runs a CNOT gate on a real quantum computer looks like? Challenge yourself with the Apply section of Quantum Entanglement!

Now that you are an expert, let's do back to Moodle entanglement survay! Go to Moodle and answer to entanglement survay #2: describe in your own words what the key feature of quantum entanglement is! Wait! Isn't this the same as entanglement survay #1? Correct, but have you now changed your mind or understood things differently?

Now that we have another quantum superpower, time for another tournament of TiqTaqToe, this time using not just quantum superpositions but also entanglement. Ready to Play? Wait for special instructions to participate to the tournament, and meanwhile start practicing here.

© QPlayLearn 2020