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.

Article web page: