New Quantum Algorithms Perform Complex Arithmetic Without Extra Qubits
Physicists devise space-efficient quantum circuits that slash auxiliary memory requirements for integer multiplication and modular inversion.
Physicists have developed new quantum algorithms that perform core arithmetic operations using significantly fewer physical resources than previously thought possible. By designing circuits that compute directly inside the phase of quantum states without wasting extra memory qubits, the researchers achieved subquadratic gate counts while requiring zero ancilla qubits for several major arithmetic tasks, and at most a logarithmic number for others.
Arithmetic operations such as multiplication and inversion form the bedrock of complex quantum algorithms, including Shor’s factoring method and simulations in quantum chemistry. Traditionally, executing these routines efficiently forces a difficult trade-off between gate count and space overhead. While fast multiplication constructions inspired by classical Toom-Cook methods can reduce gate counts, reconciling them with quantum reversibility typically requires storing massive amounts of intermediate data. This often creates a space penalty that scales linearly with the input size.
Unifying Multiplication Through a Single Construction
The study, published on the arXiv preprint server by David Halpenny, Adithya Sireesh, and Petros Wallden from the University of Edinburgh, introduces a unified framework that combines classical and quantum multipliers with standard and modular integer arithmetic. Central to their approach is a fast controlled and parameterized version of the quantum Fourier transform that operates entirely without auxiliary helper qubits. By blending this transform with phase-encoded fast integer multiplication subroutines, the authors constructed circuits capable of handling modular multiplication, standard multiplication, and modular inversion with remarkable space efficiency.
For modular multiplication of integers modulo a power of two, the team demonstrated that calculations can be executed using $O(n^{1+\epsilon})$ gates and zero ancilla qubits for any $\epsilon > 0$. This performance holds whether the multiplier is a classical constant or an active quantum register. Standard integer multiplication achieves similar subquadratic scaling, requiring either zero ancillas for classical values or a sublinear number of clean ancillas for quantum multipliers.
Achieving Ancilla-Free Modular Inversion
Extending beyond basic multiplication, the researchers tackled the more challenging problem of in-place modular inversion modulo a power of two. Inverting a quantum integer without destroying superposition usually demands extensive workspace. However, the authors established an iterative strategy derived from classical Newton-Hensel iteration.
By leveraging partial inverses and doubling the number of precision bits across recursive steps, the new inversion algorithm attains an asymptotic upper bound of $O(m^{1+\epsilon})$ gates while using a flexible number of clean ancillas ranging from zero up to $m - 1$. When zero ancillas are utilized, the circuit still maintains its fast asymptotic gate count by adjusting the frequency of modular multiplication and addition calls.
These theoretical advances point toward highly optimized quantum subroutines that can execute inside heavily resource-constrained architectures. Because fault-tolerant quantum computers will likely operate under strict physical qubit budgets, techniques that eliminate auxiliary registers without sacrificing circuit speed will be vital for scaling future algorithms.
The study was posted to the arXiv preprint server on November 19, 2026.
This article has been fact checked for accuracy, with information verified against reputable sources. Learn more about us and our editorial process.
Last reviewed on .
Article history
- Latest version
Reference(s)
- Halpenny, David. “Fast, in-place, and ancilla-free quantum algorithms for integer multiplication and inversion.” arXiv.org <http://arxiv.org/abs/2611.26605v1>.
Cite this page:
- Posted by Nida Rehman