Gates and circuits: Programming with unitary matrices

In 1985 David Deutsch, at Oxford, defined the universal quantum computer: a Turing machine whose states can be in superposition. The model that won out, however, was the one he himself developed in 1989: quantum circuits, wires that carry qubits and gates that transform them. It is the language in which every quantum algorithm is written today.

Gates are unitary matrices

Theorem (characterization of unitaries)

For a matrix $U \in ℂ^{d \times d}$ the following are equivalent: (1) $U^{†} U = I$ ; (2) $U$ preserves inner products, $⟨ U ϕ | U ψ ⟩ = ⟨ ϕ | ψ ⟩$ ; (3) $U$ preserves norms, $‖ U ψ ‖ = ‖ ψ ‖$ ; (4) the columns of $U$ form an orthonormal basis.

Proof

(1)⇒(2): $⟨ U ϕ | U ψ ⟩ = ⟨ ϕ | U^{†} U | ψ ⟩ = ⟨ ϕ | ψ ⟩$ . (2)⇒(3) is the case $ϕ = ψ$ . (3)⇒(2) uses the polarization identity, which recovers the inner product from norms: $⟨ ϕ | ψ ⟩ = \frac{1}{4} \sum_{k = 0}^{3} i^{- k} ‖ ϕ + i^{k} ψ ‖^{2}$ . (2)⇔(4): the entries of $U^{†} U$ are the inner products of the columns. (4)⇒(1) for the same reason.

The most common single-qubit gates are the Pauli matrices, the Hadamard gate and the phase gates:

X, Y, Z, H = \frac{1}{\sqrt{2}} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}), S = (\begin{matrix} 1 & 0 \\ 0 & i \end{matrix}), T = (\begin{matrix} 1 & 0 \\ 0 & e^{i π / 4} \end{matrix}) .

On the Bloch sphere, every single-qubit gate is a rotation. $X$ , $Y$ and $Z$ are half-turns about each axis; $H$ is a half-turn about the axis between $x$ and $z$ ; $S$ and $T$ are quarter and eighth turns about $z$ .

Theorem (Euler decomposition)

Every unitary $U \in ℂ^{2 \times 2}$ can be written as

U = e^{i α} R_{z} (β) R_{y} (γ) R_{z} (δ), R_{z} (θ) = e^{- i θ Z / 2}, R_{y} (θ) = e^{- i θ Y / 2},

for some real numbers $α, β, γ, δ$ : any rotation of the sphere is a composition of rotations about $z$ , $y$ and $z$ .

Two qubits: CNOT

The controlled-NOT gate flips the second qubit (the target) only if the first one (the control) is 1. In the basis $| 00 ⟩, | 01 ⟩, | 10 ⟩, | 11 ⟩$ :

CNOT = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix}), CNOT (H \otimes I) | 00 ⟩ = \frac{| 00 ⟩ + | 11 ⟩}{\sqrt{2}} = | Φ^{+} ⟩ .

A Hadamard followed by a CNOT creates entanglement from scratch. Try it in the simulator.

A three-qubit circuit simulator. Click on a cell to cycle through the gates; a ● in a column turns the other gates in that column into controlled gates (● plus ⊕ is a CNOT; ●●⊕ is a Toffoli). The bars show the

2^{3} = 8

amplitudes of the final state: the height is the probability and the colour is the phase. The examples include a Bell pair, a GHZ state and the Deutsch–Jozsa algorithm.

Universality

Classically, NAND is enough to build everything. Is there a finite quantum set that is enough too? The answer comes in two steps.

Theorem (exact universality; Barenco et al., 1995)

Every unitary on $n$ qubits can be written exactly as a product of CNOT gates and single-qubit gates.

But there are infinitely many single-qubit gates, and a real device can only implement a few with high precision. Fortunately, approximating is enough, and it is cheap:

Theorem (Solovay–Kitaev, 1995–1997)

Let $𝒢$ be a finite set of single-qubit gates, closed under inverses, that generates a dense subgroup of $S U (2)$ (for example ${H, T, T^{†}}$ ). Then every single-qubit gate can be approximated to precision $ε$ by a product of $O (\log^{c} (1 / ε))$ gates from $𝒢$ , with $c \approx 4$ (improved versions reach $c < 2$ ).

Together, ${H, T, CNOT}$ is a universal set: any quantum computation can be approximated with polylogarithmic overhead.

Not every quantum circuit is powerful

Superposition and entanglement are necessary for a quantum advantage, but not sufficient. The circuits built from $H$ , $S$ and CNOT (the Clifford group) can generate highly entangled states and yet:

Theorem (Gottesman–Knill, 1998)

A circuit that starts in $| 0 \dots 0 ⟩$ , uses only Clifford gates and measures in the computational basis can be simulated by a classical computer in time polynomial in the number of qubits and gates.

The trick is to describe the state not by its $2^{n}$ amplitudes, but by the $n$ Pauli operators that leave it invariant (its stabilizers), which Clifford gates transform into one another. The power of a quantum computer comes from adding non-Clifford gates like $T$ , which are also the most expensive to protect from errors.

Deutsch–Jozsa: the first exponential separation

Suppose a function $f : {0, 1}^{n} \to {0, 1}$ is promised to be either constant or balanced (0 on exactly half the inputs). A deterministic classical algorithm may need $2^{n - 1} + 1$ queries to be sure. The algorithm of Deutsch and Jozsa (1992) needs a single one:

{| 0 ⟩}^{\otimes n} \overset{H^{\otimes n}}{⟶} \frac{1}{\sqrt{2^{n}}} \sum_{x} | x ⟩ \overset{U_{f}}{⟶} \frac{1}{\sqrt{2^{n}}} \sum_{x} (- 1)^{f (x)} | x ⟩ \overset{H^{\otimes n}}{⟶} \dots

The amplitude of $| 0 \dots 0 ⟩$ at the end is $\frac{1}{2^{n}} \sum_{x} (- 1)^{f (x)}$ : it is $\pm 1$ if $f$ is constant and exactly 0 if it is balanced. Measuring all zeros or not answers the question with certainty. A randomized classical algorithm can answer with high probability using only a few queries, so the separation is against deterministic algorithms; but the idea (put the information in the phases and make it interfere) is the template for everything that follows.

Quantum complexity

In 1993 Ethan Bernstein and Umesh Vazirani defined BQP, the class of problems that a quantum computer solves in polynomial time with error probability at most $1 / 3$ . They also proved that

BPP \subseteq BQP \subseteq PSPACE .

The first inclusion says that quantum computers can do everything randomized classical ones can (thanks to Toffoli); the second, that they can be simulated with polynomial memory, by summing over paths. Whether either inclusion is strict is not known: proving $BPP \neq BQP$ would imply $P \neq PSPACE$ , a major open problem. The evidence of quantum power is, for now, algorithms like Shor's for problems that we believe are classically hard.

References

D. Deutsch (1985). “Quantum theory, the Church–Turing principle and the universal quantum computer”. Proceedings of the Royal Society A, 400.
D. Deutsch and R. Jozsa (1992). “Rapid solution of problems by quantum computation”. Proceedings of the Royal Society A, 439.
E. Bernstein and U. Vazirani (1993). “Quantum complexity theory”. STOC (journal version: SIAM J. Computing, 1997).
A. Barenco et al. (1995). “Elementary gates for quantum computation”. Physical Review A, 52(5).
D. Gottesman (1998). “The Heisenberg Representation of Quantum Computers”. arXiv:quant-ph/9807006.
C. M. Dawson and M. A. Nielsen (2006). “The Solovay-Kitaev algorithm”. Quantum Information and Computation, 6(1).

§Gates are unitary matrices

§Two qubits: CNOT

§Universality

§Not every quantum circuit is powerful

§Deutsch–Jozsa: the first exponential separation

§Quantum complexity

§References