Simple Algorithm
Quantum Computing · Rydberg State · 30 min

Toffoli, T-Count & Multi-Controlled Gates

Decomposing big controls into Clifford+T.

The Toffoli is classical logic's universal reversible gate, but in a fault-tolerant quantum computer it is expensive: every TT gate it contains costs a distilled magic state. How many does it need? Seven without ancillas; four with an ancilla and a measurement. You will derive the seven-TT circuit from a phase polynomial, prove that CNOT-and-phase circuits cannot do better, and see how the cost scales to many controls.

What you’ll learn

  • Explain why TT-count is the cost metric of fault-tolerant circuits, and why the Toffoli dominates it.
  • Derive the seven-TT CCZ circuit from 4abc=a+b+c−(a⊕b)−(a⊕c)−(b⊕c)+(a⊕b⊕c)4abc=a+b+c-(a\oplus b)-(a\oplus c)-(b\oplus c)+(a\oplus b\oplus c).
  • Prove that every circuit over CNOT, XX and phase gates implementing CCZ uses at least seven TT gates, and state what is known with Hadamards, ancillas and measurement.
  • Count Toffolis and TT gates for Λk(X)\Lambda_k(X) under different ancilla budgets.

Why the Toffoli, and why it is expensive

The Toffoli gate ∣a,b,c⟩↦∣a,b,c⊕ab⟩\ket{a,b,c}\mapsto\ket{a,b,c\oplus ab} is universal for classical reversible computation, so it is how a quantum computer evaluates arithmetic, oracles and comparisons. Remarkably, Toffoli and Hadamard together are already computationally universal for quantum computation (Shi 2003; Aharonov 2003), because circuits with real amplitudes can simulate complex ones using one extra qubit.

In an error-corrected machine, gates are not equally priced. In codes such as the surface code, Clifford operations are comparatively cheap, while each TT gate consumes a magic state that must be distilled at considerable cost in qubits and time. The cost of a fault-tolerant algorithm is therefore usually quoted in TT gates or Toffolis, and the Toffoli is the gate that most often dominates it.

CCX=(I⊗I⊗H)  CCZ  (I⊗I⊗H),CCZ∣x1x2x3⟩=(−1)x1x2x3∣x1x2x3⟩\mathrm{CCX}=(\id\otimes\id\otimes H)\;\mathrm{CCZ}\;(\id\otimes\id\otimes H),\qquad\mathrm{CCZ}\ket{x_1x_2x_3}=(-1)^{x_1x_2x_3}\ket{x_1x_2x_3}
Hadamards are Clifford, so the Toffoli and the symmetric, diagonal CCZ have the same TT-count. We work with CCZ.

Seven T gates from a phase polynomial

DerivationThe phase polynomial of CCZ
  1. (−1)x1x2x3=ω4x1x2x3,ω=eiπ/4(-1)^{x_1x_2x_3}=\omega^{4x_1x_2x_3},\qquad\omega=e^{i\pi/4}

    Write the sign as a power of the TT phase, since T∣x⟩=ωx∣x⟩T\ket x=\omega^x\ket x.

  2. a⊕b=a+b−2aba\oplus b=a+b-2ab

    The basic identity for bits.

  3. a⊕b⊕c=a+b+c−2(ab+ac+bc)+4abca\oplus b\oplus c=a+b+c-2(ab+ac+bc)+4abc

    Apply it twice, to (a⊕b)⊕c(a\oplus b)\oplus c.

  4. 4abc=a+b+c−(a⊕b)−(a⊕c)−(b⊕c)+(a⊕b⊕c)4abc=a+b+c-(a\oplus b)-(a\oplus c)-(b\oplus c)+(a\oplus b\oplus c)

    Combine: the pairwise products cancel, and each of the seven non-empty parities appears with coefficient ±1\pm1.

  5. CCZ∣x⟩=ω x1+x2+x3−(x1⊕x2)−(x1⊕x3)−(x2⊕x3)+(x1⊕x2⊕x3)∣x⟩\mathrm{CCZ}\ket{x}=\omega^{\,x_1+x_2+x_3-(x_1\oplus x_2)-(x_1\oplus x_3)-(x_2\oplus x_3)+(x_1\oplus x_2\oplus x_3)}\ket{x}

    So CCZ is seven TT-type gates, each applied while some wire carries the right parity: TT for odd-weight parities, T†T^\dagger for even-weight ones. A CNOT network supplies the parities and must compose to the identity.

The circuit below implements exactly this. After preparing ∣+++⟩\ket{+++}, it applies TT to x1,x2,x3x_1,x_2,x_3. Six CNOTs then walk the wires through the parities x1⊕x2x_1\oplus x_2 (wire 1) and x1⊕x2⊕x3x_1\oplus x_2\oplus x_3, x2⊕x3x_2\oplus x_3, x1⊕x3x_1\oplus x_3 (wire 2), before restoring (x1,x2,x3)(x_1,x_2,x_3). A TT-type gate sits in each of those four slots, but every one of them is a TT, so the circuit is wrong.

Think first Why do the single variables and the triple parity get TT, while the pairs get T†T^\dagger?

It is inclusion–exclusion. In 4abc=a+b+c−(a⊕b)−⋯+(a⊕b⊕c)4abc=a+b+c-(a\oplus b)-\dots+(a\oplus b\oplus c), a parity of weight ∣y∣\abs y carries the coefficient (−1)∣y∣+1(-1)^{\abs y+1}: plus for weights 1 and 3, minus for weight 2.

Seven is optimal

DerivationProof
  1. CNOT and XX act affinely on bits, and every phase gate multiplies by ωk\omega^{k} (k=±1k=\pm1 for T±1T^{\pm1}, ±2\pm2 for S±1S^{\pm1}, 44 for ZZ) according to the current value of its wire. Since ancillas start at 0, every wire always holds an affine parity y⋅x⊕cy\cdot x\oplus c of the inputs.

  2. U∣x⟩∣0⟩=ω c0+∑y≠0ay χy(x)∣x⟩∣0⟩,χy(x)=y⋅x mod 2∈{0,1}U\ket{x}\ket{0}=\omega^{\,c_0+\sum_{y\neq0}a_y\,\chi_y(x)}\ket{x}\ket{0},\qquad\chi_y(x)=y\cdot x\bmod2\in\{0,1\}

    Collect the phases. A gate of weight kk on a wire holding y⋅x⊕1y\cdot x\oplus1 contributes k(1−χy)k(1-\chi_y), so it adds −k-k to aya_y and kk to c0c_0. Only TT-type gates have odd kk, so the TT-count is at least the number of yy with aya_y odd. A global phase only shifts c0c_0.

  3. ∑y≠0dy χy(x)∈8Z  ∀x⟹dz=−14∑x(∑ydyχy(x))(−1)z⋅x∈2Z\sum_{y\neq0}d_y\,\chi_y(x)\in8\Z\ \ \forall x\quad\Longrightarrow\quad d_z=-\tfrac14\sum_{x}\Big(\sum_{y}d_y\chi_y(x)\Big)(-1)^{z\cdot x}\in2\Z

    Uniqueness mod 2: for n=3n=3, ∑xχy(x)(−1)z⋅x=−4[y=z]\sum_x\chi_y(x)(-1)^{z\cdot x}=-4[y=z] for z≠0z\neq0. So if two coefficient vectors a,a′a,a' give the same phase function mod 8, their difference dd is even: the parity pattern of the aya_y is determined by the gate.

  4. 4x1x2x3=∑y≠0(−1)∣y∣+1 χy(x)4x_1x_2x_3=\sum_{y\neq0}(-1)^{\abs y+1}\,\chi_y(x)

    For CCZ one representation has all seven coefficients odd, hence every representation does, and seven TT-type gates are necessary. ∎

Allowing Hadamards inside the circuit enlarges the search space, but seven remains optimal for ancilla-free Clifford+TT circuits; this was settled by exhaustive search (Gosset, Kliuchnikov, Mosca & Russo 2014). The TT-depth can be reduced: to 3 without ancillas (Amy, Maslov, Mosca & Roetteler 2013) and to 1 with four ancillas (Selinger 2013), still with seven TT gates. Measurement changes the rules altogether:

SettingTT gatesNotes
Unitary, no ancilla7optimal; TT-depth 3
Unitary, 4 ancillas7TT-depth 1 (Selinger 2013)
One ancilla, measurement and classically controlled Cliffords4Jones 2013
Temporary logical-AND (target starts in ∣0⟩\ket0)4 to compute, 0 to uncomputeuncompute with an XX-basis measurement and a classically controlled CZ (Gidney 2018)
Check your understanding

Why can measurement-assisted constructions beat the bound of seven?

  1. They are not unitary circuits of the kind the bound covers: measurements with classically controlled Clifford corrections lie outside it
  2. They use rotations by angles smaller than π/4\pi/4
  3. The bound of seven is only a conjecture
  4. They implement the Toffoli only approximately
Show the answer

A. They are not unitary circuits of the kind the bound covers: measurements with classically controlled Clifford corrections lie outside it

The lower bound concerns unitary Clifford+TT circuits. With an ancilla, a measurement and classically controlled Clifford corrections, Jones's construction implements an exact Toffoli with four TT gates.

Many controls

For Λk(X)\Lambda_k(X) with kk controls, the ancilla budget sets the price. The standard approach computes the AND of the controls into ancillas, applies the final flip, and uncomputes.

Predict before you look

With k−2k-2 clean ancillas, how many Toffolis does the compute–uncompute ladder need for Λ5(X)\Lambda_5(X)?

Show the answer

7 Toffolis

2k−3=72k-3=7. Three Toffolis compute c1∧c2c_1\wedge c_2, then ∧ c3\wedge\,c_3, then ∧ c4\wedge\,c_4 into the three ancillas; one Toffoli flips the target, controlled by the last ancilla and c5c_5; three more uncompute the ancillas.

ConstructionAncillasCost
Compute–uncompute ladder of Toffolisk−2k-2 clean2k−32k-3 Toffolis, i.e. 7(2k−3)7(2k-3) TT gates
Ladder of temporary logical-ANDsk−1k-1 clean4(k−1)4(k-1) TT gates (Gidney 2018)
Barenco et al. recursionone borrowed (dirty) qubitO(k)\order{k} gates
Barenco et al. recursionnoneO(k2)\order{k^2} gates

Key takeaways

  • Fault-tolerant cost is counted in TT gates, and Toffoli/CCZ gates are their most common source.
  • 4abc=a+b+c−(a⊕b)−(a⊕c)−(b⊕c)+(a⊕b⊕c)4abc=a+b+c-(a\oplus b)-(a\oplus c)-(b\oplus c)+(a\oplus b\oplus c) yields CCZ from seven TT-type gates and six CNOTs.
  • For CNOT-and-phase circuits the parity pattern of the phase polynomial is unique, so seven TT gates are necessary; seven is also optimal for ancilla-free Clifford+TT circuits.
  • Measurement changes the price: four TT gates for a Toffoli (Jones), and a temporary AND costs four to compute and none to uncompute (Gidney).

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Why is the TT-count, rather than the CNOT count, the headline cost of a fault-tolerant circuit?

  1. TT gates are harder to calibrate on physical hardware
  2. In codes such as the surface code, Clifford gates are cheap while each TT needs a distilled magic state
  3. CNOTs can always be compiled away
  4. TT gates cause more decoherence than CNOTs
Show the answer

B. In codes such as the surface code, Clifford gates are cheap while each TT needs a distilled magic state

Fault-tolerant Clifford operations can be done directly (transversally or by lattice surgery), but TT cannot; each one consumes a magic state from a distillation factory, and those factories dominate the space-time cost.

Question 2

In the seven-TT CCZ circuit, which of these parities receives TT rather than T†T^\dagger?

  1. x1⊕x2x_1\oplus x_2
  2. x2⊕x3x_2\oplus x_3
  3. x1⊕x2⊕x3x_1\oplus x_2\oplus x_3
  4. x1⊕x3x_1\oplus x_3
Show the answer

C. x1⊕x2⊕x3x_1\oplus x_2\oplus x_3

Inclusion–exclusion: odd-weight parities (x1x_1, x2x_2, x3x_3 and x1⊕x2⊕x3x_1\oplus x_2\oplus x_3) carry +1+1, hence TT; the three pairs carry −1-1, hence T†T^\dagger.

Question 3

How many TT gates does Jones's measurement-assisted Toffoli use?

  1. 7
  2. 3
  3. 0
  4. 4
Show the answer

D. 4

Four, using one ancilla, a measurement and classically controlled Clifford corrections. The bound of seven applies only to unitary circuits.

Question 4

How many Toffolis does the compute–uncompute ladder for Λk(X)\Lambda_k(X) with k−2k-2 clean ancillas use?

  1. 2k−32k-3
  2. kk
  3. 2k2k
  4. k2k^2
Show the answer

A. 2k−32k-3

k−2k-2 Toffolis compute the running AND into the ancillas, one more flips the target, and k−2k-2 uncompute: 2(k−2)+1=2k−32(k-2)+1=2k-3.

Further reading

  • M. Amy, D. Maslov, M. Mosca & M. Roetteler, "A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits", IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 32, 818 (2013).
  • C. Jones, "Low-overhead constructions for the fault-tolerant Toffoli gate", Phys. Rev. A 87, 022328 (2013).
  • D. Gosset, V. Kliuchnikov, M. Mosca & V. Russo, "An algorithm for the T-count", Quantum Inf. Comput. 14, 1261 (2014).
  • C. Gidney, "Halving the cost of quantum addition", Quantum 2, 74 (2018).
  • M. Amy & M. Mosca, "T-count optimization and Reed–Muller codes", IEEE Trans. Inf. Theory 65, 4771 (2019).