Posted

Craig Gidney (Aug 01 2025).
Abstract: In 2004, Cuccaro et al found a quantum-quantum adder with O(n)O(n) gate cost and O(1)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)4n \pm 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)3n \pm O(1) that uses 2 clean ancillae and n2n-2 dirty ancillae. I further show that applying the presented adders conditioned on a control qubit requires no additional workspace or Toffolis.

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!