Halving the cost of quantum addition

We improve the number of T gates needed to perform an n-bit adder from 8n + O(1) [1, 7, 10] 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 [15], 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), an out-of-place adder that can be uncomputed without using T gates, and discuss some other constructions whose T-count is improved by the temporary logical-AND.