Source-linked AI summary
Halving the cost of quantum addition
Craig Gidney
TL;DR
Quantum adders require costly T gates in surface-code quantum computing. The paper reframes temporary logical-ANDs to reduce an n-bit adder’s T-count from 8n + O(1) to 4n + O(1).
Problem
Surface-code quantum computing makes T-count optimization important, while the leading factor of 8 in n-bit adders remained unimproved for over a decade.
Method
The paper reframes ancilla-and-fix-up techniques as temporary logical-ANDs that store an AND using four T gates and erase it using zero T gates.
Results
8n + O(1) to 4n + O(1): temporary logical-ANDs halve the T-count of Cuccaro-style n-bit adders.
Takeaways & Limitations
Temporary logical-ANDs provide a broadly applicable way to reduce T-counts across arithmetic and other quantum circuits.
Takeaways & Limitations
The adder’s ancilla tradeoff depends on system regime: with few T factories, logarithmic-depth adders can run longer than ripple-carry adders.
Abstract
from arXiv · showhide
We improve the number of T gates needed to perform an n-bit adder from 8n + O(1) to 4n + O(1). We do so via a "temporary logical-AND" construction which uses four T gates to store the logical-AND of two qubits into an ancilla and zero T gates to later erase the ancilla. This construction is equivalent to one by Jones, except that our framing makes it clear that the technique is far more widely applicable than previously realized. Temporary logical-ANDs can be applied to integer arithmetic, modular arithmetic, rotation synthesis, the quantum Fourier transform, Shor's algorithm, Grover oracles, and many other circuits. Because T gates dominate the cost of quantum computation based on the surface code, and temporary logical-ANDs are widely applicable, this represents a significant reduction in projected costs of quantum computation. In addition to our n-bit adder, we present an n-bit controlled adder circuit with T-count of 8n + O(1), a temporary adder that can be computed for the same cost as the normal adder but whose result can be kept until it is later uncomputed without using T gates, and discuss some other constructions whose T-count is improved by the temporary logical-AND.
Introduction
The paper targets T-count optimization because surface-code computations are expected to be dominated by costly T-gate production. A temporary logical-AND construction halves the leading T-count factor for Cuccaro-style adders and reveals broader applicability beyond addition.
- Adder construction: 4n −4 T gates and 2n −2 measurement depth implement the paper’s n-bit adder.The displayed 5-bit instance uses 16 T gates, four logical-AND computations, and four zero-T logical-AND erasures.
- Temporary logical-AND: 4 T gates compute a temporary logical-AND, while its later erasure requires no T gates.The construction combines ideas from matched-phase-error and ancilla-and-fix-up techniques.
- Motivation and contribution: T-count optimization is important because surface-code runtime is expected to be dominated in practice by the number of T gates.The surface code lacks a cheap mechanism for non-Clifford operations, and |T⟩-state distillation is sufficiently costly to create a runtime bottleneck.
- Motivation and contribution: 4n + O(1) T gates replace 8n + O(1) for Cuccaro-style n-bit adders by improving Toffoli operations in compute/uncompute pairs.The leading factor of 8 had persisted for over a decade before this construction.
- Broader applicability: Temporary logical-ANDs are more widely applicable than previously realized, including cases where operations share controls even when they are far apart.The reframing is presented as the paper’s main conceptual contribution, beyond its focus on addition.
Opportunity Cost of Ancillae
The adder saves 4n |T⟩ states versus Cuccaro’s construction by holding n ancillae for measurement depth 2n, creating an opportunity cost that depends on system resources. Under the paper’s estimate, this makes the adder worse beyond n > 1920, while logarithmic-depth alternatives can eventually have lower effective T-counts but require sufficient T factories.
- Adder tradeoff: 4n fewer |T⟩ states come at the cost of holding n ancillae through measurement-depth 2n.The tradeoff motivates evaluating ancilla opportunity cost before adopting the construction.
- Adder tradeoff: Ancillae consume resources that could otherwise support T factories, and insufficient space can make the construction infeasible.Cuccaro’s adder remains viable on small quantum computers with no spare ancillae.
- Effective T-count: 1 480|T⟩ states per measurement-depth is the estimated opportunity cost of holding an ancilla, based on spacetime-volume comparisons.A high-quality |T⟩ state is assigned 960 units of spacetime volume, while an ancilla stored through k serial measurements uses at least 2k units.
- Effective T-count: 1 480n2 + 4n is the adder’s effective T-count versus 8n for Cuccaro’s, making it worse when n > 1920.The calculation includes ancilla opportunity cost and accounts for ancillae being held for different durations.
- System dependence: The estimated cutoff is not fixed: improving T-factory spacetime volume lowers it, while improving ancilla storage raises it.Inactive-memory compression is cited as an example of an ancilla improvement, using six times fewer physical qubits than double-defect storage.
- Alternative adders: Θ(n lg n) opportunity cost lets logarithmic-depth adders eventually outperform the ripple-carry adder’s Θ(n2) opportunity cost despite higher raw T-count.This comparison assumes enough physical qubits and T factories to feed the logarithmic-depth adder.
Results
The results demonstrate that temporary logical-ANDs reduce T-costs across controlled and reversible addition, quantum rotations, phase gradients, Grover oracles, and low-depth adders. These constructions also enable T-free uncomputation and broad compute/uncompute-pair optimizations under stated conditions.
- Controlled and out-of-place adders: 8n + O(1) replaces 21n + O(1) for controlled additions conditioned on a control qubit.The controlled-adder building block has a T-count of 8.
- Controlled and out-of-place adders: 0 T gates are required to uncompute an out-of-place addition when registers storing both a and b remain available.The construction does not improve the cost of computing the out-of-place addition itself.
- Quantum-specific operations: 4n + O(lg n lg 1 ϵ ) T gates implement RZ(θ) on n qubits using a Hamming weight register and T-free uncomputation.The Hamming weight register is built with out-of-place adder building-blocks, while the remaining rotation cost is negligible for large n.
- Quantum-specific operations: 4n + O(1) T gates implement the n-qubit phase gradient operation when a reusable phase gradient register is available.The operation uses addition followed by phase kickback.
- Broader applications: 4 T gates are saved whenever compute/uncompute Toffoli pairs satisfy the phase-insensitivity condition for intermediate operations.The later Toffoli must uncompute the earlier one, and intermediate operations must not be sensitive to the entangled ancilla.
- Broader applications: 12n T gates suffice for an O(lg n)-depth reversible Brent-Kung adder, while temporary logical-ANDs halve the T-count of a naive Grover-oracle construction.The Grover-oracle optimization may require an unreasonable number of ancillae and does not generalize to every oracle-construction method.
Discussion
The discussion emphasizes that temporary logical-ANDs halve the leading T-count cost of addition while providing a broadly applicable optimization technique. It also identifies unresolved lower-bound questions and opportunities for further T-count reductions across the quantum-computing technology stack.
- Cost reduction: 8n + O(1) was the established T-count for addition before temporary logical-ANDs halved its leading factor.The paper replaces Toffolis in compute/uncompute pairs with temporary logical-ANDs.
- Temporary logical-ANDs: Temporary logical-ANDs are reusable circuit widgets whose measurement-based uncomputation can be more efficient than computation.The discussion highlights measurement as breaking the symmetry between computation and uncomputation.
- Lower bounds: 4 T gates are required by the proven lower bound for a Toffoli, but it remains possible that many Toffolis could use fewer than 4n T gates collectively.The authors suspect the true lower bound is 4 while acknowledging uncertainty about collective implementations.
- Future opportunities: Further T-count optimizations may exist from low-level operations through high-level constructions and across the technology stack for surface-code quantum computation.The discussion extends this outlook beyond basic paired Toffoli gates.