A Classical-Quantum Adder with Constant Workspace and Linear Gates
Abstract
In 2004, Cuccaro et al found a quantum-quantum adder with linear gate cost and
constant workspace overhead. Since then, it’s been an open question whether classicalquantum adders can achieve the same asymptotic complexity. In this paper, I resolve
the issue by constructing an adder that uses 3 clean ancillae and at most 4n−18 Toffoli
gates to add a classical offset into a quantum register.
constant workspace overhead. Since then, it’s been an open question whether classicalquantum adders can achieve the same asymptotic complexity. In this paper, I resolve
the issue by constructing an adder that uses 3 clean ancillae and at most 4n−18 Toffoli
gates to add a classical offset into a quantum register.
