A Polylogarithmic-Depth Quantum Multiplier
Fred Sun 1,2, Anton Borissov 1 · 2026
Read A Polylogarithmic-Depth Quantum Multiplier by Fred Sun 1,2, Anton Borissov 1 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-09847.txt.
Introduction
Sun and Borissov present a quantum method for n-bit integer products with log circuit depth and T-depth, using squared gate counts and spare qubits. The build makes partial products via flag copying, then sums them with a tree of two-way 3-to-2 adders plus one quantum carry-ahead adder. Building on Kim's carry-save adders, the team mixes full input fanout, workspace reuse, and phase-fixed gate builds to reduce T-depth. The paper gives exact circuit designs, proofs that they work, and closed-form resource bounds.
Catalog record
| CREATOR | Fred Sun 1,2, Anton Borissov 1 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37782 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.09847
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Polylogarithmic-Depth Quantum Multiplier Fred Sun 1,2, Anton Borissov 1 Abstract We present a quantum algorithm for multiplying two n n -bit integers with overall circuit depth and T T -depth both bounded by O ( log 2 n ) O(\log^{2}n) , while using O ( n 2 ) O(n^{2}) gates and ancillary qubits. Our construction generates partial products via indicator-controlled copying and adds them using a binary adder tree, enabling parallel accumulation with logarithmic depth overhead per level. To the best of our knowledge, our design has the lowest T T -depth among all multiplication algorithms using the Clifford + T T model. By optimizing both circuit depth and T T -depth, our construction advances the practical feasibility of large-scale fault-tolerant quantum algorithms. I Introduction Quantum arithmetic is a fundamental building block in many quantum algorithms, most notably the modular exponentiation component of Shor’s factoring algorithm 15 ; 11 , but also in scientific computing applications and numerical approximations, such as Hamiltonian simulations, the HHL algorithm for solving linear systems, and Taylor series approximations 3 ; 7 ; 2 . Efficient implementations of elementary arithmetic operations, eg. addition and multiplication, play a critical role in the optimization of large-scale quantum circuits. 16 ; 4 ; 5 ; 13 ; 6 . In fault-tolerant quantum computing, the cost of an algorithm is more accurately captured by circuit depth and, in particular, by T -depth, rather than by total gate count alone 14 ; 1 . Since non-Clifford gates dominate the overhead of fault-tolerant implementations, optimizing T -depth is often more desirable for practical performance, even at the expense of qubit count or Clifford gate depth. In this work, we study the multiplication of two n -bit natural numbers. We present a simple and modular quantum multiplication algorithm that achieves O(\log^{2}n) depth and T -depth, making it the fastest known multiplication circuit constructed entirely from standard Clifford+ T primitives. The algorithm prioritizes minimizing T -depth and overall depth, trading off a quadratic number of clean ancillary qubits and T-gates to achieve these performance improvements. I.1 Related Work Table 1: Asymptotic resource costs for quantum multiplication algorithms. Paper T -depth T -count Ancillary Qubit Count Shift-and-Add 8 O(n^{2}) O(n^{2}) O(n) Karatsuba 10 O(n^{1.158}) O(n^{\log_{2}3}) O(n^{1.427}) Toom–Cook 12 O(n^{1.0569}) O(n^{\log_{8}15}) O(n^{1.245}) Schönhage–Strassen ∗ 9 O(\log^{2}n) O(n\log n\log\log n) O(n\log n\log\log n) This work O(\log^{2}n) O(n^{2}) O(n^{2}) ∗ The quantum Schönhage–Strassen algorithm is a galactic algorithm and requires the input size to be n\geq 2^{40} 9 . Table 2: Concrete (non-asymptotic, tight upper-bounded) resource costs for quantum multiplication algorithms. ‘–’ indicates no concrete metric was provided. Paper Depth Toffoli Depth Toffoli Count Gate Count Ancillary Qubits Shift-and-Add 8 5n^{2}+2n-6 3n^{2}-14 3n^{2}-14 7n^{2}-4n+4 2n+1 Karatsuba 10 – \approx n^{1.158} 98n^{\log 3} 218n^{\log{3}} \approx n^{1.427} Toom–Cook 12 – \approx n^{1.0569} 112n^{\log_{8}15}-128n – \approx n^{1.245} Schönhage–Strassen (weaker) 9 58\log^{2}n-126\log n+806 58\log^{2}{n}+O(\log{n}) – – 13n^{1.5}+4\log n-8 This work 3\log^{2}n+17\log{n}+20 3\log^{2}n+7\log{n}+14 12n^{2}-n\log{n} 26n^{2}+2n\log{n} 3n^{2} Many quantum circuits for integer multiplication have been proposed, each with trade-offs among depth, T -count, and ancillary qubit count. In this work, we compare against representative constructions, as surveyed by Wang et al. 16 , that serve as benchmarks in fault-tolerant settings: shift-and-add (schoolbook) multiplication, Karatsuba’s algorithm, Toom–Cook multiplication, and divide-and-conquer approaches such as the quantum Schönhage–Strassen algorithm 8 ; 10 ; 12 ; 9 . The shift-and-add multiplication method, implemented by Muñoz-Coreas et al. , uses Toffoli gates and controlled adders to directly construct the standard schoolbook multiplication procedure 8 . This approach has quadratic T -depth and T -count, but requires only O(n) ancillary qubits. The quantum implementations of Karatsuba’s algorithm and the Toom–Cook multiplication algorithm reduce asymptotic gate complexity by recursively decomposing large multiplications into smaller subproblems 10 ; 12 . These approaches improve T -count and T -depth compared to shift-and-add multiplication at the tradeoff of a greater number of ancillary qubits. Nie et al. 9 introduce the quantum Schönhage–Strassen algorithm, which achieves O(\log^{2}n) depth and O(n\log n\log\log n) T -count by employing a recursive structure based on the Fast Fourier Transform. This algorithm also requires only O(n\log n\log\log n) ancillary qubits. However, the asymptotic expressions hide extremely large constant factors, making the approach practical only for very large input sizes ( n\geq 2^{40} 9 ). This paper also designed a simplified version of the Schönhage–Strassen algorithm with O(n^{1.5}) gate and qubit counts, which has more manageable coefficients and could be implemented for moderately large inputs. A tree-like solution can be applied to multiplication, using a similar method to their Quantum Carry Lookahead Adder 5 . It was later proposed that a family of circuits can optimize multiplication down to depth and Toffoli depth 8\log^{2}{n}+O(\log{n}) based on the standard textbook multiplication algorithm, such that it conducts addition in the fashion of the binary tree 9 . However, such a design has both size and number of ancillary qubits O(n^{2}) and no concrete implementation has yet been provided. Our algorithm follows this approach to achieve both a depth and Toffoli depth of 3\log^{2}{n}+O(\log{n}) through an optimized shift-and-add-based divide-and-conquer structure. In this paper, we also introduce explicit circuit constructions with detailed proofs of correctness and provide concrete (non-asymptotic, tight upper-bounded) resource-cost analyses across all submodules. Furthermore, our approach is optimized to have low constant factors in the resource costs, making it a practical solution to quantum multiplication for when circuit depth is the most important criterion. A summary of our algorithm’s resource costs is shown in Table 1 and Table 2 . The remainder of the paper is organized as follows. In Section 2, we provide the foundations for our algorithm, including the design and analysis of all submodules used. In Section 3, we explicitly provide the full fast quantum multiplication algorithm and explicitly analyze our algorithm’s depth, Toffoli depth, size, and ancilla requirements. II Preliminaries II.1 Notation Consider two n -bit positive integers, x,y . We express their binary representation as \displaystyle x \displaystyle=x_{n-1}\cdot 2^{n-1}+\dots+x_{1}\cdot 2+x_{0}, (1) \displaystyle y \displaystyle=y_{n-1}\cdot 2^{n-1}+\dots+y_{1}\cdot 2+y_{0}, (2) where n=\lfloor\log_{2}{\max{(x,y)}}\rfloor+1 , and for 0\leq i\leq n-1 , x_{i},y_{i}\in\{0,1\} . The most significant bit of x is x_{n-1} and the least significant bit is x_{0} . We structure our algorithm around the following representation of the product: \displaystyle xy \displaystyle=y_{n-1}(2^{n-1}x)+\dots+y_{1}(2x)+y_{0}x. (3) This allows us to think of each y_{i} as a binary indicator variable for whether 2^{i}x is included in the sum to compute the product. We find it useful to introduce n -bit partial products , \alpha^{(0,i)}:=y_{i}x , and we introduce partial sums defined as sums of consecutive partial products weighted with factors of 2 : \displaystyle\alpha^{(d,r)}=\sum_{k=0}^{2^{d}-1}2^{k}\alpha^{(0,r2^{d}+k)}=\left(\sum_{k=0}^{2^{d}-1}2^{k}y_{r2^{d}+k}\right)x. (4) Since it is possible to express \alpha^{(d,r)} as a product of a 2^{d} bit integer and a n bit integer, for 1\leq d\leq\lceil\log{n}\rceil , each \alpha^{(d,r)} is a n+2^{d} bit nonnegative integer. Note that the final partial sum, \alpha^{(\lceil\log n\rceil,0)} , is the desired product, xy . Throughout the paper, if we have an m -bit nonnegative integer, a=a_{m-1}2^{m-1}+\cdots+a_{0} , we shall encode it into an m -qubit register as, \displaystyle\ket{a}\equiv\ket{a_{m-1}}\cdots\ket{a_{0}}. (5) We would like to find an efficient circuit that implements the following transformation, \displaystyle\ket{x}\ket{y}\ket{0}^{\otimes 2n}\ket{0}_{anc}\xrightarrow[\hskip 16.38895pt]{}\ket{x}\ket{y}\ket{xy}\ket{0}_{anc}, (6) where \ket{x} , \ket{y} , \ket{xy} represent n , and 2n -qubit registers, defined using Eq.