betaFeedback

WorksPhysics and Astronomy

Fast, in-place, and ancilla-free quantum algorithms for integer multiplication and inversion

Abstract

Arithmetic operations are a fundamental building block in the design of quantum algorithms, with their implementation cost expected to have a significant impact on the viability of a wide variety of quantum applications. In this work, we present novel algorithms for a number of in-place quantum arithmetic operations that are highly efficient in terms of their space and gate count overheads compared to the current state-of-the-art. We show that in-place modular multiplication of integers, modulo a power of two, can be performed with either a classical or quantum odd multiplier using O(n1+ε)O(n^{1+ε}) gates and no ancilla qubits, for any ε>0ε>0. We then show that standard in-place integer multiplication can be performed with a non-zero classical or quantum multiplier using O(n1+ε)O(n^{1+ε}) gates for any ε>0ε>0, with no ancilla qubits required for the classical multiplier and a logarithmic number of ancilla qubits for the quantum. Using our quantum modular multiplication algorithm, we also show that in-place modular inversion, modulo a power of two, can be performed using O(n1+ε)O(n^{1+ε}) gates and no ancilla qubits, for any ε>0ε>0. To our knowledge, these are the first quantum algorithms achieving both subquadratic gate counts and sublinear ancilla counts for each of the considered in-place operations. All but one of these fast operations are optimal in terms of memory, only requiring enough space to store the output of the operation, which overwrites the input directly. We present our multiplication algorithms as consequences of a single unified theorem, which may find further application within quantum arithmetic.

Intro & Main Results

Consider an injective function f:Z2n→Z2mf : \mathbb{Z}_{2^n} \to\mathbb{Z}_{2^m}. A fundamental task across quantum algorithms research is to determine whether various injective functions like ff can be computed efficiently using quantum circuits, and if they can, at what resource cost. Gate, depth, and space requirements are the principal resources of interest and are often traded for one another. For well-studied functions, such as certain arithmetic operations, asymptotic performance improvements are highly sought after and heavily researched, due to the widespread use of these operations as subroutines in larger algorithms [1, 2, 3, 4, 5, 6, 7, 8, 9].

David Halpenny: [email protected]

Adithya Sireesh: [email protected]

Two natural approaches for computing these functions exist, typically referred to as in-place and out-of-place, illustrated (without considering potential ancillas) below:

out-of-place:∣x⟩n∣0⟩m⟼∣x⟩n∣f(x)⟩min-place:∣x⟩n∣0⟩m−n⟼∣f(x)⟩m.(1)\begin{aligned} \text{out-of-place}: \lvert x\rangle_n\lvert0\rangle_m &\longmapsto\lvert x\rangle_n\lvert f(x)\rangle_m \\ \text{in-place}: \lvert x\rangle_n\lvert0\rangle_{m-n} &\longmapsto\lvert f(x)\rangle_m . \tag*{(1)} \end{aligned}

In the context of a larger algorithm, each approach offers a distinct benefit. If the function input needs to be reused later, retaining it with an out-of-place approach is desirable. Otherwise, an in-place approach, defined by its uncomputation of the function input is preferable. In many algorithms, uncomputation is an essential component [7, 8, 9, 10, 11, 12, 13].

The standard approach for out-of-place integer multiplication in both classical and quantum settings is the schoolbook method, which can be implemented by repeatedly using an addition circuit, requiring a gate count that scales quadratically with respect to the length of the input. Fast constructions achieving subquadratic gate counts have also been developed, based on recursive multiplication algorithms from classical computing [14, 15, 16, 17, 18, 19, 20]. Until recently, it was a major open question whether the recursive nature of these constructions could be reconciled with quantum reversibility without incurring a space overhead, for the storage of intermediate computations, scaling linearly in the length of the input. This question was resolved in [20], when it was proven that out-of-place quantum integer multiplication is possible using O(n1+ϵ)O(n^{1+\epsilon}) gates and no ancilla qubits, for any ϵ>0\epsilon> 0.

It is a well-known fact that two unitaries UfU_f and UgU_g computing ff and its left-inverse gg out-of-place can be used to build an in-place algorithm for ff [21]. This is clear by considering the following sequence of operations:

∣x⟩n∣0⟩m→Uf∣x⟩n∣f(x)⟩m→SWAP∣f(x)⟩m∣x⟩n→Ug−1∣f(x)⟩m∣0⟩n.(2)\lvert x\rangle_n\lvert0\rangle_m \xrightarrow{U_f} \lvert x\rangle_n\lvert f(x)\rangle_m \xrightarrow{\mathrm{SWAP}} \lvert f(x)\rangle_m\lvert x\rangle_n \xrightarrow{U_g^{-1}} \lvert f(x)\rangle_m\lvert0\rangle_n . \tag*{(2)}

However, the space efficiency of this in-place algorithm is clearly sub-optimal, involving nn ancilla qubits for the simultaneous storage of both the function input and output, in addition to any workspace required. In contrast, an ancilla-free, in-place algorithm for computing ff is optimally space-efficient, directly overwriting the input with the function output. In-place and ancilla-free constructions for standard multiplication and modular multiplication modulo a power of two exist [22, 23, 24, 25, 26, 27] ([24] is nearly ancilla-free), all scaling quadratically with respect to the length of the input in terms of gate count.

The history of quantum instantiations for fast multiplication and the evident tension between gate and space cost motivate the following question: since in-place and ancilla-free algorithms reduce space cost maximally, might they be fundamentally prevented from being made fast?

Our Contributions. In this paper, we show that this is not the case. We present in-place and ancilla-free (in all but one of the cases we highlight) algorithms achieving subquadratic gate count for a number of quantum arithmetic operations (see Table 1).

Arithmetic OperationDomainGates GGAncillasDepth DDTheorem
∣z⟩n↦∣az mod 2n⟩n|z\rangle_n \mapsto|az \bmod2^n\rangle_na∈Z2n×a \in\mathbb{Z}_{2^n}^{\times}O(n1+ϵ)O(n^{1+\epsilon})0O(nlog⁡n)O(n \log n)Thm. 3.1
∣0⟩m∣z⟩n↦∣az⟩m+n|0\rangle_m |z\rangle_n \mapsto|az\rangle_{m+n}a∈Z2m∖{0}a \in\mathbb{Z}_{2^m} \setminus\{0\}O(n1+ϵ)O(n^{1+\epsilon})0O(nlog⁡n)O(n \log n)Thm. 3.3
∣x⟩m∣z⟩n↦∣x⟩m∣xz mod 2n⟩n|x\rangle_m |z\rangle_n \mapsto|x\rangle_m |xz \bmod2^n\rangle_nx∈Z2m×x \in\mathbb{Z}_{2^m}^{\times}O(n1+ϵ)O(n^{1+\epsilon})0≤G\leq GThm. 4.3
∣x⟩m∣0⟩m∣z⟩n↦∣x⟩m∣xz⟩m+n|x\rangle_m |0\rangle_m |z\rangle_n \mapsto|x\rangle_m |xz\rangle_{m+n}x∈Z2m×x \in\mathbb{Z}_{2^m}^{\times}O(n1+ϵ)O(n^{1+\epsilon})0≤G\leq GThm. 4.5
x∈Z2m∖{0}x \in\mathbb{Z}_{2^m} \setminus\{0\}⌈log⁡2m⌉\lceil\log_2 m\rceil≤G\leq GThm. 4.5
∣x⟩n↦∣x−1 mod 2n⟩n|x\rangle_n \mapsto|x^{-1} \bmod2^n\rangle_nx∈Z2n×x \in\mathbb{Z}_{2^n}^{\times}O(n1+ϵ)O(n^{1+\epsilon})ss≤G\leq GThm. 5.4

Table 1. Main arithmetic results. The results hold for any ϵ>0\epsilon> 0 as long as m=O(n)m = O(n). The first two results are for multiplication (modular and standard) of a quantum register by a classical multiplier. The next two are for multiplication (modular and standard) between two quantum registers. The fifth result is for modular inversion of a quantum register. The ancilla count ss is a parameter in our construction that determines the exact cost of the algorithm. For all ss in the range 0≤s≤n−10 \leq s \leq n - 1 the claimed asymptotic gate count holds. We work in the abstract quantum circuit model.

In more detail, we show that integer multiplication modulo a power of two can be performed in-place on a quantum register between two O(n)O(n)-bit integers using O(n1+ϵ)O(n^{1+\epsilon}) gates and no ancilla qubits, for any ϵ>0\epsilon> 0. The multiplier can be either a classically chosen value a∈Z2na \in\mathbb{Z}_{2^n} (Theorem 3.1) or a quantum state ∣x⟩m\lvert x\rangle_m for x∈Z2mx \in\mathbb{Z}_{2^m} and m=O(n)m = O(n) (Theorem 4.3).

We then show that standard integer multiplication can be performed in-place on a quantum register between two O(n)O(n)-bit integers using O(n1+ϵ)O(n^{1+\epsilon}) gates for any ϵ>0\epsilon> 0, and with a multiplier-dependent ancilla count (Theorems 3.3 and 4.5). When the multiplier is a classically chosen value a∈Z2m∖{0}a \in\mathbb{Z}_{2^m} \setminus\{0\} or a quantum state ∣x⟩m\lvert x\rangle_m with x∈Z2m×x \in\mathbb{Z}_{2^m}^{\times} and m=O(n)m = O(n), no ancillas are required, and when x∈Z2m∖{0}x \in\mathbb{Z}_{2^m} \setminus\{0\}, just ⌈log⁡2m⌉\lceil\log_2 m\rceil ancillas are required. Note that in-place multiplication by zero is not a unitary operation (see Remark 4.9 for details on handling this case). We also prove that our multiplication algorithms involving a classical value have O(nlog⁡n)O(n \log n) circuit depth.

Finally, we show that modular inversion of x∈Z2n×x \in\mathbb{Z}_{2^n}^{\times} can be performed in-place on a quantum register using O(n1+ϵ)O(n^{1+\epsilon}) gates and ss ancilla qubits, for any ϵ>0\epsilon> 0 and 0≤s≤n−10 \leq s \leq n - 1 (Theorem 5.4). The ancilla count ss is a parameter affecting the true gate count of the algorithm and does not impact the stated asymptotic upper bound, meaning that our fast modular inversion algorithm can be ancilla-free.

To the best of our knowledge, these are the first known quantum algorithms achieving both subquadratic gate counts and sublinear ancilla counts for all of the stated in-place operations. With the exception of our algorithm for standard multiplication by ∣x⟩m|x\rangle_m for x∈Z2m∖{0}x \in\mathbb{Z}_{2^m} \setminus\{0\}, all of these results are optimal in terms of space cost.

We unify our multiplication algorithms using a single construction (Theorem 2.5) that treats quantum versus classical and modular versus standard multiplication as parameters that can be turned on and off before running the algorithm. The results that we highlight in Table 1 are therefore a selection of well-motivated operations in the context of quantum arithmetic following from this main theorem, and not an exhaustive list. We believe this main theorem of our work may help to build other fast and space-efficient arithmetic operations.

Central to our results are two subroutines: the phase-encoded fast integer multiplication operation introduced in [20], which we extend (Lemmas 2.2 and 2.3), and a fast controlled and parametrised version of the quantum Fourier transform, which to our knowledge we introduce here for the first time, and which we expect to be of independent interest (Lemma 2.4).

Motivated by highly space-constrained settings where temporarily idle qubits may be repurposed [13, 28, 29, 30], we develop variants of our standard integer multiplication algorithms which encode the (m+n)(m+n)-bit product on an idle quantum register in a potentially unknown state (Theorems 3.6 and 4.8). If used within a larger algorithm, these constructions may be even more space-efficient than the main results of this work, as they avoid initialising an mm qubit register ∣0⟩m|0\rangle_m to store the (m+n)(m+n)-bit product (see Remark 3.5 for more details).

Paper Outline

Our work is structured into four main sections. In Section 2, we introduce the fast and ancilla-free subroutines critical for this work and we present our main theorem that unifies standard and modular multiplication with classical and quantum multipliers in a single construction. We prove the cost of these subroutines in Appendices A and B, and an extension of our main theorem in Appendix E. In Section 3, we present our fast, in-place, and ancilla-free algorithms for integer multiplication with a classical multiplier, and in Section 4, we present our algorithms for multiplication with a quantum multiplier. In Section 5, we use our algorithm for modular multiplication, modulo a power of two, to construct a fast algorithm for inversion modulo a power of two. We leave the proof of some additional subroutines used in our multiplication and inversion algorithms for Appendices C and D. We conclude with a discussion in Section 6.

Conventions

Throughout this work we adopt the following conventions. A length nn bitstring is denoted xn−1⋯x0x_{n-1}\cdots x_0 and identified with the integer x=∑i=0n−12ixix = \sum_{i=0}^{n-1} 2^i x_i in Z2n\mathbb{Z}_{2^n}. The bit-reversal x0⋯xn−1x_0\cdots x_{n-1} is denoted xˉ\bar{x} and identified with ∑i=0n−12n−i−1xi\sum_{i=0}^{n-1} 2^{n-i-1}x_i. The variables w,x,y,zw, x, y, z will always refer to integers that are stored within a quantum register. We refer to these as quantum integers. The variables a,b,ca, b, c will always refer to an integer that is a classical parameter of an algorithm, chosen before the algorithm starts. We refer to this as a classical integer. We use Z2n×\mathbb{Z}_{2^n}^{\times} to refer to the multiplicative group of Z2n\mathbb{Z}_{2^n}, whose elements we identify with odd integers.

We use subscripts to denote the number of qubits contained within a quantum register and to denote the number of qubits a unitary operation is being applied to. For example, ∣x⟩n|x\rangle_n refers to an nn qubit quantum register storing the integer xx and Um,nU_{m,n} refers to a unitary transformation applied to two registers of sizes mm and nn. We use ImI_m for the identity on mm qubits. If during an algorithm, we apply an operation to just a subregister of the total register of qubits, it is understood that the rest of the qubits are receiving the identity.

Unless stated otherwise logarithms are taken base 2. We define the function tz:Z2n→Zn+1t_z : \mathbb{Z}_{2^n} \to\mathbb{Z}_{n+1} by tz(x)=log⁡(gcd⁡(x,2n))t_z(x) = \log(\gcd(x, 2^n)). This function counts the number of trailing zeroes of the bitstring xx, evaluating to nn for the zero bitstring. We use G(⋅)G(\cdot) and D(⋅)D(\cdot) to denote the gate count and depth of an operation. When solving gate and depth recurrence relations, we often implicitly apply the master theorem for divide and conquer algorithms. We use 1(P)\mathbb{1}(P) to denote an indicator function which takes the value 1 when the predicate PP is true and 0 when it is not.

We work in the abstract quantum circuit model. We assign equal cost to all elementary gates and assume that arbitrary rotation gates can be implemented exactly. We assume qubits have all-to-all connectivity and that gates acting on disjoint sets of qubits can be executed in parallel.

Main Theorem

We now develop the subroutines used in our main theorem. We present algorithms for phase-encoded integer multiplication between two or three differently sized registers and establish their gate, depth, and ancilla costs. We use these operations to develop a fast controlled and parametrised quantum Fourier transform that requires no ancilla qubits. Together, these results provide the tools needed to treat multiplication by both classical and quantum integers within a single construction, culminating in our main theorem.

Subroutines

References

  1. [1]Dave Bacon, Isaac L. Chuang, and Aram W. Harrow. Efficient quantum circuits for schur and clebsch-gordan transforms. Physical Review Letters, 97(17), October 2006.pubmed.ncbi.nlm.nih.gov/17155455
  2. [2]Sean Hallgren. Polynomial-time quantum algorithms for pell’s equation and the principal ideal problem. Journal of the ACM (JACM), 54(1):1–19, 2007.
  3. [3]Ivan Kassal, Stephen P. Jordan, Peter J. Love, Masoud Mohseni, and Alán Aspuru-Guzik. Polynomial-time quantum algorithm for the simulation of chemical dynamics. Proceedings of the National Academy of Sciences, 105(48):18681–18686, December 2008.DOI
  4. [4]Ryan Babbush, Dominic W. Berry, Jarrod R. McClean, and Hartmut Neven. Quantum simulation of chemistry with sublinear scaling in basis size. npj Quantum Information, 5(1), November 2019.DOI
  5. [5]Od​​ed Regev. An efficient quantum factoring algorithm. Journal of the ACM, 72(1):1–13, 2025.arxiv.org/abs/2308.06572
  6. [6]Nicholas C. Rubin, Dominic W. Berry, Alina Kononov, Fionn D. Malone, Tanuj Khattar, Alec White, Joonho Lee, Hartmut Neven, Ryan Babbush, and Andrew D. Baczewski. Quantum computation of stopping power for inertial fusion target design. Proceedings of the National Academy of Sciences, 121(23), May 2024.
  7. [7]Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, October 1997.
  8. [8]John Proos and Christof Zalka. Shor’s discrete logarithm quantum algorithm for elliptic curves. arXiv preprint quant-ph/0301141, 2003.DOI
  9. [9]Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, Tanuj Khattar, and Ryan Babbush. Optimization by decoded quantum interferometry. Nature, 646(8086):831–836, October 2025.
  10. [10]Od​​ed Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6):1–40, 2009.
  11. [11]Dominic W. Berry and Andrew M. Childs. Black-box Hamiltonian simulation and unitary implementation. Quant. Inf. Comput., 12(1-2):0029–0062, 2012.
  12. [12]Andris Ambainis, Loïck Magnin, Martin Roetteler, and Jeremie Roland. Symmetry-assisted adversaries for quantum state generation. In 2011 IEEE 26th Annual Conference on Computational Complexity, page 167–177. IEEE, 2011.DOI
  13. [13]Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R McClean, and Ryan Babbush. Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization. Quantum, 3:208, 2019.DOI
  14. [14]Christof Zalka. Fast versions of shor’s quantum factoring algorithm. arXiv preprint quant-ph/9806084, 1998.
  15. [15]Luis Kowada, Renato Portugal, and Celina Figueiredo. Reversible karatsuba’s algorithm. J. UCS, 12:499–511, January 2006.DOI
  16. [16]Alex Parent, Martin Roetteler, and Michele Mosca. Improved reversible and quantum circuits for karatsuba-based integer multiplication. arXiv preprint arXiv:1706.03419, 2017.arxiv.org/abs/1706.03419
  17. [17]Srijit Dutta, Debjyoti Bhattacharjee, and Anupam Chattopadhyay. Quantum circuits for Toom-Cook multiplication. Physical Review A, 98(1):012311, July 2018.DOI
  18. [18]Craig Gidney. Asymptotically efficient quantum karatsuba multiplication, 2019.arxiv.org/abs/1904.07356
  19. [19]Junhong Nie, Qinlin Zhu, Meng Li, and Xiaoming Sun. Quantum Circuit Design for Integer Multiplication Based on Schönhage-Strassen Algorithm. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 42(12):4791–4802, December 2023.
  20. [20]Gregory D Kahanamoku-Meyer and Norman Y Yao. Fast quantum integer multiplication with zero ancillas. arXiv preprint arXiv:2403.18006, 2024.
  21. [21]Charles H. Bennett. Logical reversibility of computation. IBM Journal of Research and Development, 17(6):525–532, 1973.DOI
  22. [22]Craig Gidney. Simple algorithm for multiplicative inverses mod 2ⁿ. https://algassert.com/post/1709, June 2017.
  23. [23]Rich Rines and Isaac Chuang. High performance quantum modular multipliers. arXiv preprint arXiv:1801.01081, 2018.arxiv.org/abs/1801.01081
  24. [24]Torben Ægidius Mogensen. Garbage-free reversible multiplication and division. In Jarkko Kari and Irek Ulidowski, editors, Reversible Computation, pages 253–268, Cham, 2018. Springer International Publishing.DOI
  25. [25]Raphael Seidel, Nikolay Tcholtchev, Sebastian Bock, Colin Kai-Uwe Becker, and Manfred Hauswirth. Efficient floating point arithmetic for quantum computers. arXiv preprint arXiv:2112.10537, 2021.arxiv.org/abs/2112.10537
  26. [26]Hai-Sheng Li, Ping Fan, Haiying Xia, and Gui-Lu Long. The circuit design and optimization of quantum multiplier and divider. Science China Physics, Mechanics & Astronomy, 65(6):260311, 2022.DOI
  27. [27]Ping Fan and Hai-Sheng Li. Designs of the divider and special multiplier optimizing t and cnot gates. EPJ Quantum Technology, 11(1):13, 2024.DOI
  28. [28]Craig Gidney. Factoring with n+ 2 clean qubits and n-1 dirty qubits. arXiv preprint arXiv:1706.07884, 2017.arxiv.org/abs/1706.07884
  29. [29]Thomas Häner, Martin Roetteler, and Krysta M Svore. Factoring using 2n+ 2 qubits with toffoli based modular multiplication. arXiv preprint arXiv:1611.07995, 2016.arxiv.org/abs/1611.07995
  30. [30]Harry Buhrman, Marten Folkertsma, Ian Mertz, Florian Speelman, Sergii Strelchuk, Sathyawageeswar Subramanian, and Quinten Tupker. Quantum catalytic space. arXiv preprint arXiv:2506.16324, 2025.arxiv.org/abs/2506.16324
  31. [31]Richard Cleve and John Watrous. Fast parallel circuits for the quantum fourier transform. In Proceedings 41st annual symposium on foundations of computer science, pages 526–536. IEEE, 2000.
  32. [32]NIST Digital Library of Mathematical Functions. https://dlmf.nist.gov/, Release 1.2.8 of 2026-09-15. F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds.
  33. [33]Thomas Haener, Mathias Soeken, Martin Roetteler, and Krysta M Svore. Quantum circuits for floating-point arithmetic. In International conference on reversible computation, pages 162–174. Springer, 2018.
  34. [34]Priyanka Mukhopadhyay, Alexandru Gheorghiu, and Hari Krovi. Improved quantum circuits for division. arXiv preprint arXiv:2603.18110, 2026.arxiv.org/abs/2603.18110
  35. [35]Richard P. Brent and Paul Zimmermann. Modern Computer Arithmetic, volume 18 of Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, 2010.
  36. [36]Steven A Cuccaro, Thomas G Draper, Samuel A Kutin, and David Petrie Moulton. A new quantum ripple-carry addition circuit. arXiv preprint quant-ph/0410184, 2004.DOI
  37. [37]Tanuj Khattar and Craig Gidney. Rise of conditionally clean ancillae for efficient quantum circuit constructions. Quantum, 9:1752, 2025.DOI

Paper details

vlnc:W_6bxnpmkm
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

GPT-6 Astra (bare), GPT-6.1 Sol (bare)

View statement
Looking for related papers…
Contents