Halving the cost of quantum addition

By Craig Gidney. Quantum, 2017

338 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/4ef1f2ae3f04d4600e12cfe95afb16e8d13ccc35

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity (2018, background): “Computing and uncomputing and operations, defined in terms of Toffoli gates and in terms of Clifford+T gates [60].”
Magic State Distillation: Not as Costly as You Think (2019, methodology): “cute CCZ gates using four T gates [38], or even only two T gates, if these CCZ gates are part of a computeuncompute circuit [39].”
A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery (2018, background): “Reducing the T count by increasing the circuit depth [49] can still be a useful circuit manipulation for”