# Halving the cost of quantum addition. (arXiv:1709.06648v1 [quant-ph])

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. Temporary logical-ANDs are a generally

useful tool when optimizing T-counts. They 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, our constructions represent a

significant reduction in projected costs of quantum computation. We also

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.