QuantumCore

Lesson 22 · 85 min · advanced

Toffoli, Reversible Logic & Universality

Loading progress…

The Toffoli gate CCX∣a,b,c⟩=∣a,b,c⊕ab⟩\mathrm{CCX}\lvert a,b,c\rangle=\lvert a,b,c\oplus ab\rangle computes NAND and FANOUT reversibly, so every classical Boolean circuit can be simulated by a quantum circuit. Toffoli itself decomposes exactly into six CNOTs, seven T/T†T/T^\dagger gates and two Hadamards, which is checked here state by state through the phase bookkeeping ω4abc\omega^{4abc} with ω=eiπ/4\omega=e^{i\pi/4}. Any U∈U(d)U\in U(d) factors into at most d(d−1)/2d(d-1)/2 two-level unitaries, hence into CNOTs and single-qubit gates (exact universality), and the finite set {H,T,CNOT}\{H,T,\mathrm{CNOT}\} approximates any unitary to accuracy ε\varepsilon with O(log⁡c(1/ε))O(\log^c(1/\varepsilon)) gates (Solovay–Kitaev).

Prerequisites: Controlled Gates: CNOT, CZ, SWAP

Objectives and key results

  • Write the 8×88\times8 permutation matrix of CCX\mathrm{CCX}, show CCX2=I\mathrm{CCX}^2=I, and use CCX∣a,b,1⟩=∣a,b,ab‾⟩\mathrm{CCX}\lvert a,b,1\rangle=\lvert a,b,\overline{ab}\rangle and CCX∣a,1,0⟩=∣a,1,a⟩\mathrm{CCX}\lvert a,1,0\rangle=\lvert a,1,a\rangle to obtain NAND and FANOUT.

  • Prove that NAND generates NOT, AND and OR, and conclude that Toffoli is universal for reversible classical computation.

  • Verify the decomposition of CCX\mathrm{CCX} into 66 CNOTs, 77 T/T†T/T^\dagger and 22 HH by computing the phase ωE(a,b,c)\omega^{E(a,b,c)} on all eight basis states and proving E=4abcE=4abc.

  • Prove that every U∈U(d)U\in U(d) is a product of at most d(d−1)/2d(d-1)/2 two-level unitaries, carry out the elimination on a 3×33\times3 example, and turn two-level unitaries into Gray-code-conjugated multi-controlled gates built from CNOTs and single-qubit gates.

  • Derive cos⁡λ2=cos⁡2π8\cos\tfrac\lambda2=\cos^2\tfrac\pi8 for the rotation T⋅HTHT\cdot HTH, prove that λ/π\lambda/\pi is irrational, explain the density argument, and state the Solovay–Kitaev theorem with its O(log⁡c(1/ε))O(\log^c(1/\varepsilon)) length bound.

identity · Toffoli action
CCX∣a,b,c⟩=∣a,b,c⊕ab⟩,CCX∣a,b,1⟩=∣a,b,ab‾⟩,CCX∣a,1,0⟩=∣a,1,a⟩\mathrm{CCX}\lvert a,b,c\rangle=\lvert a,b,c\oplus ab\rangle,\qquad\mathrm{CCX}\lvert a,b,1\rangle=\lvert a,b,\overline{ab}\rangle,\qquad\mathrm{CCX}\lvert a,1,0\rangle=\lvert a,1,a\rangle
algorithm · Clifford+T Toffoli
CCX=(I⊗I⊗H) CCZ (I⊗I⊗H),CCZ∣a,b,c⟩=ω4abc∣a,b,c⟩,ω=eiπ/4\mathrm{CCX}=(I\otimes I\otimes H)\,\mathrm{CCZ}\,(I\otimes I\otimes H),\qquad\mathrm{CCZ}\lvert a,b,c\rangle=\omega^{4abc}\lvert a,b,c\rangle,\quad\omega=e^{i\pi/4}
theorem · Two-level decomposition
U∈U(d) ⇒ U=V1V2⋯Vk,Vj two-level unitary,k≤d(d−1)2U\in U(d)\ \Rightarrow\ U=V_1V_2\cdots V_k,\quad V_j\ \text{two-level unitary},\quad k\le\frac{d(d-1)}{2}
formula · Irrational rotation
T⋅HTH=eiπ/4Rn^(λ),cos⁡λ2=cos⁡2π8,λπ∉QT\cdot HTH=e^{i\pi/4}R_{\hat n}(\lambda),\qquad\cos\frac\lambda2=\cos^2\frac\pi8,\qquad\frac\lambda\pi\notin\mathbb Q
theorem · Solovay–Kitaev
∀ U∈SU(2), ε>0: ∃ W∈⟨G⟩, ∥U−W∥≤ε, ∣W∣=O(log⁡c(1/ε)), c=ln⁡5ln⁡(3/2)≈3.97\forall\,U\in SU(2),\ \varepsilon>0:\ \exists\,W\in\langle\mathcal G\rangle,\ \lVert U-W\rVert\le\varepsilon,\ \lvert W\rvert=O\big(\log^{c}(1/\varepsilon)\big),\ c=\frac{\ln5}{\ln(3/2)}\approx3.97

The Toffoli gate and reversible classical logic#

Definition

Toffoli gate (CCX)

The Toffoli gate or controlled-controlled-NOT is the three-qubit unitary defined on the computational basis by CCX∣a,b,c⟩=∣a,b,c⊕ab⟩\mathrm{CCX}\lvert a,b,c\rangle=\lvert a,b,c\oplus ab\rangle for a,b,c∈{0,1}a,b,c\in\{0,1\}: the target bit cc is flipped exactly when both controls are 11. In block form CCX=(I4−∣11⟩⟨11∣)⊗I+∣11⟩⟨11∣⊗X\mathrm{CCX}=(I_4-\lvert11\rangle\langle11\rvert)\otimes I+\lvert11\rangle\langle11\rvert\otimes X. With qubit 00 as the most significant bit, ∣a,b,c⟩\lvert a,b,c\rangle has index 4a+2b+c4a+2b+c, so CCX\mathrm{CCX} exchanges indices 66 and 77 and fixes the other six.

CCX=(1000000001000000001000000001000000001000000001000000000100000010)=(I600X)\mathrm{CCX}=\begin{pmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\\0&0&0&0&0&0&1&0\end{pmatrix}=\begin{pmatrix}I_6&0\\0&X\end{pmatrix}
Toffoli CCX (8×8 permutation matrix)8×8

Unitary verified: U†U=IU^\dagger U = I (max deviation 0.0e+0)

Derivation

CCX\mathrm{CCX} is a self-inverse permutation

  1. Step 1:
    CCX2∣a,b,c⟩=CCX∣a,b,c⊕ab⟩=∣a,b,c⊕ab⊕ab⟩=∣a,b,c⟩\mathrm{CCX}^2\lvert a,b,c\rangle=\mathrm{CCX}\lvert a,b,c\oplus ab\rangle=\lvert a,b,c\oplus ab\oplus ab\rangle=\lvert a,b,c\rangle
    Apply the definition twice; the controls are unchanged, and ab⊕ab=0ab\oplus ab=0 for every bit value of abab.
  2. Step 2:
    CCX2=I8,CCX†=CCXT=CCX\mathrm{CCX}^2=I_8,\qquad\mathrm{CCX}^\dagger=\mathrm{CCX}^T=\mathrm{CCX}
    A linear map that fixes every basis vector is the identity. The matrix is real and symmetric (it swaps indices 66 and 77), so it equals its adjoint, and with CCX2=I\mathrm{CCX}^2=I it is unitary.
  3. Step 3:
    (a,b,c)↦(a,b,c⊕ab) is a bijection of {0,1}3(a,b,c)\mapsto(a,b,c\oplus ab)\ \text{is a bijection of}\ \{0,1\}^3
    A self-inverse map is invertible. Hence the classical Toffoli function loses no information, unlike AND or NAND on two bits, which map four inputs to two outputs.

Result

CCX=CCX†=CCX−1\boxed{\mathrm{CCX}=\mathrm{CCX}^\dagger=\mathrm{CCX}^{-1}}

Circuit · 3 qubits

Quantum circuit on 3 qubitsX on q0; X on q1; X on q2 controlled by q0, q1q0q1q2XX

XX on qubits 00 and 11 prepares ∣110⟩\lvert110\rangle (index 66); the Toffoli then flips the target because ab=1ab=1, and the statevector panel shows amplitude 11 on ∣111⟩\lvert111\rangle (index 77).

∣ψ⟩=1∣111⟩\lvert\psi\rangle = 1\lvert 111\rangle
Derivation

NAND and FANOUT from one Toffoli

  1. Step 1:
    CCX∣a,b,1⟩=∣a,b,1⊕ab⟩=∣a,b,ab‾⟩\mathrm{CCX}\lvert a,b,1\rangle=\lvert a,b,1\oplus ab\rangle=\lvert a,b,\overline{ab}\rangle
    Set the target to c=1c=1 and use 1⊕y=yˉ1\oplus y=\bar y for a bit yy.
  2. Step 2:
    ab‾=NAND(a,b):(0,0)↦1, (0,1)↦1, (1,0)↦1, (1,1)↦0\overline{ab}=\mathrm{NAND}(a,b):\quad(0,0)\mapsto1,\ (0,1)\mapsto1,\ (1,0)\mapsto1,\ (1,1)\mapsto0
    Evaluate 1⊕ab1\oplus ab on the four inputs: only a=b=1a=b=1 gives ab=1ab=1 and hence output 00.
  3. Step 3:
    CCX∣a,1,0⟩=∣a,1,0⊕a⋅1⟩=∣a,1,a⟩\mathrm{CCX}\lvert a,1,0\rangle=\lvert a,1,0\oplus a\cdot1\rangle=\lvert a,1,a\rangle
    Set the second control to b=1b=1 and the target to c=0c=0: the target receives a copy of the classical bit aa (FANOUT). This copies only basis states; it is not a cloner for superpositions.
  4. Step 4:
    CCX∣1,1,c⟩=∣1,1,cˉ⟩\mathrm{CCX}\lvert1,1,c\rangle=\lvert1,1,\bar c\rangle
    With both controls fixed to 11 the Toffoli is a NOT on the target, so constant ancilla bits turn it into NOT as well.

Result

NAND(a,b)=target of CCX∣a,b,1⟩,FANOUT(a)=CCX∣a,1,0⟩\boxed{\mathrm{NAND}(a,b)=\text{target of }\mathrm{CCX}\lvert a,b,1\rangle,\qquad\mathrm{FANOUT}(a)=\mathrm{CCX}\lvert a,1,0\rangle}
Theorem

NAND is universal for classical Boolean logic

Every Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\} can be computed by a circuit of NAND gates together with FANOUT (copying wires) and the constants 0,10,1. Consequently, with ancilla bits prepared in constant states and extra output (garbage) bits, every classical Boolean circuit can be simulated by a circuit of Toffoli gates acting reversibly on basis states.

Proof (6 steps)
  1. Step 1:
    NAND(a,a)=a⋅a‾=aˉ\mathrm{NAND}(a,a)=\overline{a\cdot a}=\bar a
    Feed one bit into both inputs (this uses FANOUT); since a⋅a=aa\cdot a=a the output is NOT aa.
  2. Step 2:
    AND(a,b)=ab=ab‾‾=NAND(NAND(a,b),NAND(a,b))\mathrm{AND}(a,b)=ab=\overline{\overline{ab}}=\mathrm{NAND}\big(\mathrm{NAND}(a,b),\mathrm{NAND}(a,b)\big)
    Double negation, with the NOT from the previous step applied to NAND(a,b)\mathrm{NAND}(a,b).
  3. Step 3:
    OR(a,b)=a∨b=aˉ bˉ‾=NAND(aˉ,bˉ)=NAND(NAND(a,a),NAND(b,b))\mathrm{OR}(a,b)=a\lor b=\overline{\bar a\,\bar b}=\mathrm{NAND}(\bar a,\bar b)=\mathrm{NAND}\big(\mathrm{NAND}(a,a),\mathrm{NAND}(b,b)\big)
    De Morgan's law a∨b=aˉ∧bˉ‾a\lor b=\overline{\bar a\land\bar b}, checked on the four inputs: (0,0)↦1⋅1‾=0(0,0)\mapsto\overline{1\cdot1}=0, (0,1)↦1⋅0‾=1(0,1)\mapsto\overline{1\cdot0}=1, (1,0)↦1(1,0)\mapsto1, (1,1)↦0⋅0‾=1(1,1)\mapsto\overline{0\cdot0}=1.
  4. Step 4:
    f(x)=⋁y: f(y)=1 ⋀i=1nℓiy(x),ℓiy(x)={xiyi=1xˉiyi=0f(x)=\bigvee_{y:\,f(y)=1}\ \bigwedge_{i=1}^{n}\ell_{i}^{y}(x),\qquad\ell_i^{y}(x)=\begin{cases}x_i&y_i=1\\\bar x_i&y_i=0\end{cases}
    Disjunctive normal form: the inner AND equals 11 exactly when x=yx=y, so the OR over all yy with f(y)=1f(y)=1 equals f(x)f(x) (if no such yy exists, ff is the constant 00). Hence NOT, AND and OR, with copies of the inputs, compute every ff.
  5. Step 5:
    {NOT,AND,OR}⊂⟨NAND,FANOUT⟩ ⇒ f∈⟨NAND,FANOUT⟩\{\mathrm{NOT},\mathrm{AND},\mathrm{OR}\}\subset\langle\mathrm{NAND},\mathrm{FANOUT}\rangle\ \Rightarrow\ f\in\langle\mathrm{NAND},\mathrm{FANOUT}\rangle
    Substitute the three NAND expressions into the DNF circuit.
  6. Step 6:
    ∣x, 1,…,1, 0,…,0⟩ → Toffolis  ∣x, g(x), f(x)⟩\lvert x,\,1,\dots,1,\,0,\dots,0\rangle\ \xrightarrow{\ \text{Toffolis}\ }\ \lvert x,\,g(x),\,f(x)\rangle
    Replace each NAND by CCX∣a,b,1⟩\mathrm{CCX}\lvert a,b,1\rangle and each FANOUT by CCX∣a,1,0⟩\mathrm{CCX}\lvert a,1,0\rangle, each using fresh ancilla bits; the inputs are kept, the intermediate results g(x)g(x) remain as garbage, and every step is a permutation of basis states.

∎

Quick check

Which input makes CCX\mathrm{CCX} copy the bit aa of qubit 00 onto qubit 22?

Select one answer

Toffoli from H, T, T† and CNOT#

The Toffoli gate is not a native gate on most hardware, but it can be built exactly from the Clifford+TT set {H,T,T†,CNOT}\{H,T,T^\dagger,\mathrm{CNOT}\} with T=diag(1,ω)T=\mathrm{diag}(1,\omega), T†=diag(1,ω−1)T^\dagger=\mathrm{diag}(1,\omega^{-1}) and ω=eiπ/4\omega=e^{i\pi/4}. The construction has two ingredients: a Hadamard on the target turns CCX\mathrm{CCX} into the diagonal gate CCZ\mathrm{CCZ}, and a diagonal gate is built by placing TT and T†T^\dagger on wires that carry suitable parities of the input bits. On a basis state ∣p⟩\lvert p\rangle of one wire, T∣p⟩=ωp∣p⟩T\lvert p\rangle=\omega^{p}\lvert p\rangle and T†∣p⟩=ω−p∣p⟩T^\dagger\lvert p\rangle=\omega^{-p}\lvert p\rangle, and a CNOT maps ∣u,v⟩↦∣u,u⊕v⟩\lvert u,v\rangle\mapsto\lvert u,u\oplus v\rangle, so every gate of the middle part sends basis states to basis states times a power of ω\omega.

Derivation

CCX=(I⊗I⊗H) CCZ (I⊗I⊗H)\mathrm{CCX}=(I\otimes I\otimes H)\,\mathrm{CCZ}\,(I\otimes I\otimes H)

  1. Step 1:
    CCZ=(I4−∣11⟩⟨11∣)⊗I+∣11⟩⟨11∣⊗Z=diag(1,1,1,1,1,1,1,−1)\mathrm{CCZ}=(I_4-\lvert11\rangle\langle11\rvert)\otimes I+\lvert11\rangle\langle11\rvert\otimes Z=\mathrm{diag}(1,1,1,1,1,1,1,-1)
    The controlled-controlled-ZZ applies ZZ to the target exactly when a=b=1a=b=1; on ∣a,b,c⟩\lvert a,b,c\rangle it multiplies by (−1)abc(-1)^{abc}.
  2. Step 2:
    (I⊗I⊗H) CCZ (I⊗I⊗H)=(I4−∣11⟩⟨11∣)⊗H2+∣11⟩⟨11∣⊗HZH(I\otimes I\otimes H)\,\mathrm{CCZ}\,(I\otimes I\otimes H)=(I_4-\lvert11\rangle\langle11\rvert)\otimes H^2+\lvert11\rangle\langle11\rvert\otimes HZH
    Each term has the form P⊗BP\otimes B with PP a projector on the controls; the mixed-product rule gives (I4⊗H)(P⊗B)(I4⊗H)=P⊗HBH(I_4\otimes H)(P\otimes B)(I_4\otimes H)=P\otimes HBH.
  3. Step 3:
    =(I4−∣11⟩⟨11∣)⊗I+∣11⟩⟨11∣⊗X=CCX=(I_4-\lvert11\rangle\langle11\rvert)\otimes I+\lvert11\rangle\langle11\rvert\otimes X=\mathrm{CCX}
    H2=IH^2=I and HZH=XHZH=X (Lesson on Hadamard and phase gates).
  4. Step 4:
    (−1)abc=ω4abc(-1)^{abc}=\omega^{4abc}
    ω4=eiπ=−1\omega^4=e^{i\pi}=-1, so the CCZ phase is ω\omega raised to 4abc∈{0,4}4abc\in\{0,4\}.

Result

CCX=(I⊗I⊗H) CCZ (I⊗I⊗H),CCZ∣a,b,c⟩=ω4abc∣a,b,c⟩\boxed{\mathrm{CCX}=(I\otimes I\otimes H)\,\mathrm{CCZ}\,(I\otimes I\otimes H),\qquad\mathrm{CCZ}\lvert a,b,c\rangle=\omega^{4abc}\lvert a,b,c\rangle}
CCZ=diag(1,1,1,1,1,1,1,−1)=(I700−1)\mathrm{CCZ}=\mathrm{diag}(1,1,1,1,1,1,1,-1)=\begin{pmatrix}I_7&0\\0&-1\end{pmatrix}
CCZ = diag(1,1,1,1,1,1,1,−1)8×8

Unitary verified: U†U=IU^\dagger U = I (max deviation 0.0e+0)

Circuit · 3 qubits

Quantum circuit on 3 qubitsH on q2; X on q2 controlled by q1; Tdg on q2; X on q2 controlled by q0; T on q2; X on q2 controlled by q1; Tdg on q2; X on q2 controlled by q0; T on q1; T on q2; H on q2; X on q1 controlled by q0; T on q0; Tdg on q1; X on q1 controlled by q0q0q1q2HT†TT†TTHTT†

The decomposition H(2); CNOT(1,2); T†(2); CNOT(0,2); T(2); CNOT(1,2); T†(2); CNOT(0,2); T(1); T(2); H(2); CNOT(0,1); T(0); T†(1); CNOT(0,1)H(2);\ \mathrm{CNOT}(1,2);\ T^\dagger(2);\ \mathrm{CNOT}(0,2);\ T(2);\ \mathrm{CNOT}(1,2);\ T^\dagger(2);\ \mathrm{CNOT}(0,2);\ T(1);\ T(2);\ H(2);\ \mathrm{CNOT}(0,1);\ T(0);\ T^\dagger(1);\ \mathrm{CNOT}(0,1) with 66 CNOTs, 77 T/T†T/T^\dagger and 22 HH. The unitary panel shows the 8×88\times8 permutation matrix of CCX\mathrm{CCX} exactly, with no global phase.

U=(1000000001000000001000000001000000001000000001000000000100000010)U = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}
Derivation

Wire contents and phases of the diagonal part

  1. Step 1:
    ∣a,b,c⟩→CNOT(1,2)∣a,b,b⊕c⟩→T†(2)ω−(b⊕c)∣a,b,b⊕c⟩\lvert a,b,c\rangle\xrightarrow{\mathrm{CNOT}(1,2)}\lvert a,b,b\oplus c\rangle\xrightarrow{T^\dagger(2)}\omega^{-(b\oplus c)}\lvert a,b,b\oplus c\rangle
    The CNOT adds the control bit bb to the target; the T†T^\dagger then contributes ω−p\omega^{-p} with p=b⊕cp=b\oplus c the current target bit.
  2. Step 2:
    →CNOT(0,2)∣a,b,a⊕b⊕c⟩→T(2)ω+(a⊕b⊕c)\xrightarrow{\mathrm{CNOT}(0,2)}\lvert a,b,a\oplus b\oplus c\rangle\xrightarrow{T(2)}\omega^{+(a\oplus b\oplus c)}
    The target accumulates aa; the TT contributes ω+(a⊕b⊕c)\omega^{+(a\oplus b\oplus c)} (only the new factor is written).
  3. Step 3:
    →CNOT(1,2)∣a,b,a⊕c⟩→T†(2)ω−(a⊕c)\xrightarrow{\mathrm{CNOT}(1,2)}\lvert a,b,a\oplus c\rangle\xrightarrow{T^\dagger(2)}\omega^{-(a\oplus c)}
    Adding bb a second time cancels it, since b⊕b=0b\oplus b=0.
  4. Step 4:
    →CNOT(0,2)∣a,b,c⟩→T(1) T(2)ω+b ω+c\xrightarrow{\mathrm{CNOT}(0,2)}\lvert a,b,c\rangle\xrightarrow{T(1)\,T(2)}\omega^{+b}\,\omega^{+c}
    Adding aa again restores the target bit cc; TT on qubit 11 and on qubit 22 contribute ωb\omega^{b} and ωc\omega^{c}.
  5. Step 5:
    →CNOT(0,1)∣a,a⊕b,c⟩→T(0) T†(1)ω+a ω−(a⊕b)→CNOT(0,1)∣a,b,c⟩\xrightarrow{\mathrm{CNOT}(0,1)}\lvert a,a\oplus b,c\rangle\xrightarrow{T(0)\,T^\dagger(1)}\omega^{+a}\,\omega^{-(a\oplus b)}\xrightarrow{\mathrm{CNOT}(0,1)}\lvert a,b,c\rangle
    These four gates act on the controls only and therefore commute with H(2)H(2), so they can be placed after it. The middle qubit carries a⊕ba\oplus b while T†T^\dagger acts, and the last CNOT restores bb.
  6. Step 6:
    E(a,b,c)=−(b⊕c)+(a⊕b⊕c)−(a⊕c)+b+c+a−(a⊕b)E(a,b,c)=-(b\oplus c)+(a\oplus b\oplus c)-(a\oplus c)+b+c+a-(a\oplus b)
    Every basis state returns to itself, so the diagonal part multiplies ∣a,b,c⟩\lvert a,b,c\rangle by ωE(a,b,c)\omega^{E(a,b,c)} with EE the sum of the seven exponents.

Result

D∣a,b,c⟩=ωE(a,b,c)∣a,b,c⟩\boxed{D\lvert a,b,c\rangle=\omega^{E(a,b,c)}\lvert a,b,c\rangle}

The seven exponents for each of the eight basis states (columns in circuit order, ω=eiπ/4\omega=e^{i\pi/4}):

∣a,b,c⟩\lvert a,b,c\rangle−(b⊕c)-(b\oplus c)+(a⊕b⊕c)+(a\oplus b\oplus c)−(a⊕c)-(a\oplus c)+b+b+c+c+a+a−(a⊕b)-(a\oplus b)EEωE\omega^{E}
∣000⟩\lvert 000\rangle000000000000000011
∣001⟩\lvert 001\rangle−1-1+1+1−1-100+1+100000011
∣010⟩\lvert 010\rangle−1-1+1+100+1+10000−1-10011
∣011⟩\lvert 011\rangle0000−1-1+1+1+1+100−1-10011
∣100⟩\lvert 100\rangle00+1+1−1-10000+1+1−1-10011
∣101⟩\lvert 101\rangle−1-1000000+1+1+1+1−1-10011
∣110⟩\lvert 110\rangle−1-100−1-1+1+100+1+1000011
∣111⟩\lvert 111\rangle00+1+100+1+1+1+1+1+10044−1-1

Seven rows sum to E=0E=0 and only ∣111⟩\lvert111\rangle gives E=4E=4, i.e. the phase ω4=−1\omega^4=-1: the diagonal part is exactly CCZ\mathrm{CCZ}.

Lemma

The T-count phase identity

For all bits a,b,c∈{0,1}a,b,c\in\{0,1\}, E(a,b,c)=−(b⊕c)+(a⊕b⊕c)−(a⊕c)+a+b+c−(a⊕b)=4abcE(a,b,c)=-(b\oplus c)+(a\oplus b\oplus c)-(a\oplus c)+a+b+c-(a\oplus b)=4abc. Hence the diagonal part implements ω4abc=(−1)abc\omega^{4abc}=(-1)^{abc}, which is CCZ\mathrm{CCZ}, and the full circuit with the two H(2)H(2) gates equals CCX\mathrm{CCX} exactly.

Proof (6 steps)
  1. Step 1:
    x⊕y=x+y−2xy(x,y∈{0,1})x\oplus y=x+y-2xy\qquad(x,y\in\{0,1\})
    Check the four cases: 0+0−0=00+0-0=0, 0+1−0=10+1-0=1, 1+0−0=11+0-0=1, 1+1−2=01+1-2=0.
  2. Step 2:
    a⊕b⊕c=(a+b−2ab)+c−2(a+b−2ab)c=a+b+c−2ab−2bc−2ac+4abca\oplus b\oplus c=(a+b-2ab)+c-2(a+b-2ab)c=a+b+c-2ab-2bc-2ac+4abc
    Apply the identity twice, first with (x,y)=(a,b)(x,y)=(a,b) and then with x=a⊕bx=a\oplus b, y=cy=c.
  3. Step 3:
    E=−(b+c−2bc)+(a+b+c−2ab−2bc−2ac+4abc)−(a+c−2ac)+a+b+c−(a+b−2ab)E=-(b+c-2bc)+(a+b+c-2ab-2bc-2ac+4abc)-(a+c-2ac)+a+b+c-(a+b-2ab)
    Substitute the arithmetic forms of the four parities.
  4. Step 4:
    =a (1−1+1−1)+b (−1+1+1−1)+c (−1+1−1+1)+bc (2−2)+ab (−2+2)+ac (−2+2)+4abc=a\,(1-1+1-1)+b\,(-1+1+1-1)+c\,(-1+1-1+1)+bc\,(2-2)+ab\,(-2+2)+ac\,(-2+2)+4abc
    Collect the coefficients of each monomial.
  5. Step 5:
    =4abc=4abc
    Every linear and quadratic coefficient vanishes.
  6. Step 6:
    D=∑a,b,cω4abc∣a,b,c⟩⟨a,b,c∣=CCZ ⇒ (I⊗I⊗H) D (I⊗I⊗H)=CCXD=\textstyle\sum_{a,b,c}\omega^{4abc}\lvert a,b,c\rangle\langle a,b,c\rvert=\mathrm{CCZ}\ \Rightarrow\ (I\otimes I\otimes H)\,D\,(I\otimes I\otimes H)=\mathrm{CCX}
    ω4abc=(−1)abc\omega^{4abc}=(-1)^{abc}, and the conjugation identity derived above turns CCZ\mathrm{CCZ} into CCX\mathrm{CCX}.

∎

Quick check

How many TT and T†T^\dagger gates (together) does the decomposition use?

tolerance ±0.5

Quick check

If the two H(2)H(2) gates are removed, what is the process fidelity FU=∣Tr(CCX†U)∣/8F_U=\lvert\mathrm{Tr}(\mathrm{CCX}^\dagger U)\rvert/8 of the remaining circuit with CCX\mathrm{CCX}?

tolerance ±0.005

Exact universality: two-level unitaries#

Definition

Two-level unitary

A unitary V∈U(d)V\in U(d) is two-level if there are indices j<kj<k such that VV acts non-trivially only on span{∣j⟩,∣k⟩}\mathrm{span}\{\lvert j\rangle,\lvert k\rangle\}: V∣l⟩=∣l⟩V\lvert l\rangle=\lvert l\rangle for all l∉{j,k}l\notin\{j,k\} and VV maps span{∣j⟩,∣k⟩}\mathrm{span}\{\lvert j\rangle,\lvert k\rangle\} to itself by a 2×22\times2 unitary V~\tilde V. The adjoint and the identity are two-level, and a two-level unitary of U(d−1)U(d-1) embedded as 1⊕V1\oplus V is two-level in U(d)U(d).

Theorem

Decomposition into two-level unitaries

Every U∈U(d)U\in U(d) with d≥2d\ge2 is a product U=V1V2⋯VkU=V_1V_2\cdots V_k of two-level unitaries with k≤d(d−1)/2k\le d(d-1)/2.

Proof (9 steps)
  1. Step 1:
    W=1s(uˉjuˉkuk−uj) on span{∣j⟩,∣k⟩},s=∣uj∣2+∣uk∣2>0W=\frac1s\begin{pmatrix}\bar u_j&\bar u_k\\u_k&-u_j\end{pmatrix}\ \text{on}\ \mathrm{span}\{\lvert j\rangle,\lvert k\rangle\},\qquad s=\sqrt{\lvert u_j\rvert^2+\lvert u_k\rvert^2}>0
    Elimination step. Given two entries uj,uku_j,u_k (with j<kj<k) of a column, define WW as this 2×22\times2 block on the pair and as the identity on all other basis vectors. If s=0s=0 take W=IW=I.
  2. Step 2:
    W~W~†=1s2(uˉjuˉkuk−uj)(ujuˉkuk−uˉj)=1s2(∣uj∣2+∣uk∣2uˉjuˉk−uˉkuˉjukuj−ujuk∣uk∣2+∣uj∣2)=I2\tilde W\tilde W^\dagger=\frac1{s^2}\begin{pmatrix}\bar u_j&\bar u_k\\u_k&-u_j\end{pmatrix}\begin{pmatrix}u_j&\bar u_k\\u_k&-\bar u_j\end{pmatrix}=\frac1{s^2}\begin{pmatrix}\lvert u_j\rvert^2+\lvert u_k\rvert^2&\bar u_j\bar u_k-\bar u_k\bar u_j\\u_ku_j-u_ju_k&\lvert u_k\rvert^2+\lvert u_j\rvert^2\end{pmatrix}=I_2
    Multiply W~\tilde W by its conjugate transpose entry by entry; the off-diagonal entries cancel and the diagonal entries equal s2/s2=1s^2/s^2=1. So WW is a two-level unitary.
  3. Step 3:
    W~(ujuk)=1s(uˉjuj+uˉkukukuj−ujuk)=(s0)\tilde W\begin{pmatrix}u_j\\u_k\end{pmatrix}=\frac1s\begin{pmatrix}\bar u_ju_j+\bar u_ku_k\\u_ku_j-u_ju_k\end{pmatrix}=\begin{pmatrix}s\\0\end{pmatrix}
    WW zeros the entry kk, puts the real number s≥0s\ge0 in position jj, and leaves every other entry of the column unchanged.
  4. Step 4:
    Wd−1⋯W2W1 U∣0⟩=(r,0,…,0)T,r≥0W_{d-1}\cdots W_2W_1\,U\lvert0\rangle=(r,0,\dots,0)^T,\qquad r\ge0
    Apply the step to column 00 with the pairs (0,1),(0,2),…,(0,d−1)(0,1),(0,2),\dots,(0,d-1) in this order. WkW_k touches only rows 00 and kk, so the entries already zeroed (rows 1,…,k−11,\dots,k-1) stay zero, and after the last step entry 00 is real and non-negative (it is ss, or 00 if all remaining entries were 00).
  5. Step 5:
    ∥Wd−1⋯W1U∣0⟩∥=1 ⇒ r=1\lVert W_{d-1}\cdots W_1U\lvert0\rangle\rVert=1\ \Rightarrow\ r=1
    A product of unitaries is unitary, so its columns have norm 11; the only non-zero entry is r≥0r\ge0, hence r=1r=1.
  6. Step 6:
    (1,x1,…,xd−1) row 0,1+∑i∣xi∣2=1 ⇒ xi=0 ⇒ Wd−1⋯W1U=(100U′), U′∈U(d−1)(1,x_1,\dots,x_{d-1})\ \text{row }0,\quad1+\textstyle\sum_i\lvert x_i\rvert^2=1\ \Rightarrow\ x_i=0\ \Rightarrow\ W_{d-1}\cdots W_1U=\begin{pmatrix}1&0\\0&U'\end{pmatrix},\ U'\in U(d-1)
    The rows of a unitary also have norm 11; row 00 starts with the entry 11, so the rest of the row vanishes. The remaining block U′U' is unitary because the whole matrix is.
  7. Step 7:
    WN⋯W1U=Id−2⊕V~,V~∈U(2),N=(d−1)+(d−2)+⋯+2W_N\cdots W_1U=I_{d-2}\oplus\tilde V,\qquad\tilde V\in U(2),\qquad N=(d-1)+(d-2)+\cdots+2
    Repeat on U′U' with columns 1,2,…,d−31,2,\dots,d-3; each step uses pairs inside the indices 1,…,d−11,\dots,d-1, so the WW's remain two-level in U(d)U(d), and column jj needs d−1−jd-1-j factors. The process stops when a 2×22\times2 block on indices d−2,d−1d-2,d-1 remains (for d=2d=2 take N=0N=0 and V~=U\tilde V=U).
  8. Step 8:
    U=W1†W2†⋯WN† (Id−2⊕V~)U=W_1^\dagger W_2^\dagger\cdots W_N^\dagger\,(I_{d-2}\oplus\tilde V)
    Multiply by W1†⋯WN†W_1^\dagger\cdots W_N^\dagger on the left; each Wi†W_i^\dagger is two-level, and so is Id−2⊕V~I_{d-2}\oplus\tilde V.
  9. Step 9:
    k=N+1=∑m=2d−1m+1=∑m=1d−1m=d(d−1)2k=N+1=\sum_{m=2}^{d-1}m+1=\sum_{m=1}^{d-1}m=\frac{d(d-1)}2
    Count the factors; factors equal to II can be dropped, which only lowers the count, so k≤d(d−1)/2k\le d(d-1)/2.

∎

Derivation

Worked example in U(3)U(3)

  1. Step 1:
    U=13(12221−22−21),UTU=19(900090009)=IU=\frac13\begin{pmatrix}1&2&2\\2&1&-2\\2&-2&1\end{pmatrix},\qquad U^TU=\frac19\begin{pmatrix}9&0&0\\0&9&0\\0&0&9\end{pmatrix}=I
    A real orthogonal (hence unitary) matrix: e.g. column 00 dotted with column 11 gives (2+2−4)/9=0(2+2-4)/9=0 and each column has squared norm (1+4+4)/9=1(1+4+4)/9=1.
  2. Step 2:
    u0=13, u1=23, s=19+49=53 ⇒ W1=15(1202−10005)u_0=\tfrac13,\ u_1=\tfrac23,\ s=\sqrt{\tfrac19+\tfrac49}=\tfrac{\sqrt5}3\ \Rightarrow\ W_1=\frac1{\sqrt5}\begin{pmatrix}1&2&0\\2&-1&0\\0&0&\sqrt5\end{pmatrix}
    First elimination step on the pair (0,1)(0,1) of column 00: W~1=35(1/32/32/3−1/3)=15(122−1)\tilde W_1=\tfrac3{\sqrt5}\begin{pmatrix}1/3&2/3\\2/3&-1/3\end{pmatrix}=\tfrac1{\sqrt5}\begin{pmatrix}1&2\\2&-1\end{pmatrix} (all entries real, so conjugation does nothing).
  3. Step 3:
    W1U=(535435−2350152523−2313)W_1U=\begin{pmatrix}\frac5{3\sqrt5}&\frac4{3\sqrt5}&-\frac2{3\sqrt5}\\0&\frac1{\sqrt5}&\frac2{\sqrt5}\\\frac23&-\frac23&\frac13\end{pmatrix}
    Row 00 is 15(row0+2 row1)=135(5,4,−2)\tfrac1{\sqrt5}(\text{row}_0+2\,\text{row}_1)=\tfrac1{3\sqrt5}(5,4,-2), row 11 is 15(2 row0−row1)=135(0,3,6)\tfrac1{\sqrt5}(2\,\text{row}_0-\text{row}_1)=\tfrac1{3\sqrt5}(0,3,6), and row 22 is unchanged.
  4. Step 4:
    u0=535=53, u2=23, s=59+49=1 ⇒ W2=(53023010230−53)u_0=\tfrac{5}{3\sqrt5}=\tfrac{\sqrt5}3,\ u_2=\tfrac23,\ s=\sqrt{\tfrac59+\tfrac49}=1\ \Rightarrow\ W_2=\begin{pmatrix}\frac{\sqrt5}3&0&\frac23\\0&1&0\\\frac23&0&-\frac{\sqrt5}3\end{pmatrix}
    Second step on the pair (0,2)(0,2) of column 00; s=1s=1 as it must be for the last step of a unit column.
  5. Step 5:
    W2W1U=(10001525025−15)=1⊕V~,V~=15(122−1)W_2W_1U=\begin{pmatrix}1&0&0\\0&\frac1{\sqrt5}&\frac2{\sqrt5}\\0&\frac2{\sqrt5}&-\frac1{\sqrt5}\end{pmatrix}=1\oplus\tilde V,\qquad\tilde V=\frac1{\sqrt5}\begin{pmatrix}1&2\\2&-1\end{pmatrix}
    Row 00: 53⋅135(5,4,−2)+23⋅13(2,−2,1)=19(5,4,−2)+19(4,−4,2)=(1,0,0)\tfrac{\sqrt5}3\cdot\tfrac1{3\sqrt5}(5,4,-2)+\tfrac23\cdot\tfrac13(2,-2,1)=\tfrac19(5,4,-2)+\tfrac19(4,-4,2)=(1,0,0). Row 22: 23⋅135(5,4,−2)−53⋅13(2,−2,1)=195((10,8,−4)−(10,−10,5))=15(0,2,−1)\tfrac23\cdot\tfrac1{3\sqrt5}(5,4,-2)-\tfrac{\sqrt5}3\cdot\tfrac13(2,-2,1)=\tfrac1{9\sqrt5}\big((10,8,-4)-(10,-10,5)\big)=\tfrac1{\sqrt5}(0,2,-1). Row 00 is (1,0,0)(1,0,0) exactly as the proof predicts.
  6. Step 6:
    U=W1†W2†W3=W1W2W3,W3=1⊕V~U=W_1^\dagger W_2^\dagger W_3=W_1W_2W_3,\qquad W_3=1\oplus\tilde V
    W1W_1 and W2W_2 are real symmetric, so Wi†=WiW_i^\dagger=W_i. Three factors, which equals d(d−1)/2=3d(d-1)/2=3 for d=3d=3.

Result

13(12221−22−21)=15(1202−10005)(53023010230−53)15(50001202−1)\boxed{\frac13\begin{pmatrix}1&2&2\\2&1&-2\\2&-2&1\end{pmatrix}=\frac1{\sqrt5}\begin{pmatrix}1&2&0\\2&-1&0\\0&0&\sqrt5\end{pmatrix}\begin{pmatrix}\frac{\sqrt5}3&0&\frac23\\0&1&0\\\frac23&0&-\frac{\sqrt5}3\end{pmatrix}\frac1{\sqrt5}\begin{pmatrix}\sqrt5&0&0\\0&1&2\\0&2&-1\end{pmatrix}}
U=13(12221−22−21)U=\frac13\begin{pmatrix}1&2&2\\2&1&-2\\2&-2&1\end{pmatrix}
Worked example U ∈ U(3)3×3

Unitary verified: U†U=IU^\dagger U = I (max deviation 0.0e+0)

Derivation

A two-level unitary as a Gray-code-conjugated multi-controlled gate

  1. Step 1:
    U~ acts on ∣s⟩,∣t⟩,s=g1,g2,…,gm=t,gi and gi+1 differ in one bit,m≤n+1\tilde U\ \text{acts on}\ \lvert s\rangle,\lvert t\rangle,\qquad s=g_1,g_2,\dots,g_m=t,\quad g_i\ \text{and}\ g_{i+1}\ \text{differ in one bit},\quad m\le n+1
    On nn qubits (d=2nd=2^n) the two basis strings s,ts,t differ in at most nn bits; flipping the differing bits one at a time gives a Gray code from ss to tt.
  2. Step 2:
    Pi: ∣gi⟩↔∣gi+1⟩ for i=1,…,m−2P_i:\ \lvert g_i\rangle\leftrightarrow\lvert g_{i+1}\rangle\ \text{for}\ i=1,\dots,m-2
    PiP_i flips the single bit where gig_i and gi+1g_{i+1} differ, controlled on the other n−1n-1 bits taking the common values of gi,gi+1g_i,g_{i+1} (a 00-control is an ordinary control conjugated by XX). It is an (n−1)(n-1)-controlled NOT that swaps exactly these two basis states and fixes all others.
  3. Step 3:
    Pm−2⋯P1∣s⟩=∣gm−1⟩,Pm−2⋯P1∣t⟩=∣t⟩P_{m-2}\cdots P_1\lvert s\rangle=\lvert g_{m-1}\rangle,\qquad P_{m-2}\cdots P_1\lvert t\rangle=\lvert t\rangle
    The swaps move the amplitude of ∣s⟩\lvert s\rangle along the code to ∣gm−1⟩\lvert g_{m-1}\rangle, a neighbour of tt; t=gmt=g_m is never touched by P1,…,Pm−2P_1,\dots,P_{m-2}.
  4. Step 4:
    Cn−1(U~) on the bit where gm−1,gm differC^{n-1}(\tilde U)\ \text{on the bit where}\ g_{m-1},g_m\ \text{differ}
    Apply U~\tilde U to that bit, controlled on the other n−1n-1 bits equal to their common values, with the basis order chosen so that the row/column of ∣s⟩\lvert s\rangle of U~\tilde U corresponds to ∣gm−1⟩\lvert g_{m-1}\rangle.
  5. Step 5:
    V=P1†⋯Pm−2†  Cn−1(U~)  Pm−2⋯P1V=P_1^\dagger\cdots P_{m-2}^\dagger\;C^{n-1}(\tilde U)\;P_{m-2}\cdots P_1
    Undo the swaps. The result acts as U~\tilde U on {∣s⟩,∣t⟩}\{\lvert s\rangle,\lvert t\rangle\} and as the identity elsewhere. It uses 2(m−2)≤2(n−1)2(m-2)\le2(n-1) multi-controlled NOTs and one multi-controlled single-qubit gate.
  6. Step 6:
    n=3, s=000, t=111:000→001→011→111n=3,\ s=000,\ t=111:\quad000\to001\to011\to111
    Example: P1P_1 flips qubit 22 when q0q1=00q_0q_1=00, P2P_2 flips qubit 11 when q0=0,q2=1q_0=0,q_2=1, then U~\tilde U acts on qubit 00 controlled by q1=q2=1q_1=q_2=1, followed by P2P_2 and P1P_1 again.

Result

V=(∏iPi)† Cn−1(U~) ∏iPi\boxed{V=\Big(\prod_{i}P_i\Big)^{\dagger}\,C^{n-1}(\tilde U)\,\prod_{i}P_i}
Derivation

Multi-controlled gates from CNOTs and single-qubit gates

  1. Step 1:
    V2=U,C2(U)=C0,2(V)  CNOT0,1  C1,2(V†)  CNOT0,1  C1,2(V)V^2=U,\qquad C^2(U)=C_{0,2}(V)\;\mathrm{CNOT}_{0,1}\;C_{1,2}(V^\dagger)\;\mathrm{CNOT}_{0,1}\;C_{1,2}(V)
    Choose a square root VV of UU (diagonalise U=∑eiθj∣ej⟩⟨ej∣U=\sum e^{i\theta_j}\lvert e_j\rangle\langle e_j\rvert and take V=∑eiθj/2∣ej⟩⟨ej∣V=\sum e^{i\theta_j/2}\lvert e_j\rangle\langle e_j\rvert). The product is written right to left: the circuit applies C1,2(V)C_{1,2}(V) first.
  2. Step 2:
    ∣a,b⟩∣ψ⟩↦∣a,b⟩ Va V−(a⊕b) Vb∣ψ⟩\lvert a,b\rangle\lvert\psi\rangle\mapsto\lvert a,b\rangle\,V^{a}\,V^{-(a\oplus b)}\,V^{b}\lvert\psi\rangle
    C1,2(V)C_{1,2}(V) applies VbV^{b}; the CNOT puts a⊕ba\oplus b on qubit 11, so C1,2(V†)C_{1,2}(V^\dagger) applies V−(a⊕b)V^{-(a\oplus b)}; the second CNOT restores bb; C0,2(V)C_{0,2}(V) applies VaV^{a}. Powers of one matrix commute.
  3. Step 3:
    a+b−(a⊕b)=a+b−(a+b−2ab)=2ab ⇒ V2ab=Uaba+b-(a\oplus b)=a+b-(a+b-2ab)=2ab\ \Rightarrow\ V^{2ab}=U^{ab}
    Use x⊕y=x+y−2xyx\oplus y=x+y-2xy. The target receives UU exactly when a=b=1a=b=1: this is C2(U)C^2(U).
  4. Step 4:
    C(V)=(∣0⟩⟨0∣⊗I+∣1⟩⟨1∣⊗eiαI) (I⊗A) CNOT (I⊗B) CNOT (I⊗C)C(V)=(\lvert0\rangle\langle0\rvert\otimes I+\lvert1\rangle\langle1\rvert\otimes e^{i\alpha}I)\,(I\otimes A)\,\mathrm{CNOT}\,(I\otimes B)\,\mathrm{CNOT}\,(I\otimes C)
    The ABCABC construction of the controlled-gates lesson: V=eiαAXBXCV=e^{i\alpha}AXBXC with ABC=IABC=I, so each controlled single-qubit gate costs 22 CNOTs, three single-qubit gates and a phase gate on the control.
  5. Step 5:
    Cn(U): compute c1∧⋯∧cn into n−1 ancillas with n−1 Toffolis, apply C(U), uncomputeC^n(U):\ \text{compute}\ c_1\land\cdots\land c_n\ \text{into}\ n-1\ \text{ancillas with}\ n-1\ \text{Toffolis},\ \text{apply}\ C(U),\ \text{uncompute}
    The ancilla r1=c1c2r_1=c_1c_2, r2=r1c3r_2=r_1c_3, …\dots, rn−1=rn−2cnr_{n-1}=r_{n-2}c_n (each a Toffoli onto a ∣0⟩\lvert0\rangle ancilla) holds the AND of all controls; C(U)C(U) controlled by rn−1r_{n-1} acts exactly when all ci=1c_i=1; running the Toffolis in reverse returns the ancillas to ∣0⟩\lvert0\rangle. In total 2(n−1)2(n-1) Toffolis, each 66 CNOTs, plus one C(U)C(U).
  6. Step 6:
    U∈U(2n) ⇒ U=∏j=1kVj, k≤2n−1(2n−1), Vj∈⟨CNOT, U(2)⟩U\in U(2^n)\ \Rightarrow\ U=\prod_{j=1}^{k}V_j,\ k\le2^{n-1}(2^n-1),\ V_j\in\langle\mathrm{CNOT},\ U(2)\rangle
    Combine the three constructions: two-level factors, Gray-code conjugation and multi-controlled gates. Hence {CNOT}∪U(2)\{\mathrm{CNOT}\}\cup U(2) is exactly universal, with O(n24n)O(n^24^n) gates for a generic UU.

Result

CNOT and single-qubit gates are exactly universal for U(2n)\boxed{\text{CNOT and single-qubit gates are exactly universal for }U(2^n)}

Quick check

What is the upper bound d(d−1)/2d(d-1)/2 on the number of two-level factors for a three-qubit unitary (d=8d=8)?

tolerance ±0.5

Approximate universality and Solovay–Kitaev#

Definition

Approximation error

For unitaries U,VU,V on the same space the approximation error is the operator-norm distance E(U,V)=max⁡∥ψ∥=1∥(U−V)∣ψ⟩∥E(U,V)=\max_{\lVert\psi\rVert=1}\lVert(U-V)\lvert\psi\rangle\rVert. A gate set G\mathcal G is approximately universal if for every unitary UU and every ε>0\varepsilon>0 there is a finite product WW of gates from G\mathcal G with E(U,eiγW)≤εE(U,e^{i\gamma}W)\le\varepsilon for some global phase γ\gamma. The errors of a circuit add up: E(Um⋯U1,Vm⋯V1)≤∑jE(Uj,Vj)E(U_m\cdots U_1,V_m\cdots V_1)\le\sum_jE(U_j,V_j), by the telescoping sum U2U1−V2V1=U2(U1−V1)+(U2−V2)V1U_2U_1-V_2V_1=U_2(U_1-V_1)+(U_2-V_2)V_1 and ∥U∥=∥V∥=1\lVert U\rVert=\lVert V\rVert=1.

Derivation

T⋅HTHT\cdot HTH is a rotation by λ\lambda with cos⁡λ2=cos⁡2π8\cos\tfrac\lambda2=\cos^2\tfrac\pi8

  1. Step 1:
    T=(100eiπ/4)=eiπ/8(e−iπ/800eiπ/8)=eiπ/8RZ(π4)T=\begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}=e^{i\pi/8}\begin{pmatrix}e^{-i\pi/8}&0\\0&e^{i\pi/8}\end{pmatrix}=e^{i\pi/8}R_Z(\tfrac\pi4)
    Factor out eiπ/8e^{i\pi/8}; RZ(θ)=diag(e−iθ/2,eiθ/2)R_Z(\theta)=\mathrm{diag}(e^{-i\theta/2},e^{i\theta/2}) with θ=π/4\theta=\pi/4.
  2. Step 2:
    HTH=eiπ/8HRZ(π4)H=eiπ/8H(cos⁡π8I−isin⁡π8Z)H=eiπ/8(cos⁡π8I−isin⁡π8X)=eiπ/8RX(π4)HTH=e^{i\pi/8}HR_Z(\tfrac\pi4)H=e^{i\pi/8}H\big(\cos\tfrac\pi8I-i\sin\tfrac\pi8Z\big)H=e^{i\pi/8}\big(\cos\tfrac\pi8I-i\sin\tfrac\pi8X\big)=e^{i\pi/8}R_X(\tfrac\pi4)
    RZ(θ)=cos⁡θ2I−isin⁡θ2ZR_Z(\theta)=\cos\tfrac\theta2I-i\sin\tfrac\theta2Z, H2=IH^2=I and HZH=XHZH=X.
  3. Step 3:
    T⋅HTH=eiπ/4(cos⁡π8I−isin⁡π8Z)(cos⁡π8I−isin⁡π8X)T\cdot HTH=e^{i\pi/4}\big(\cos\tfrac\pi8I-i\sin\tfrac\pi8Z\big)\big(\cos\tfrac\pi8I-i\sin\tfrac\pi8X\big)
    Multiply the two factorisations; the global phases add to eiπ/4e^{i\pi/4}.
  4. Step 4:
    =eiπ/4[cos⁡2π8I−icos⁡π8sin⁡π8(X+Z)−sin⁡2π8 ZX]=e^{i\pi/4}\Big[\cos^2\tfrac\pi8I-i\cos\tfrac\pi8\sin\tfrac\pi8(X+Z)-\sin^2\tfrac\pi8\,ZX\Big]
    Expand the product of the two brackets; (−i)2=−1(-i)^2=-1.
  5. Step 5:
    =eiπ/4[cos⁡2π8I−isin⁡π8(cos⁡π8X+sin⁡π8Y+cos⁡π8Z)]=e^{i\pi/4}\Big[\cos^2\tfrac\pi8I-i\sin\tfrac\pi8\big(\cos\tfrac\pi8X+\sin\tfrac\pi8Y+\cos\tfrac\pi8Z\big)\Big]
    ZX=iYZX=iY, so −sin⁡2π8 ZX=−isin⁡2π8 Y-\sin^2\tfrac\pi8\,ZX=-i\sin^2\tfrac\pi8\,Y; factor −isin⁡π8-i\sin\tfrac\pi8 out of the three Pauli terms.
  6. Step 6:
    v⃗=(cos⁡π8,sin⁡π8,cos⁡π8),∥v⃗∥2sin⁡2π8+cos⁡4π8=(1+cos⁡2π8)sin⁡2π8+cos⁡4π8=1\vec v=\big(\cos\tfrac\pi8,\sin\tfrac\pi8,\cos\tfrac\pi8\big),\qquad\lVert\vec v\rVert^2\sin^2\tfrac\pi8+\cos^4\tfrac\pi8=\big(1+\cos^2\tfrac\pi8\big)\sin^2\tfrac\pi8+\cos^4\tfrac\pi8=1
    Check that the bracket has the form cos⁡λ2I−isin⁡λ2 n^⋅σ⃗\cos\tfrac\lambda2I-i\sin\tfrac\lambda2\,\hat n\cdot\vec\sigma: with c=cos⁡2π8c=\cos^2\tfrac\pi8, (1+c)(1−c)+c2=1(1+c)(1-c)+c^2=1.
  7. Step 7:
    T⋅HTH=eiπ/4Rn^(λ),cos⁡λ2=cos⁡2π8,n^=(cos⁡π8,sin⁡π8,cos⁡π8)1+cos⁡2π8T\cdot HTH=e^{i\pi/4}R_{\hat n}(\lambda),\qquad\cos\tfrac\lambda2=\cos^2\tfrac\pi8,\qquad\hat n=\frac{(\cos\frac\pi8,\sin\frac\pi8,\cos\frac\pi8)}{\sqrt{1+\cos^2\frac\pi8}}
    Read off cos⁡λ2\cos\tfrac\lambda2 from the identity coefficient and normalise the axis; sin⁡λ2=sin⁡π81+cos⁡2π8\sin\tfrac\lambda2=\sin\tfrac\pi8\sqrt{1+\cos^2\tfrac\pi8}.
  8. Step 8:
    cos⁡2π8=1+cos⁡π42=2+24≈0.853553\cos^2\tfrac\pi8=\frac{1+\cos\frac\pi4}2=\frac{2+\sqrt2}4\approx0.853553
    Half-angle formula with cos⁡π4=22\cos\tfrac\pi4=\tfrac{\sqrt2}2.

Result

T⋅HTH=eiπ/4Rn^(λ),cos⁡λ2=cos⁡2π8=2+24\boxed{T\cdot HTH=e^{i\pi/4}R_{\hat n}(\lambda),\qquad\cos\frac\lambda2=\cos^2\frac\pi8=\frac{2+\sqrt2}4}
Proposition

The angle λ is an irrational multiple of π

Let λ∈(0,2π)\lambda\in(0,2\pi) be defined by cos⁡λ2=cos⁡2π8\cos\tfrac\lambda2=\cos^2\tfrac\pi8. Then λ/π∉Q\lambda/\pi\notin\mathbb Q.

Proof (5 steps)
  1. Step 1:
    cos⁡λ=2cos⁡2λ2−1=2(2+24)2−1=6+428−1=22−14\cos\lambda=2\cos^2\tfrac\lambda2-1=2\Big(\frac{2+\sqrt2}4\Big)^2-1=\frac{6+4\sqrt2}8-1=\frac{2\sqrt2-1}4
    Double-angle formula and (2+2)2=6+42(2+\sqrt2)^2=6+4\sqrt2.
  2. Step 2:
    x=2cos⁡λ=22−12 ⇒ (2x+1)2=8 ⇒ x2+x−74=0x=2\cos\lambda=\frac{2\sqrt2-1}2\ \Rightarrow\ (2x+1)^2=8\ \Rightarrow\ x^2+x-\frac74=0
    Isolate 22=2x+12\sqrt2=2x+1 and square.
  3. Step 3:
    λπ=pq∈Q ⇒ ζ=eiλ satisfies ζ2q=e2πip=1\frac\lambda\pi=\frac pq\in\mathbb Q\ \Rightarrow\ \zeta=e^{i\lambda}\ \text{satisfies}\ \zeta^{2q}=e^{2\pi ip}=1
    Suppose for contradiction that λ/π\lambda/\pi is rational; then ζ\zeta is a root of unity, i.e. a root of the monic integer polynomial z2q−1z^{2q}-1, hence an algebraic integer, and so is ζˉ=ζ2q−1\bar\zeta=\zeta^{2q-1}.
  4. Step 4:
    x=ζ+ζˉ is an algebraic integerx=\zeta+\bar\zeta\ \text{is an algebraic integer}
    Algebraic integers form a ring, so the sum ζ+ζˉ=2cos⁡λ\zeta+\bar\zeta=2\cos\lambda is an algebraic integer.
  5. Step 5:
    x∉Q ⇒ minimal polynomial of x over Q is x2+x−74∉Z[x]x\notin\mathbb Q\ \Rightarrow\ \text{minimal polynomial of }x\text{ over }\mathbb Q\text{ is }x^2+x-\tfrac74\notin\mathbb Z[x]
    xx is irrational because 2\sqrt2 is, so its minimal polynomial has degree 22 and is the monic quadratic found above. An algebraic integer has a monic minimal polynomial with integer coefficients (Gauss's lemma), but −74∉Z-\tfrac74\notin\mathbb Z: contradiction. Hence λ/π\lambda/\pi is irrational.

∎

Theorem

Density of the group generated by H and T

The products of HH and TT approximate every single-qubit unitary up to a global phase to arbitrary accuracy. Together with CNOT, {H,T,CNOT}\{H,T,\mathrm{CNOT}\} is approximately universal: any circuit of mm CNOT and single-qubit gates can be approximated to accuracy ε\varepsilon by approximating each single-qubit gate to accuracy ε/m\varepsilon/m.

Proof (7 steps)
  1. Step 1:
    θk=kλ mod 2π,k=1,…,N+1,θj≠θk (j≠k)\theta_k=k\lambda\bmod2\pi,\quad k=1,\dots,N+1,\qquad\theta_j\ne\theta_k\ (j\ne k)
    If θj=θk\theta_j=\theta_k then (j−k)λ=2πl(j-k)\lambda=2\pi l for an integer ll, so λ/π=2l/(j−k)\lambda/\pi=2l/(j-k) would be rational, contradicting the proposition.
  2. Step 2:
    ∃ j>k: 0<∣θj−θk∣<2πN\exists\,j>k:\ 0<\lvert\theta_j-\theta_k\rvert<\tfrac{2\pi}N
    Pigeonhole: N+1N+1 distinct points in [0,2π)[0,2\pi) and NN intervals of length 2π/N2\pi/N, so two points share an interval.
  3. Step 3:
    δ:=(j−k)λ mod 2π∈(−2πN,2πN)∖{0} ⇒ {rδ}r∈Z is 2πN-dense in [0,2π)\delta:=(j-k)\lambda\bmod2\pi\in\big(-\tfrac{2\pi}N,\tfrac{2\pi}N\big)\setminus\{0\}\ \Rightarrow\ \{r\delta\}_{r\in\mathbb Z}\ \text{is}\ \tfrac{2\pi}N\text{-dense in}\ [0,2\pi)
    Consecutive multiples of δ\delta are less than 2π/N2\pi/N apart, so every angle α\alpha lies within 2π/N2\pi/N of some rδr\delta, i.e. of r(j−k)λr(j-k)\lambda modulo 2π2\pi.
  4. Step 4:
    E(Rn^(α),Rn^(β))=∣1−ei(α−β)/2∣=2∣sin⁡α−β4∣≤∣α−β∣2E\big(R_{\hat n}(\alpha),R_{\hat n}(\beta)\big)=\lvert1-e^{i(\alpha-\beta)/2}\rvert=2\big\lvert\sin\tfrac{\alpha-\beta}4\big\rvert\le\tfrac{\lvert\alpha-\beta\rvert}2
    Rn^(α)Rn^(β)†=Rn^(α−β)R_{\hat n}(\alpha)R_{\hat n}(\beta)^\dagger=R_{\hat n}(\alpha-\beta) has eigenvalues e∓i(α−β)/2e^{\mp i(\alpha-\beta)/2}. Rotation angles matter only modulo 2π2\pi up to the global phase Rn^(θ+2π)=−Rn^(θ)R_{\hat n}(\theta+2\pi)=-R_{\hat n}(\theta), so (T⋅HTH)r(j−k)(T\cdot HTH)^{r(j-k)} approximates every Rn^(α)R_{\hat n}(\alpha) within π/N\pi/N up to phase.
  5. Step 5:
    H Rn^(λ) H=Rm^(λ),m^=(cos⁡π8,−sin⁡π8,cos⁡π8)1+cos⁡2π8H\,R_{\hat n}(\lambda)\,H=R_{\hat m}(\lambda),\qquad\hat m=\frac{(\cos\frac\pi8,-\sin\frac\pi8,\cos\frac\pi8)}{\sqrt{1+\cos^2\frac\pi8}}
    Conjugation by HH maps (rx,ry,rz)↦(rz,−ry,rx)(r_x,r_y,r_z)\mapsto(r_z,-r_y,r_x) on the Bloch sphere, so HTH⋅T=H(T⋅HTH)HHTH\cdot T=H(T\cdot HTH)H (up to phase) rotates by the same λ\lambda about m^\hat m, which is not parallel to n^\hat n; the same argument approximates every Rm^(α)R_{\hat m}(\alpha).
  6. Step 6:
    U=eiγRn^(β1)Rm^(γ1)Rn^(β2)Rm^(γ2)⋯Rn^(βL)Rm^(γL)U=e^{i\gamma}R_{\hat n}(\beta_1)R_{\hat m}(\gamma_1)R_{\hat n}(\beta_2)R_{\hat m}(\gamma_2)\cdots R_{\hat n}(\beta_L)R_{\hat m}(\gamma_L)
    For non-parallel rotation axes every U∈U(2)U\in U(2) is such a finite product (Nielsen–Chuang Exercise 4.11; with n^⊥m^\hat n\perp\hat m it is the usual Euler decomposition). Approximating each of the 2L2L factors to accuracy ε/(2L)\varepsilon/(2L) gives UU to accuracy ε\varepsilon by additivity of errors.
  7. Step 7:
    E(∏i=1mUi,∏i=1mVi)≤∑i=1mE(Ui,Vi)≤m⋅εm=εE\Big(\prod_{i=1}^mU_i,\prod_{i=1}^mV_i\Big)\le\sum_{i=1}^mE(U_i,V_i)\le m\cdot\frac\varepsilon m=\varepsilon
    For a multi-qubit circuit (exactly universal by the previous section), keep every CNOT and replace each single-qubit gate by an H,TH,T word within ε/m\varepsilon/m.

∎

Theorem

Solovay–Kitaev theorem

Let G⊂SU(2)\mathcal G\subset SU(2) be a finite gate set that is closed under inverses and generates a dense subgroup of SU(2)SU(2) (for example HH and TT rescaled to determinant 11, together with their inverses). With the exponent c=ln⁡5/ln⁡(3/2)≈3.97c=\ln5/\ln(3/2)\approx3.97, the following holds: for every U∈SU(2)U\in SU(2) and every ε∈(0,1)\varepsilon\in(0,1) there is a product WW of at most O(log⁡c(1/ε))O(\log^c(1/\varepsilon)) gates of G\mathcal G with ∥U−W∥≤ε\lVert U-W\rVert\le\varepsilon, and WW can be found by a classical algorithm in time O(log⁡2.71(1/ε))O(\log^{2.71}(1/\varepsilon)).

Proof (8 steps)
  1. Step 1:
    G≤l0 is an ε0-net of SU(2),capprox2 ε0<1\mathcal G_{\le l_0}\ \text{is an}\ \varepsilon_0\text{-net of}\ SU(2),\qquad c_{\mathrm{approx}}^2\,\varepsilon_0<1
    Proof sketch. Base case: because the generated group is dense and SU(2)SU(2) is compact, all words of some length ≤l0\le l_0 form an ε0\varepsilon_0-net; ε0\varepsilon_0 is fixed small enough for the recursion to contract. Level 00 returns the nearest net point U0U_0, with ε0\varepsilon_0 error and l0l_0 gates.
  2. Step 2:
    Δ=U Un−1†,∥Δ−I∥≤εn−1\Delta=U\,U_{n-1}^\dagger,\qquad\lVert\Delta-I\rVert\le\varepsilon_{n-1}
    Level nn: the remaining error of the level-(n−1)(n-1) approximation Un−1U_{n-1} is a unitary close to the identity.
  3. Step 3:
    Δ=VWV†W†,∥V−I∥,∥W−I∥≤cgcεn−1\Delta=VWV^\dagger W^\dagger,\qquad\lVert V-I\rVert,\lVert W-I\rVert\le c_{\mathrm{gc}}\sqrt{\varepsilon_{n-1}}
    Balanced group commutator: a rotation by a small angle θ\theta equals the commutator of two rotations by angles of order θ\sqrt\theta about perpendicular axes.
  4. Step 4:
    Un=V~W~V~†W~† Un−1,εn≤capprox εn−13/2U_n=\tilde V\tilde W\tilde V^\dagger\tilde W^\dagger\,U_{n-1},\qquad\varepsilon_n\le c_{\mathrm{approx}}\,\varepsilon_{n-1}^{3/2}
    Approximate VV and WW recursively at level n−1n-1 by V~,W~\tilde V,\tilde W. The commutator suppresses their errors: the first-order terms cancel and the remainder is of order εn−1⋅εn−1\varepsilon_{n-1}\cdot\sqrt{\varepsilon_{n-1}}.
  5. Step 5:
    ln=5 ln−1=5n l0l_n=5\,l_{n-1}=5^n\,l_0
    UnU_n uses Un−1U_{n-1} once and the level-(n−1)(n-1) words for V,WV,W and their inverses (closure of G\mathcal G under inverses) once each: five words of length ln−1l_{n-1}.
  6. Step 6:
    capprox2 εn≤(capprox2 εn−1)3/2 ⇒ capprox2 εn≤(capprox2 ε0)(3/2)nc_{\mathrm{approx}}^2\,\varepsilon_n\le\big(c_{\mathrm{approx}}^2\,\varepsilon_{n-1}\big)^{3/2}\ \Rightarrow\ c_{\mathrm{approx}}^2\,\varepsilon_n\le\big(c_{\mathrm{approx}}^2\,\varepsilon_0\big)^{(3/2)^n}
    Multiply the error recursion by capprox2c_{\mathrm{approx}}^2 and iterate; the error decreases doubly exponentially in nn because capprox2ε0<1c_{\mathrm{approx}}^2\varepsilon_0<1.
  7. Step 7:
    εn≤ε ⇐ (32)n≥ln⁡(1/(capprox2ε))ln⁡(1/(capprox2ε0))\varepsilon_n\le\varepsilon\ \Leftarrow\ \Big(\frac32\Big)^n\ge\frac{\ln\big(1/(c_{\mathrm{approx}}^2\varepsilon)\big)}{\ln\big(1/(c_{\mathrm{approx}}^2\varepsilon_0)\big)}
    Take logarithms of the bound of the previous step; the smallest such nn is O(log⁡log⁡(1/ε))O(\log\log(1/\varepsilon)).
  8. Step 8:
    ln=l0 5n=l0((32)n)ln⁡5/ln⁡(3/2)=O(log⁡c1ε),c=ln⁡5ln⁡(3/2)≈3.97l_n=l_0\,5^n=l_0\Big(\big(\tfrac32\big)^n\Big)^{\ln5/\ln(3/2)}=O\Big(\log^{c}\frac1\varepsilon\Big),\qquad c=\frac{\ln5}{\ln(3/2)}\approx3.97
    Write 5n=((3/2)n)log⁡3/255^n=\big((3/2)^n\big)^{\log_{3/2}5} and insert the bound on (3/2)n(3/2)^n, which is O(log⁡(1/ε))O(\log(1/\varepsilon)) up to a constant factor.

∎

Quick check

Compute cos⁡λ2=cos⁡2π8\cos\tfrac\lambda2=\cos^2\tfrac\pi8 to three decimals.

tolerance ±0.001

Quick check

Which property of λ\lambda makes the powers of T⋅HTHT\cdot HTH approximate every rotation about n^\hat n?

Select one answer

Lab and references#

In the lab you build the Toffoli gate from {H,T,T†,CNOT}\{H,T,T^\dagger,\mathrm{CNOT}\} with at most six CNOTs. The grader compares your 8×88\times8 unitary with CCX\mathrm{CCX} through FU=∣Tr(CCX†U)∣/8F_U=\lvert\mathrm{Tr}(\mathrm{CCX}^\dagger U)\rvert/8; a circuit that builds CCZ\mathrm{CCZ} instead scores FU=0.75F_U=0.75.

References

  1. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary ed., Cambridge University Press (2010), §3.2.5 (reversible computation), §4.3 (Fig. 4.9), §4.5 (universal quantum gates), Appendix 3 (Solovay–Kitaev).doi:10.1017/CBO9780511976667
  2. A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin and H. Weinfurter, Elementary gates for quantum computation, Physical Review A 52, 3457–3467 (1995).doi:10.1103/PhysRevA.52.3457
  3. T. Toffoli, Reversible computing, in Automata, Languages and Programming (ICALP 1980), Lecture Notes in Computer Science 85, Springer, 632–644 (1980).doi:10.1007/3-540-10003-2_104
  4. C. M. Dawson and M. A. Nielsen, The Solovay–Kitaev algorithm, Quantum Information and Computation 6, 81–95 (2006); arXiv:quant-ph/0505030 (2005).arxiv.org

Hands-on labs

  • Decompose the Toffoli gate

    1 step · auto-graded

    Build the Toffoli gate CCX∣a,b,c⟩=∣a,b,c⊕ab⟩\mathrm{CCX}\lvert a,b,c\rangle=\lvert a,b,c\oplus ab\rangle (controls 0,10,1, target 22) on three qubits from the Clifford+TT set {H,T,T†,CNOT}\{H,T,T^\dagger,\mathrm{CNOT}\} with at most six CNOTs and fifteen gates in total.

    Open lab