Universal quantum gates

It is well known that in a boolean circuit, a finite set of gates is enough for realizing all possible boolean functions. Such a gate set is called ‘universal’. The most common universal gate set consists of AND, OR, NOT (and COPY if you view copying a non-trivial operation). In fact, NAND (and COPY) is enough for universality. For a reversible boolean circuit, a commonly used universal gate set includes NOT and Toffoli.

For quantum circuits, i.e., unitary operators over a fixed yet arbitrary number of qubits, there also exists the notion of universal gate sets. However, more subtlety arises from the structure of complex Hilbert space. Roughly speaking, there are three levels of universality:

• the ability to exactly realize any unitary operator, possibly with ancillae;
• the ability to approximately realize any unitary operator, possibly with ancillae;
• the ability to approximately simulate any unitary operator, with ancillae.

The meaning of the first two levels are not hard to understand. As for the third level, the difference between ‘simulation’ and ‘realization’ is that we may restrict ourselves to real superpositions of the quantum states and simulate the complex superpositions at the cost of more qubits. D. Aharonov’s note made a detailed clarification. He called the second and the third level here ‘strict universality’ and ‘computational universality’ respectively. We will come back to this point later.

The existence of a universal gate set makes hardware design much easier: you just need to design and benchmark a small number of gates for achieving universal computation. It also benefits fault-tolerance, since it is highly nontrivial for implementing logical gates on a quantum error-correcting code fault-tolerantly. Apart from these practical considerations, universal gate sets also enrich the tool box for theoretical scientists. A really interesting example, as we will discuss, is that the notion of ‘computational universality’ bridges the quantum and classical probability, since it can be used to make our life free of imaginary numbers.

Now let’s dive into the history.

In 1995, A. Barenco et al. realized that all single qubit unitary operators with a two-qubit CNOT gate can be used to exactly realize all the unitary operators on multiple qubits (see paper). In 1997, A. Kitaev discovered that a finite set of gates can be used to approximately realize all multiple-qubit unitary operators at a moderate cost (see paper). In his paper, Kitaev acknowledges Solovay as another independent discoverer of the result, which is commonly referred to as the ‘Solovay-Kitaev theorem’ today.

Note that the Solovay-Kitaev theorem concerns not only the ability but also the efficiency of a finite set of gates to approximate a unitary operator. Kitaev also proposed a classical algorithm to compile a general operator to a sequence of the universal gates. In fact, the ability of a finite set of gates to approximate an operator is not surprising since it only requires that the set of gates generate a dense subset of the unitary group. The non-trivial part is to prove the efficiency of representing an operator with a sequence of universal gates, which makes use of the non-abelian property of the unitary group. (For an abelian group, a simple counting negates the possibility of representing exponential number of group elements by a polynomial-length product of finite elements.) See Kitaev’s book for a comprehensive and detailed explanation.

In Kitaev’s construction, the universal gate set includes the single-qubit Clifford gates (generated by the Hadamard gate and the phase gate) and the quantum Toffoli gate. Another widely used universal gate set was proposed in 1999 by P. Boykin et al. (see paper). This gate set, often referred to as Clifford+T, includes the single qubit Hadamard gate, T gate (which is the \(\pi/4\)-rotation around \(Z\)-axis), and two-qubit CNOT gate.

Both constructions above can be understood as the Clifford group combined with a non-Clifford gate. The Clifford group is the unitary subgroup that maps a Pauli operator to a Pauli operator through conjugation, which itself is not universal due to Gottesman-Knill theorem (see paper). It was later proved that Clifford group combined with any non-Clifford gate is universal. It seems that there is no single paper addressing this statement. According to the discussions on Stack Exchange (Quantum Computing) and Stack Exchange (Theoretical Computer Science), as well as Appendix. D in E. Campbell et al.’s 2012 paper, the statement that Clifford group with any non-Clifford gate generates a dense subset of the unitary group follows from a series lemmas on the Clifford group proved by Nebe et al. from 2000 to 2006. The efficiency of representation also holds for these universal gate sets since Kitaev’s statement of efficiency does not depend on the choice of the gate set.

An interesting observation on quantum computing is that states with complex amplitudes can be easily simulated by states with only real amplitudes, through adding only one qubit for flagging the real and complex part. See D. Aharonov’s note for a detailed explanation. In 2002, Yaoyun Shi (施尧耘) proved that when considering only real superpositions of computational basis, Hadamard gate and Toffoli gate form a universal gate set (see paper). D. Aharonov’s note gave a simpler proof of Shi’s result. In this note, Aharonov clarified the idea of ‘strict universality’ and ‘computational universality’, corresponding to the second and the third level of universality we discussed above.

Shi’s result is really powerful for connecting quantum and classical probabilities. At early times of quantum computation, complexities were discussed based on quantum Turing machines. In 1997, E. Bernstein and U. Vazirani showed that BQP is contained in P^#P and hence in PSPACE (see paper). At the same year in 1997, L. Adleman et al. showed that BQP is contained in PP (see paper). However, with the help of the complete basis Hadamard+Toffoli, such properties is arguably much easier to prove based on circuit models, which can now be mapped to classical computation models. A beautiful result along this way, namely PostBQP equals PP, was proved by S. Aaronson in 2004 (see paper on arxiv or his own site for a finer version).