Source-linked AI summary
On the CNOT-cost of TOFFOLI gates
Vivek V. Shende, Igor L. Markov
TL;DR
The paper addresses whether the standard six-CNOT decomposition of the three-qubit TOFFOLI is optimal and how to prove lower bounds for related circuits. It uses canonical Cartan, cosine-sine, and demultiplexing decompositions to constrain low-CNOT circuits, proving the n-qubit lower bound and classifying three-qubit diagonal operators by CNOT-cost. The main scope boundary is that some ancilla-related enumeration arguments rely specifically on three-qubit circuit configurations, while relevant determinant statements weaken as the available qubit count varies.
Problem
The standard TOFFOLI decomposition uses six CNOT gates, but its CNOT-optimality and the exact cost of the n-qubit analogue required proof.
Method
The paper uses canonical Cartan KAK, cosine-sine, and demultiplexing decompositions to derive constraints on low-CNOT block-diagonal circuits.
Results
2n CNOTs are necessary for the n-qubit TOFFOLI without ancillae; for n = 3, six CNOTs are optimal even with ancillae.
Takeaways & Limitations
The results establish the six-CNOT TOFFOLI decomposition as optimal and completely classify three-qubit diagonal operators by CNOT-cost, including with ancillae.
Takeaways & Limitations
Some proofs assume three qubits when enumerating low-CZ circuit configurations, and determinant-based statements weaken when the available qubit count varies.
Abstract
from arXiv · showhide
The three-input TOFFOLI gate is the workhorse of circuit synthesis for classical logic operations on quantum data, e.g., reversible arithmetic circuits. In physical implementations, however, TOFFOLI gates are decomposed into six CNOT gates and several one-qubit gates. Though this decomposition has been known for at least 10 years, we provide here the first demonstration of its CNOT-optimality. We study three-qubit circuits which contain less than six CNOT gates and implement a block-diagonal operator, then show that they implicitly describe the cosine-sine decomposition of a related operator. Leveraging the canonicity of such decompositions to limit one-qubit gates appearing in respective circuits, we prove that the n-qubit analogue of the TOFFOLI requires at least 2n CNOT gates. Additionally, our results offer a complete classification of three-qubit diagonal operators by their CNOT-cost, which holds even if ancilla qubits are available.
1 Introduction
The paper establishes the CNOT-optimality of the standard six-CNOT TOFFOLI decomposition and develops a decomposition-based approach for proving gate-count lower bounds.
- Six CNOT gates appear in the textbook TOFFOLI decomposition alongside one-qubit H, T, and T† gates.
- Earlier five-two-qubit-gate evidence and the three-CNOT MARGOLUS result did not provide a general optimality proof for four- or five-CNOT TOFFOLI circuits.
- 2n CNOT gates are necessary for the n-qubit TOFFOLI without ancillae, and the n = 3 bound remains valid with ancillae.For three qubits, Figure 1 achieves the bound.
- Cartan KAK decompositions, including canonical cosine-sine and demultiplexing forms, provide the paper’s main tool for constraining circuit structure.Their multiplexor components commute with common circuit elements, enabling divide-and-conquer CNOT counting.
- The analysis converts CNOT and TOFFOLI questions to symmetric diagonal CZ and CCZ questions, then extends the techniques to diagonal operators and ancilla circuits.The paper defines local CZ-costs and uses lower bounds from local counts.
2 Preliminaries
The preliminaries define the gate notation, commuting and block-diagonal operator structures, circuit-cost measures, and decomposition tools used for CNOT-counting.
- CNOT-circuits and CZ-circuits are interchangeable by adding one-qubit Hadamard gates, while CZ-cost and CNOT-cost are equal.
- Operators commuting with Z on selected qubits are block-diagonal, with blocks indexed by computational-basis values of those qubits.
- The partial determinant maps a block-diagonal operator to a diagonal operator on selected qubits by taking determinants of its diagonal blocks.
- A commuting unitary admits a CZ-circuit with only diagonal gates on selected qubits exactly when its partial determinant is separable.
- Iterated cosine-sine and demultiplexing decompositions reduce general operators to multiplexed rotations and diagonal gates, yielding 2n CNOTs for an n-ply multiplexed Rz gate.The same construction gives 2n − 2 CNOTs for an arbitrary n-qubit diagonal operator.
- The paper notes that equality between CZ-cost and a local CZ-cost is not generally established, although it holds for all two-qubit operators and three-qubit diagonal operators.
3 Deriving gate constraints from circuit equations
This section derives structural constraints on low-CZ circuits from circuit equations and canonical decompositions, restricting the allowed one-qubit gates and circuit forms.
- Canonical circuit decompositions constrain which gates can appear in equations for block-diagonal operators.
- A basic lemma forces either paired diagonal structure among one-qubit factors or commutation of a remaining operator with Z on the relevant qubit.
- The resulting three-factor constraint requires an even number of anti-diagonal one-qubit gates unless a specified subcircuit commutes with Z.
- With exactly two CZ gates incident on a qubit, non-diagonal one-qubit gates on that qubit can be eliminated, possibly replacing one CZ or adding gates on neighboring qubits.
- For a five-CZ implementation of CCZ, the derived constraints make selected one-qubit gates diagonal, while the partial determinant condition then rules out the circuit.
4 The CNOT-cost of the TOFFOLI gate
The paper reduces TOFFOLI CNOT-counting to CZ-counting for CCZ, then combines local-cost invariants with cosine-sine circuit constraints to rule out five-CZ implementations. This establishes exact cost six and extends the lower bound to n-qubit TOFFOLI gates.
- Local CZ counting: The reduction uses qubit-local CZ-costs and the inequality 3|CCZ|CZ;ℓ/2 ≤ |CCZ|CZ to obtain local lower bounds.The CCZ gate has local cost three, which alone yields the weaker global bound |CCZ|CZ ≥ 5.
- Circuit constraints: Cosine-sine decomposition canonicity constrains one-qubit gates in minimum local-cost circuits, forcing them to be diagonal or anti-diagonal in relevant cases.Theorem 22 states that all one-qubit gates on a qubit with three incident CZ gates are diagonal or anti-diagonal.
- Exact cost: A hypothetical five-CZ CCZ circuit would force a nonseparable determinant condition, contradicting the structure of CZ(m,n).Two qubits would touch exactly three CZ gates, enabling the diagonal-gate restriction used in the contradiction.
- Exact cost: |CCZ|CZ = 6, establishing the exact six-CNOT cost of TOFFOLI.The lower bound follows after excluding hypothetical five-CZ circuits; a six-CZ construction is known.
- Local CZ counting: The ℓ-mux-spectrum characterizes ℓ-equivalence, linking spectral invariants to bounds on local CZ-cost.For local cost at most two, the spectrum must be congruent to unit-norm complex numbers occurring in conjugate pairs.
5 Three-qubit diagonal operators
The paper classifies three-qubit diagonal operators by CZ-cost using invariants that ignore local diagonal gates and qubit relabelling. It gives necessary and sufficient invariant conditions for costs from zero through five CZ gates, with a general upper bound for n-qubit diagonals.
- Invariants: Equivalent invariant tuples identify operators differing only by one-qubit diagonal gates and wire permutations, so they have the same CZ-cost.This establishes that the invariant tuple is sufficient for cost classification up to local diagonal equivalence and relabelling.
- Cost classification: 2 CZs touching qubit 1 occur iff S(D) matches one of three listed invariant families, while 4 CZs occur iff s(D) = (a,b,c;ab/c).The two-CZ conditions distinguish three invariant patterns; the four-CZ condition is stated in the unordered invariant notation.
- Cost classification: 5 CZs occur iff s(D) = (a,b,c;ab/c) or (a,b,c;abc), completing the reported three-qubit diagonal cost classification.The five-CZ condition adds the second invariant family alongside the four-CZ family.
- Generalization: Any n-qubit diagonal operator has CZ-cost at most 2n −2.This general upper bound extends beyond the three-qubit classification.
6 Circuits with ancillae
The section extends three-qubit diagonal-operator cost results to circuits with ancillae and uses ancilla-touching constraints to analyze minimal implementations. It also identifies a qubit-number dependence in key spectral arguments.
- Scope: The ancilla-inclusive argument establishes the relevant three-qubit diagonal-cost results despite proofs that initially enumerate only three-qubit configurations.Explicit checks eliminate the low-CZ ancilla configurations needed by the argument.
- Qubit-number dependence: For three-qubit CCZ, each qubit has local CZ-cost at least 3, whereas adding an identity ancilla can reduce a corresponding local cost to 2.The local spectral invariant therefore depends on the total number of available qubits.
- Ancilla extension: The three-qubit diagonal-operator CNOT-cost classification extends to circuits permitting ancilla qubits.The extension follows because the relevant spectral properties remain stable under adding ancillae.
- Ancilla constraints: Every ancilla in a qubit-minimal CZ circuit touches at least three CZ gates.Otherwise, the ancilla can be removed while using no more CZ gates.
- Ancilla constraints: Two-qubit operators have CZ-cost at most 3, forcing equality in the ancilla-count argument.An ancilla-touching lower bound of three CZ gates meets the general two-qubit upper bound.
- Circuit analysis: A four-qubit, five-CZ realization of a three-qubit diagonal operator with one ancilla is forced into specific incidence patterns, which are then contradicted using diagonal-gate and spectral constraints.The proof moves non-ancilla CZ gates outward and derives an impossible cost characterization.
7 Conclusion
The conclusion places the CNOT-cost results in the broader study of reversible quantum circuits and identifies open questions about one-qubit costs, other operators, and generalization.
- Context: TOFFOLI originated as a universal gate for classical reversible logic, whereas NOT and CNOT circuits implement only affine-linear transformations over F2.Single-qubit rotations supply the non-linearity missing from NOT and CNOT gates alone.
- Open cost questions: The number of non-inverter one-qubit gates can serve as a measure of reversible-computation non-linearity.The conclusion frames minimizing one-qubit gates as a distinct cost model from minimizing CNOTs.
- Open problems: The CNOT-cost of the controlled-swap, or Fredkin gate, remains unresolved.The paper notes that very little is known even for three-qubit operators computable by classical reversible circuits.
- Open problems: For n-qubit TOFFOLI, the paper proves a 2n lower bound without ancillae, while for n = 4 the known range is 8 ≤ |CCCZ|CZ ≤ 14.Existing constructions use quadratically many CNOTs without ancillae and linearly many with one ancilla, with a double-digit leading coefficient.
- Future directions: The authors propose systematic tracking of six Cartan decompositions as a possible route to simplifying the proof and extending the techniques.The decompositions correspond to conjugation by X and Z on each of three wires.
Appendix: Proof of Proposition 5
The appendix proves a characterization of when a unitary commuting with selected Z operators admits a CZ circuit with only diagonal gates on those qubits. It uses partial determinants and multiplexed rotations.
- Proposition 5: A commuting unitary U admits the restricted CZ implementation exactly when its partial determinant is separable.The selected qubits may then carry only diagonal gates.
- Proof: The forward direction verifies separability on CZ gates, selected-qubit diagonal gates, and gates acting outside the selected qubits.These operators form the generating cases used in the proof.
- Proof: The reverse direction factors out the partial determinant and implements the normalized operator by multiplexing circuits for its SU(2^(N−k))-valued diagonal blocks.The construction uses one-qubit diagonal gates together with CZ and Rx, Ry, Rz gates.
- Complexity: N-qubit operators commuting with Z on k qubits can be implemented with on the order of 2^k4^(N−k) one-qubit and CZ gates.Dimension counting indicates that roughly this many gates are necessary for almost all such operators.