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.
Craig Gidney (Wed,) studied this question.