Quantum computing · Theory (AI-assisted)

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

David Halpenny, Adithya Sireesh, Petros Wallden

arXiv:2611.26605v1 ↗PDF ↗Submitted 19 November 2026

Question
In-place arithmetic overwrites its input with the output. The generic recipe (compute out of place, swap, uncompute the inverse) needs a second \(n\)-qubit register. The in-place multipliers that use no ancillas at all are quadratic in gate count. Kahanamoku-Meyer and Yao recently showed that out-of-place multiplication needs only \(O(n^{1+\epsilon})\) gates and no ancillas. Can in-place multiplication, and in-place inversion modulo \(2^n\), be both subquadratic and essentially ancilla-free?
Result
For arithmetic modulo \(2^n\), the answer is yes. In-place multiplication \(\ket z\mapsto\ket{az\bmod2^n}\) by an odd classical \(a\), and \(\ket x\ket z\mapsto\ket x\ket{xz\bmod2^n}\) by an odd quantum \(x\), use \(O(n^{1+\epsilon})\) gates for any \(\epsilon>0\) and no ancillas. Standard multiplication \(\ket0_m\ket z_n\mapsto\ket{az}_{m+n}\) needs no ancillas for any non-zero classical \(a\). For a non-zero quantum \(x\) it needs \(\lceil\log_2m\rceil\) ancillas, and none when \(x\) is odd. In-place inversion modulo \(2^n\) also uses \(O(n^{1+\epsilon})\) gates, with any number \(s\) of ancillas from 0 to \(n-1\); more ancillas mean fewer multiplications. At \(m=256\) bits, 0, 8, 32 or 128 ancillas need 43, 27, 15 or 3 modular multiplications. The multiplications by classical constants have depth \(O(n\log n)\). Every multiplication follows from one theorem, which computes \(2^mbw^\alpha x+cw^\beta y\bmod2^{t+m}\) in place for odd \(b\), \(c\) and \(w\).

The paper in detail

Many quantum algorithms use arithmetic as a subroutine and then have to uncompute it. Computing in place, \(\ket x\mapsto\ket{f(x)}\), avoids storing input and output side by side. The standard way to get an in-place circuit from out-of-place ones (compute \(f\), swap the registers, run the inverse of \(f^{-1}\) backwards) holds both values at once and so needs \(n\) extra qubits. The known in-place multipliers without ancillas are quadratic in gate count. Out of place, the fast recursive multiplication algorithms from classical computing (Karatsuba, Toom–Cook) were long thought to need linear workspace on a quantum computer. Kahanamoku-Meyer and Yao settled that question by computing products in the phase, \(\ket y\ket z\mapsto e^{2\pi i\phi yz}\ket y\ket z\), with \(O(n^{1+\epsilon})\) gates and no ancillas.

The paper's main theorem multiplies in the Fourier basis. A parametrised QFT with odd parameter \(b\), optionally controlled by a quantum odd \(w\), moves the high part \(x\) of the register into the Fourier basis with the multiplier built into its phases. A phase multiplication couples it to the low part \(y\). A second parametrised QFT does the same for \(y\). The accumulated phases are exactly those of the Fourier transform of \(2^mbw^\alpha x+cw^\beta y\), so a standard inverse QFT writes that number into the same qubits. The new ingredient is a fast, ancilla-free version of the controlled parametrised QFT. The authors also extend the Kahanamoku-Meyer–Yao multipliers to registers of different sizes, and give a linear-depth version without ancillas.

Choosing the parameters gives the operations in the paper's Table 1. Splitting \(z=2^mx+y\) with \(b=c=a\) gives in-place multiplication modulo \(2^n\) by an odd constant, or by an odd quantum integer \(w\) when the QFTs are controlled. For standard multiplication into an enlarged register, the even part of the multiplier is handled separately. Remove the trailing zeros of \(a\) (classically), multiply by the odd part, and shift back. For a quantum multiplier the trailing-zero count is computed into \(\lceil\log_2m\rceil\) ancillas and the shifts are controlled. Variants write the product onto idle qubits in unknown states, so that the output register does not have to be clean.

For inversion, an odd \(x\) is turned in place into a pair \((z,y)\) with \(xy\equiv1+2^hz\pmod{2^m}\), stored in the qubits that held \(x\). A Newton–Hensel step then doubles \(h\) using six modular multiplications and four additions, and once \(2h\ge m\) one more multiplication yields \(x^{-1}\). Ancillas only speed up the start: with \(s\) of them the iteration starts at \(h=s\) rather than \(h=1\) (or \(h=3\) with a cheap trick). The open questions are depth bounds for quantum multipliers, moduli that are not powers of two, and concrete resource counts for a finite gate set.

Transferable methods

  1. Multiplying in the Fourier basis

    Overwriting \(z\) with \(az\) needs a reversible path that never holds both. The Fourier basis provides one. Multiplication by an odd number is a permutation of \(\mathbb Z_{2^n}\), so a QFT whose phases carry a factor \(a\) is still unitary. Phases add, so separate contributions of the high and low parts of the input can be accumulated one after another, each from a register the previous step has already consumed. An inverse QFT then reads off the total.

    The parametrised QFT is \(\mathbf{QFT}_{0,n}(\phi)\ket y=2^{-n/2}\sum_ze^{2\pi i\phi yz/2^n}\ket{\bar z}\), where \(\bar z\) is bit-reversed. For odd \(\phi\) this is the ordinary QFT applied to \(\ket{\phi y\bmod2^n}\), so it is unitary. For even \(\phi\) two inputs collide. Apply \(\mathbf{QFT}(b)\) to \(\ket x_t\), a phase \(e^{2\pi i\,cvy/2^{t+m}}\) between the Fourier index \(v\) and \(\ket y_m\), and \(\mathbf{QFT}(c)\) to \(\ket y_m\). The three phases combine (Eq. (2.8)): \[\frac{bxv}{2^t}+\frac{cvy}{2^{t+m}}+\frac{cyz}{2^m}\equiv\frac{(2^tz+v)(2^mbx+cy)}{2^{t+m}}\pmod1.\] Since \((z,v)\mapsto2^tz+v\) is a bijection onto \(\mathbb Z_{2^{t+m}}\), the state is the Fourier transform of \(\ket{2^mbx+cy\bmod2^{t+m}}\), and an inverse QFT leaves exactly that. The dropped term \(2^{t+m}bxz/2^{t+m}\) is an integer.

    In-place multiplication modulo \(2^n\) by odd \(a\) takes \(t=\lceil n/2\rceil\), \(m=\lfloor n/2\rfloor\), \(z=2^mx+y\) and \(b=c=a\): \[2^max+ay=a(2^mx+y)=az\pmod{2^n}.\] The cost is that of the subroutines. The phase multiplications use Toom–Cook-style recursion, splitting each register into \(k\) pieces and evaluating at \(2k-1\) points, with gate count \(O(n^{\log_k(2k-1)})\), which approaches \(n^{1+\epsilon}\) as \(k\) grows (editorial gloss on the review in Appendix A). Controlling everything by a quantum \(w\) turns the phase products into triple products \(\phi\bar yzw\), which the same recursion handles. The editorial simulation of the four steps confirmed the identity on all tested inputs.

    How to reuse it

    Any affine map \(z\mapsto az+c\) over \(\mathbb Z_{2^n}\) with odd \(a\), or a composition of such maps, can be implemented in place this way, and fast phase multiplication makes it subquadratic. The construction also suits pipelines whose registers already sit in a Fourier basis, such as QFT-based adders, phase-estimation post-processing and lattice-style quantum factoring circuits, where an extra basis change costs nothing.

  2. Hensel lifting with the error term stored in place

    Reversible inversion is hard because the obvious algorithms keep a history. Newton's iteration for the inverse modulo \(2^m\) avoids this if the register always holds a pair \((z,y)\) whose relation to \(x\) is invariant. Each step doubles the number of correct low bits of \(y\) and shrinks \(z\), using only multiplications and additions that are themselves in place. The input is never stored; it is implicit in the invariant.

    Keep the invariant \(xy\equiv1+2^hz\pmod{2^m}\), with \(y\) on \(h\) qubits and \(z\) on \(m-h\) qubits. The Newton step \(y'=y(2-xy)\) gives (editorial derivation) \[xy'=(1+2^hz)(1-2^hz)=1-2^{2h}z^2\equiv1\pmod{2^{2h}},\] so \(y'\) is the inverse modulo \(2^{2h}\), and a new \(z'\) on \(m-2h\) qubits restores the invariant. Once \(2h\ge m\), \[x\,(y-2^hyz)=(1+2^hz)(1-2^hz)\equiv1\pmod{2^m}\] because \(2^{2h}\equiv0\), so multiplying the \(z\)-register by \(-y\) leaves \(\ket{x^{-1}}_m\) in place. With no ancillas the iteration starts from \(h=1\), \(y=1\), \(z=(x-1)/2\), which is just a relabelling of the bits of \(x\). Remark 5.5 reaches \(h=3\) cheaply, using \(y=x\bmod8\), which is its own inverse modulo 8.

    Lemma 5.1 starts the iteration from \(s\) ancillas. The low \(s\) bits of \(x^{-1}\) are the inverse of the low \(s\) bits of \(x\), so they can be written out with one modular multiplication. One more multiplication turns the input into the pair \((z,y)\) with \(h=s\). The number of multiplications is then \[2\,[s>0]+6\,\Bigl\lceil\log_2\frac m{\max(1,s)}\Bigr\rceil-6+1\quad\text{(for }m\text{ a power of two)},\] which is 43, 27, 15 and 3 at \(m=256\) for \(s=0,8,32,128\), the values of Figure 2. Each multiplication costs \(O(m^{1+\delta})\) and there are \(O(\log m)\) of them, so the total stays \(O(m^{1+\epsilon})\).

    How to reuse it

    Storing the current error of an iterative method in the register it replaces is a general way to make lifting and refinement algorithms reversible without history. Candidates include division and square roots modulo \(2^n\), \(p\)-adic lifting in number-theoretic subroutines, and fixed-point reciprocal or square-root iterations used in quantum linear-algebra pipelines.

Source: Section 2 (Eqs. (2.1)–(2.3), Lemmas 2.1–2.4, Theorem 2.5 and its proof, Eqs. (2.5)–(2.11)); Section 3 (Theorems 3.1, 3.3); Section 5 (Lemma 5.1, Theorems 5.2 and 5.4, Remark 5.5, Figure 2). Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. The results show that the most space-efficient form of multiplication, writing the output over the input with no workspace, does not force quadratic gate counts. Two primitives are reusable: a fast controlled and parametrised quantum Fourier transform that needs no ancillas, and a Newton–Hensel inversion that stores its own error term in the register. Arithmetic dominates the cost of many quantum algorithms, and where qubits are scarcer than gates, removing an \(n\)-qubit work register matters.

Limitations. All costs are asymptotic in an abstract circuit model with exact arbitrary rotations, unit cost per gate and all-to-all connectivity. The constants depend on the recursion parameters, and no finite-size or fault-tolerant resource estimate is given, including the cost of synthesising the rotations. Only moduli that are powers of two are covered. Arbitrary moduli, which Shor-type modular exponentiation needs, are open. Depth for quantum multipliers is bounded only by the gate count. Multiplication by zero is not unitary and must be handled separately. The authors used GPT-6 Astra and GPT-6.1 Sol for literature search and proofreading, and to suggest proof techniques for Lemmas 2.1 and 5.3.

Description based on the full arXiv HTML of v1, read 2026-11-22: Sections 1–6, including the proof of Theorem 2.5, Theorems 3.1–3.6, 4.3 and 4.5, Lemma 5.1, Theorems 5.2 and 5.4 and Remark 5.5. The recursive phase multipliers, the parametrised QFT, the trailing-zero circuit and the proof of Lemma 5.3 in Appendices A–E were not reproduced. Editorial checks: Theorem 2.5's four steps were simulated exactly from the definitions of the parametrised QFTs and the bit-reversed phase multiplier. On 200 random instances, with register sizes up to \((s,t,m)=(2,3,3)\) and random odd \(b\), \(c\) and \(w\), every basis state went to \(\ket{2^mbw^\alpha x+cw^\beta y\bmod2^{t+m}}\) with unit amplitude. Newton–Hensel doubling followed by the final step returned \(x^{-1}\bmod2^m\) for 600 random odd \(x\) with \(m=8\), 13 and 64. The counts 43, 27, 15 and 3 at \(m=256\) follow from six multiplications per doubling plus the initial and final multiplications. The identity \((y^2-1)/8=y_1+3y_2+2y_1y_2\) of Remark 5.5 holds for \(y=1,3,5,7\).