Craig Gidney (Aug 01 2025).
Abstract: In 2004, Cuccaro et al found a quantum-quantum adder with
O(n) gate cost and
O(1) ancilla qubits. Since then, it's been an open question whether classical-quantum adders can achieve the same asymptotic complexity. These costs are particularly relevant to modular arithmetic circuits, which often offset by the classically known modulus. In this paper, I construct an adder that uses 3 clean ancillae and
4n±O(1) Toffoli gates to add a classical offset into a quantum register. I also present an adder with a Toffoli cost of
3n±O(1) that uses 2 clean ancillae and
n−2 dirty ancillae. I further show that applying the presented adders conditioned on a control qubit requires no additional workspace or Toffolis.
