Shhhh… the quantum cheat sheet
Welcome to Introduction to Quantum Computing. I am your guide, Associate Professor Chris Ferrie, a researcher in the UTS Centre for Quantum Software and Information. This is Lecture 5. It would probably be a good idea to have read the previous Lectures before continuing:
What did you learn last week?
In the last few weeks you completed your basic training. You now know about quantum information, how to write it, how to read it, and how to dial it up to 11 with entanglement. Entangled states were those that could not be written as product states (in any basis!). With multi-qubit states and gates, you have all the tools you need to start creating quantum algorithms.What will you learn this week?
But not so fast! Most quantum algorithms use a standard toolset. This week you will fill your tool box with the canonical gate set and learn how to quickly recognise their utility and tricks for working with them. At the end of the week, you’ll have a complete “cheat sheet” that you’ll be able to refer to when we analyse the first practical quantum protocols.What will you be able to do at the end of this week 5?
At the end of this module, you should be able to answer these questions:
Which are the canonical single qubit gates?
Which sets of gates are not useful?
How do I create most two qubit gates from one?
Three qubit gates… and beyond?
How do I analyse a quantum circuit?
Models of quantum computation?
Wait. What? Models of quantum computation — there are more than one? Yes!
There is the adiabatic model — a continuous time model which encodes information in the lowest energy state of a system that can be gotten at by very slowly changing the system from a simple one to the (presumably) more complicated one.
There is measurement-based quantum computation — rather than starting in a product state and creating entanglement, here we imagine starting with a highly entangled state of many qubits. Instead of using gates, the computation proceeds by performing sequences of measurements, one depending on the results of the former. The answer is encoded in the results of outcomes of the measurement.
Unitary circuit model — this is the standard model and the one we have been discussing (though not in detail), which closely matches the digital circuit model of classical computation.
In addition to each of the above, there are finer-grained categories of quantum computation within each. One, within the unitary circuit model, can be phrased as the choice of gate set. A gate set is a small finite set of gates from which all others can be generated. You might think that the smallest gate set would be preferred, but it is not so simple. Smaller gate sets might require longer computations to reach a target, even if it is in principle possible. More importantly is the considerations of error correction. Some choices of gate sets are easier to error correct. Since we assume that error correction will play a crucial role in quantum computation, these gate sets are the most commonly considered. Error correction is also extremely interesting, but the details require some tools and will have to wait.
These are not the gates you are looking for
Not every gate set is useful. Clearly, the gate set containing only the identity gate is useless, but others you might not be so sure about. Take, for example, the Hadamard gate.
Although this circuit generates superpositions (all of them in fact!), we can separately calculate what happens to each qubit. This requires, for n qubits, only n 2-dimensional vectors to be stored and manipulated. This would be true of any number of single-qubit gates. Clearly, then, to do something non-trivial we need entanglement. We showed last time that the CNOT gate generates entanglement. But this circuit, for example, only changes one computational basis state into another at each step.
It is a classical computation on the labels of the basis states. Not good enough! Putting the Hadamard and CNOT together generates superposition and entanglement. However, you’ll note something peculiar about a randomly chosen circuit of this type.
You can only ever generate superposition with +1 or -1 in front of the basis states (ignoring the overall normalisation). There are definitely no complex numbers to be seen here. Oddly enough, if you add just two new single-qubit gates, you can generate any other unitary matrix, no matter how big!
Mr. T gate
Surprisingly, gates on single qubits are the most important ones in many models of quantum computation. The gate set consisting of CNOT, Hadamard, and two different phase gates — called S and T — are enough to generate any other gate. That is, any computation — no matter how large — can be built up from a small set of one- and two-qubit gates!
If you recall we mentioned this fact when the Solovay-Kitaev theorem. One thing we have left out is that a finite set of gates cannot generate any gate perfectly since all unitaries form an uncountable set. The theorem shows that we can get arbitrarily close to any other gate with a number of elementary gates that grows very slowly in the accuracy we desire.
Your first quantum primitive
Another important gate that we will use is called the Toffoli, or CCNOT (controlled-controlled-NOT), gate. The Toffoli can simulate the classical NAND gate. In fact, we can perform many logic operations on the binary labels of the computational basis.
Since NAND is universal for classical computation, the Toffoli immediately shows that classical computing is contained within quantum computing. This 3 qubit gate can actually be implemented exactly with CNOT, Hadamards, and the T gate. It looks like this.
(You can also play a bit more interactively here.)
Why does it look like that? Why do you need these weird phase gates? Well, one answer is, lots of guess work, trial-and-error, and some intuition from building and playing with circuits. Some idea of where the phase gates come from is the following equivalent circuit to the Toffoli.
The first thing is to convince yourself that, by looking at all four combinations of bits on the first two registers, this is indeed equivalent to the Toffoli gate. The next thing to notice is that the “square-root-of-X” gate contains complex phases and these need to be implemented with some phase gate in addition to simple gates that do not introduce complex numbers.
Cheaters never prosper
Now you have seen some primitive gates. You don’t really need to memorise them — most don’t. However, some are used so often that they are implicitly committed to memory. You can find many “cheat sheets” with the common gates, how they are drawn in circuit notation, and what their matrix representation looks like. For example, Wikipedia has a nice table. However, most don’t have the Dirac notation equivalent. Your homework is to modify this cheat sheet to create the Dirac-Rosetta stone by adding the Dirac notation representation of each gate.
