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 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- 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 -count is the cost metric of fault-tolerant circuits, and why the Toffoli dominates it.
- Derive the seven- CCZ circuit from .
- Prove that every circuit over CNOT, and phase gates implementing CCZ uses at least seven gates, and state what is known with Hadamards, ancillas and measurement.
- Count Toffolis and gates for under different ancilla budgets.
Why the Toffoli, and why it is expensive
The Toffoli gate 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 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 gates or Toffolis, and the Toffoli is the gate that most often dominates it.
Seven T gates from a phase polynomial
Write the sign as a power of the phase, since .
The basic identity for bits.
Apply it twice, to .
Combine: the pairwise products cancel, and each of the seven non-empty parities appears with coefficient .
So CCZ is seven -type gates, each applied while some wire carries the right parity: for odd-weight parities, for even-weight ones. A CNOT network supplies the parities and must compose to the identity.
The circuit below implements exactly this. After preparing , it applies to . Six CNOTs then walk the wires through the parities (wire 1) and , , (wire 2), before restoring . A -type gate sits in each of those four slots, but every one of them is a , so the circuit is wrong.
Think first Why do the single variables and the triple parity get , while the pairs get ?
It is inclusion–exclusion. In , a parity of weight carries the coefficient : plus for weights 1 and 3, minus for weight 2.
Seven is optimal
CNOT and act affinely on bits, and every phase gate multiplies by ( for , for , for ) according to the current value of its wire. Since ancillas start at 0, every wire always holds an affine parity of the inputs.
Collect the phases. A gate of weight on a wire holding contributes , so it adds to and to . Only -type gates have odd , so the -count is at least the number of with odd. A global phase only shifts .
Uniqueness mod 2: for , for . So if two coefficient vectors give the same phase function mod 8, their difference is even: the parity pattern of the is determined by the gate.
For CCZ one representation has all seven coefficients odd, hence every representation does, and seven -type gates are necessary. ∎
Allowing Hadamards inside the circuit enlarges the search space, but seven remains optimal for ancilla-free Clifford+ circuits; this was settled by exhaustive search (Gosset, Kliuchnikov, Mosca & Russo 2014). The -depth can be reduced: to 3 without ancillas (Amy, Maslov, Mosca & Roetteler 2013) and to 1 with four ancillas (Selinger 2013), still with seven gates. Measurement changes the rules altogether:
| Setting | gates | Notes |
|---|---|---|
| Unitary, no ancilla | 7 | optimal; -depth 3 |
| Unitary, 4 ancillas | 7 | -depth 1 (Selinger 2013) |
| One ancilla, measurement and classically controlled Cliffords | 4 | Jones 2013 |
| Temporary logical-AND (target starts in ) | 4 to compute, 0 to uncompute | uncompute with an -basis measurement and a classically controlled CZ (Gidney 2018) |
Why can measurement-assisted constructions beat the bound of seven?
- They are not unitary circuits of the kind the bound covers: measurements with classically controlled Clifford corrections lie outside it
- They use rotations by angles smaller than
- The bound of seven is only a conjecture
- 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+ circuits. With an ancilla, a measurement and classically controlled Clifford corrections, Jones's construction implements an exact Toffoli with four gates.
Many controls
For with controls, the ancilla budget sets the price. The standard approach computes the AND of the controls into ancillas, applies the final flip, and uncomputes.
With clean ancillas, how many Toffolis does the compute–uncompute ladder need for ?
Show the answer
7 Toffolis
. Three Toffolis compute , then , then into the three ancillas; one Toffoli flips the target, controlled by the last ancilla and ; three more uncompute the ancillas.
| Construction | Ancillas | Cost |
|---|---|---|
| Compute–uncompute ladder of Toffolis | clean | Toffolis, i.e. gates |
| Ladder of temporary logical-ANDs | clean | gates (Gidney 2018) |
| Barenco et al. recursion | one borrowed (dirty) qubit | gates |
| Barenco et al. recursion | none | gates |
Key takeaways
- Fault-tolerant cost is counted in gates, and Toffoli/CCZ gates are their most common source.
- yields CCZ from seven -type gates and six CNOTs.
- For CNOT-and-phase circuits the parity pattern of the phase polynomial is unique, so seven gates are necessary; seven is also optimal for ancilla-free Clifford+ circuits.
- Measurement changes the price: four 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.
Why is the -count, rather than the CNOT count, the headline cost of a fault-tolerant circuit?
- gates are harder to calibrate on physical hardware
- In codes such as the surface code, Clifford gates are cheap while each needs a distilled magic state
- CNOTs can always be compiled away
- gates cause more decoherence than CNOTs
Show the answer
B. In codes such as the surface code, Clifford gates are cheap while each needs a distilled magic state
Fault-tolerant Clifford operations can be done directly (transversally or by lattice surgery), but cannot; each one consumes a magic state from a distillation factory, and those factories dominate the space-time cost.
In the seven- CCZ circuit, which of these parities receives rather than ?
Show the answer
C.
Inclusion–exclusion: odd-weight parities (, , and ) carry , hence ; the three pairs carry , hence .
How many gates does Jones's measurement-assisted Toffoli use?
- 7
- 3
- 0
- 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.
How many Toffolis does the compute–uncompute ladder for with clean ancillas use?
Show the answer
A.
Toffolis compute the running AND into the ancillas, one more flips the target, and uncompute: .
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).