pith. machine review for the scientific record. sign in

arxiv: 2604.09847 · v1 · submitted 2026-04-10 · 🪐 quant-ph

Recognition: unknown

A Polylogarithmic-Depth Quantum Multiplier

Fred Sun , Anton Borissov
Authors on Pith no claims yet

Pith reviewed 2026-05-10 17:27 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum multiplicationClifford plus Tlow-depth circuitspolylogarithmic depthfault-tolerant quantum computingbinary adder treepartial products
0
0 comments X

The pith

Quantum circuits multiply n-bit integers in O(log squared n) depth using partial-product copying and adder trees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives a quantum algorithm to multiply two n-bit integers whose total circuit depth and T-depth are both bounded by O(log squared n). It builds the product by first generating all partial products through indicator-controlled copying, then summing those products in a binary tree of adders that adds logarithmic depth per level. The construction uses only O(n squared) gates and ancilla qubits. A reader would care because multiplication is a core subroutine in quantum algorithms, and lowering depth reduces the number of error-correction rounds needed for fault tolerance. The authors state that this yields the lowest T-depth known for any Clifford-plus-T multiplier.

Core claim

We present a quantum algorithm for multiplying two n-bit integers with overall circuit depth and T-depth both bounded by O(log squared n), while using O(n squared) 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-depth among all multiplication algorithms using the Clifford plus T model.

What carries the argument

Indicator-controlled copying to generate partial products, followed by a binary adder tree that performs parallel accumulation at each level.

If this is right

  • Multiplication becomes a polylog-depth primitive rather than a linear-depth bottleneck in quantum arithmetic.
  • The T-count and T-depth remain low enough to make large-scale fault-tolerant algorithms more practical.
  • Any quantum algorithm whose runtime is dominated by multiplication can inherit the same polylog depth scaling.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same controlled-copying-plus-tree pattern could be adapted to modular multiplication or squaring with only constant-factor changes in depth.
  • Classical circuit simulators could verify the claimed depth for n up to a few dozen bits, providing an immediate empirical check.
  • If the depth bound is tight, it would set a new target for lower bounds on the T-depth of arithmetic in the Clifford-plus-T model.

Load-bearing premise

The indicator-controlled copying for partial products and the binary adder tree can be realized with the claimed O(log squared n) depth bounds in the Clifford plus T gate set without hidden linear or higher overheads.

What would settle it

An explicit gate-by-gate construction of the circuit for n equals 8 or n equals 16 that requires depth larger than a small constant times log squared n would show the bound does not hold.

Figures

Figures reproduced from arXiv: 2604.09847 by Anton Borissov, Fred Sun.

Figure 1
Figure 1. Figure 1: FIG. 1. Implementation for fast-copying of 8 registers. The [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. High-level circuit diagram for a quantum adder at [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Explicit multiplication of 4-bit integers. According to Claim 2, each partial sum has at most [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. 4-bit integer Parallel Adder Tree Example. [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
read the original abstract

We present a quantum algorithm for multiplying two $n$-bit integers with overall circuit depth and $T$-depth both bounded by $O(\log^{2} n)$, while using $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$-depth among all multiplication algorithms using the Clifford + $T$ model. By optimizing both circuit depth and $T$-depth, our construction advances the practical feasibility of large-scale fault-tolerant quantum algorithms.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The manuscript presents a quantum circuit construction for multiplying two n-bit integers. Partial products are generated via indicator-controlled copying of the multiplicand, and these O(n²) terms are summed using a binary adder tree. The central claim is that both total circuit depth and T-depth are O(log² n) while using O(n²) gates and ancilla qubits in the Clifford+T model, asserted to be the lowest T-depth among known multiplication algorithms.

Significance. If the depth bounds are rigorously established, the result would advance quantum arithmetic by providing a polylogarithmic-depth multiplier with optimized T-count, which is relevant for reducing overhead in fault-tolerant implementations of algorithms such as Shor's or quantum linear systems solvers. The reliance on standard primitives (controlled copying and tree summation) is a methodological strength that could facilitate adoption if the T-depth analysis holds.

major comments (2)
  1. Abstract and construction outline: the claimed O(log² n) T-depth for the overall circuit rests on the assertion that indicator-controlled copying contributes constant T-depth and that each level of the binary adder tree (log(n²) = O(log n) levels) performs n-bit addition with O(log n) T-depth. No explicit T-depth recurrence, gate count per adder, or ancilla management analysis is supplied to confirm the absence of hidden linear factors from multi-controlled gates or carry propagation in the Clifford+T set.
  2. Abstract: the manuscript states that the design uses 'standard quantum primitives' but supplies neither circuit diagrams for the controlled-copy operation nor a breakdown of how the binary tree summation avoids Ω(n) T-depth per addition (as occurs in ripple-carry adders). Without this, the central polylogarithmic claim cannot be verified from the given information.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the opportunity to respond to the referee's report on our manuscript arXiv:2604.09847. We address each of the major comments below and will revise the manuscript accordingly to provide the requested clarifications and details.

read point-by-point responses

  1. Referee: Abstract and construction outline: the claimed O(log² n) T-depth for the overall circuit rests on the assertion that indicator-controlled copying contributes constant T-depth and that each level of the binary adder tree (log(n²) = O(log n) levels) performs n-bit addition with O(log n) T-depth. No explicit T-depth recurrence, gate count per adder, or ancilla management analysis is supplied to confirm the absence of hidden linear factors from multi-controlled gates or carry propagation in the Clifford+T set.

    Authors: We thank the referee for this detailed comment. Our construction relies on parallel execution of the indicator-controlled copying, which uses a constant T-depth circuit (T-depth 2 after standard decomposition into Clifford+T gates) across all partial products. The binary adder tree consists of O(log n) levels, where each level performs additions using a quantum adder with O(log n) T-depth, such as those based on parallel carry computation that avoid sequential propagation. This yields the O(log² n) bound without linear factors, as the multi-controlled operations are decomposed to constant depth and carry is handled in logarithmic depth. However, we agree that an explicit recurrence and analysis was not provided in sufficient detail. We will include a new subsection with the T-depth recurrence relation, per-adder gate counts, and ancilla qubit management in the revised version. revision: yes

  2. Referee: Abstract: the manuscript states that the design uses 'standard quantum primitives' but supplies neither circuit diagrams for the controlled-copy operation nor a breakdown of how the binary tree summation avoids Ω(n) T-depth per addition (as occurs in ripple-carry adders). Without this, the central polylogarithmic claim cannot be verified from the given information.

    Authors: The controlled-copy is a standard operation implemented via parallel controlled-NOT gates controlled by the indicator bits, which has constant T-depth. The summation uses a binary tree of adders, each avoiding Ω(n) T-depth by employing a logarithmic-depth adder construction rather than ripple-carry. We recognize that the absence of diagrams and explicit breakdown makes verification difficult from the text alone. In the revision, we will add circuit diagrams for the controlled-copy operation and a detailed breakdown of the T-depth for the adder tree to clearly demonstrate how the polylogarithmic bound is achieved. revision: yes

Circularity Check

0 steps flagged

No circularity: direct construction from standard primitives

full rationale

The paper describes an explicit construction: partial products are generated by indicator-controlled copying and summed via a binary adder tree. The O(log² n) depth and T-depth bounds are asserted to follow from the tree having O(log n) levels with each level using a logarithmic-depth adder in the Clifford+T gate set. No equations reduce the claimed bound to a fitted parameter, self-referential definition, or load-bearing self-citation; the derivation remains a standard algorithmic composition without the enumerated circular patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The construction rests on standard quantum circuit assumptions; no free parameters, new entities, or ad-hoc axioms are visible in the abstract.

axioms (1)
  • domain assumption Standard Clifford+T gate set and quantum circuit model allow logarithmic-depth parallel controlled copies and adder trees.
    Invoked implicitly when claiming the depth bounds for the described operations.

pith-pipeline@v0.9.0 · 5394 in / 1185 out tokens · 68203 ms · 2026-05-10T17:27:44.749006+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 8 canonical work pages

  1. [1]

    Modified QCLA Since the representation of|xy⟩has 2nqubits, a naive implementation of each adder in the parallel adder treecan be represented with ev- ery partial sum using 2nqubits, introducing leading and trailing zeros to account for shifts by powers of

  2. [2]

    Let us now discuss how to compute the right-hand side of Eq

    Our modified QCLA avoids trivial sums with these leading/trailing zeros. Let us now discuss how to compute the right-hand side of Eq. (9). Recall that multiplying an integer by a power of 2, say 2 k, is equivalent to a bit-shift to the left bykbits. This means the least significant 2 d−1 qubits of α(d−1,2r) and the most significant 2d−1 qubits of α(d−1,2r...

  3. [3]

    This subsection provides an efficient approach to uncom- pute ancillas corresponding to intermediate partial sums produced by theparallel adder tree

    Efficient Parallel Adder Tree Uncomputation As mentioned in the introduction, this work uses clean ancillas, and so each submodule needs to be uncomputed. This subsection provides an efficient approach to uncom- pute ancillas corresponding to intermediate partial sums produced by theparallel adder tree. As shown in Fig. 2, each adder leaves its input regi...

  4. [4]

    We exploit this property to reuse ancillas across lay- ers of the tree

    Qubit-Efficient Parallel Adder Tree Forn-qubit addition, the original QCLA uses at most nancillary qubits for computation and is designed such that these qubits are reset to|0⟩at the end of the adder [8]. We exploit this property to reuse ancillas across lay- ers of the tree. As will be discussed in the next sec- tion, thefast copyprocedure is uncomputed ...

  5. [5]

    We consider the contribution of each stage of the modified adder

    Depth and Size Analysis In this section, we analyze the depth and gate cost of theparallel adder tree. We consider the contribution of each stage of the modified adder. Consider the adder at depthd, with inputs α(d−1,2r) , α(d−1,2r+1) . As mentioned earlier, the suffix copyingstage can be implemented by reusing the least significant 2 d−1 qubits of α(d−1,...

  6. [6]

    P. W. Shor, Polynomial-time algorithms for prime factor- ization and discrete logarithms on a quantum computer, SIAM Journal on Computing26, 1484–1509 (1997)

    1997

  7. [7]

    Pavlidis and D

    A. Pavlidis and D. Gizopoulos, Fast quantum modu- lar exponentiation architecture for shor’s factoring algo- rithm, Quantum Info. Comput.14, 649–682 (2014)

    2014

  8. [8]

    A. M. Childs, R. Kothari, and R. D. Somma, Quantum algorithm for systems of linear equations with exponen- tially improved dependence on precision, SIAM Journal on Computing46, 1920–1950 (2017)

    1920

  9. [9]

    A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum al- gorithm for linear systems of equations, Physical Review Letters103, 10.1103/physrevlett.103.150502 (2009)

    work page doi:10.1103/physrevlett.103.150502 2009

  10. [10]

    D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Simulating hamiltonian dynamics with a truncated taylor series, Physical Review Letters114, 10.1103/physrevlett.114.090502 (2015)

    work page doi:10.1103/physrevlett.114.090502 2015

  11. [11]

    S. Wang, X. Li, W. J. B. Lee, S. Deb, E. Lim, and A. Chattopadhyay, A comprehensive study of quantum arithmetic circuits (2024), arXiv:2406.03867 [quant-ph]

    work page arXiv 2024

  12. [12]

    S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P. Moulton, A new quantum ripple-carry addition circuit (2004), arXiv:quant-ph/0410184 [quant-ph]

    work page Pith review arXiv 2004

  13. [13]

    T. G. Draper, S. A. Kutin, E. M. Rains, and K. M. Svore, A logarithmic-depth quantum carry-lookahead adder (2004), arXiv:quant-ph/0406142 [quant-ph]

    work page arXiv 2004

  14. [14]

    Ruiz-Perez and J

    L. Ruiz-Perez and J. C. Garcia-Escartin, Quantum arith- metic with the quantum fourier transform, Quantum Information Processing16, 10.1007/s11128-017-1603-1 (2017)

    work page doi:10.1007/s11128-017-1603-1 2017

  15. [15]

    Gidney, A classical-quantum adder with constant workspace and linear gates (2025), arXiv:2507.23079 [quant-ph]

    C. Gidney, A classical-quantum adder with constant workspace and linear gates (2025), arXiv:2507.23079 [quant-ph]

    work page arXiv 2025

  16. [16]

    Selinger, Quantum circuits oft-depth one, Phys

    P. Selinger, Quantum circuits oft-depth one, Phys. Rev. A87, 042302 (2013)

    2013

  17. [17]

    M. Amy, D. Maslov, M. Mosca, and M. Roetteler, A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Sys- tems32, 818 (2013)

    2013

  18. [18]

    Mu˜ noz-Coreas and H

    E. Mu˜ noz-Coreas and H. Thapliyal, Quantum circuit design of a t-count optimized integer multiplier, IEEE Transactions on Computers68, 729 (2019)

    2019

  19. [19]

    arXiv preprint arXiv:1706.03419 , year=

    A. Parent, M. Roetteler, and M. Mosca, Improved re- versible and quantum circuits for karatsuba-based integer multiplication (2017), arXiv:1706.03419 [quant-ph]

    work page arXiv 2017

  20. [20]

    D. S. C. Putranto, R. W. Wardhani, H. T. Larasati, and H. Kim, Space and time-efficient quantum multiplier in post quantum cryptography era, IEEE Access11, 21848 (2023)

    2023

  21. [21]

    J. Nie, Q. Zhu, M. Li, and X. Sun, Quantum circuit design for integer multiplication based on sch¨ onhage–strassen algorithm, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Sys- tems42, 4791 (2023)

    2023