A Logarithmic-Depth Quantum Multiplier

The gist The authors present a quantum algorithm for multiplying two n-bit integers with overall circuit depth and T-depth both bounded by O(log2 n), while using O(n 2) gates and ancillary qubits.

Introduction and Motivation

Quantum arithmetic is a fundamental building block in many quantum algorithms, most notably the modular exponentiation component of Shor’s factoring algorithm [1, 2]. Efficient implementations of elementary arithmetic operations, eg. addition and multiplication, play a critical role in the optimization of large-scale quantum circuits [6–10]. 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 [11, 12]. The paper studies the multiplication of two nbit natural numbers and presents a simple and modular quantum multiplication algorithm that achieves O(log2 n) depth and T-depth, making it the fastest known multiplication circuit constructed entirely from standard Clifford+T primitives [arXiv:2604.09847v1].

Related Work Comparison

The paper compares their construction against representative constructions surveyed by Wang et al. [6], which include shift-and-add (schoolbook) multiplication, Karatsuba’s algorithm, Toom–Cook multiplication, and divide-and-conquer approaches such as the quantum Schönhage–Strassen algorithm [13–16]. The shiftand-add multiplication method uses Toffoli gates and controlled adders to directly construct the standard schoolbook multiplication procedure [13], which has quadratic Tdepth and T-count but requires only O(n) ancillary qubits [TABLE I]. Karatsuba’s algorithm and the Toom–Cook multiplication algorithm reduce asymptotic gate complexity by recursively decomposing large multiplications into smaller subproblems [14, 15]. Nie et al. [16] introduce the quantum Schönhage–Strassen algorithm, which achieves O(log2 n) depth and O(n log n log log n) T-count by employing a recursive structure based on the Fast Fourier Transform [TABLE I]. The authors 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 [arXiv:2604.09847v1].

Algorithm Structure

The algorithm is structured around representing the product as xy = yn−1(2n−1x) + · · · + y1(2x) + y0x [Equation (3)]. The computation involves three main submodules:

1. Fast Copy: This subroutine produces n computational basis copies of an n-qubit quantum register in O(log n) depth, using O(n 2) ancillary qubits [Algorithm 1]. It is used to create n copies of both x⟩ and y⟩ to maximize the amount of parallel operations that can be performed, thereby optimizing the circuit depth [Section II B].

2. Partial Products: This subroutines computes all partial products, α(0,i) = yix, by applying conditional copy on all pairs y(i) and x(i) in parallel to produce all partial products of x⟩ and y⟩ [Algorithm 2]. This contributes a T-depth of 1 despite having n Toffoli gates [Section II C].

3. Parallel Addition of n Terms: This subsubsection introduces the parallel adder tree, which computes the sum of all partial products weighted with powers of two, equivalent to the product xy⟩ = α(0,0) + 2α(0,1) + · · · + 2n−1α(0,n-1) [Section II D]. This is organized in a tree-like fashion using modified versions of Draper et al.’s Quantum Carry Lookahead Adder (QCLA) [Section II D].

Resource Cost Analysis

The concrete resource costs for the overall Fast Quantum Multiplication Algorithm are summarized in Table III [Table III]. The total circuit depth is 3 log2 n + 17 log n + 20 [TABLE III], and the total T-depth is 3 log2 n + 7 log n + 14 [TABLE III]. The total gate count is at most 16n squared + 2n log n, and the total ancillary qubit count required is exactly O(n 2) [TABLE III].

Conclusion

The paper demonstrates how parallelization techniques can be leveraged to reduce the overall circuit depth and T-depth to O(log2 n) while maintaining reasonable qubit overhead and gate complexity. This construction is simple and modular, enabling straightforward implementation, analysis, and integration into larger quantum computing applications [Section IV]. These optimizations are particularly significant in the fault-tolerant setting, where T-depth is an especially important cost function [Section I]. Future work may explore further reductions in T-depth through improved Quantum Carry Lookahead Adder constructions or alternative parallel addition schemes [Section IV].

1. For large-scale fault-tolerant quantum algorithms, improve modular exponentiation components in Shor's factoring algorithm by implementing multiplication with a circuit depth and T-depth bounded by O(log2 n). This allows for faster execution of quantum arithmetic operations in applications such as Hamiltonian simulations and HHL algorithms.

2. Implement faster integer multiplication within quantum circuits using the fast copy subroutine, which produces n computational basis copies of an n-qubit quantum register in O(log n) depth. This parallelization maximizes the amount of parallel operations that can be performed, thereby optimizing circuit depth.

3. Develop a practical implementation for large-scale integer multiplication by utilizing a parallel adder tree structure, achieving a depth and Toffoli depth of 3 log2 n+O(log n) while maintaining resource costs below the quadratic bounds of previous methods. This provides a more feasible construction for moderately large input sizes.

4. Optimize the overall resource cost profile for quantum multiplication by employing an efficient parallel adder tree uncomputation procedure, ensuring that the total number of ancillas required by the parallel adder tree, including uncomputation, is strictly less than 2n squared. This reduces the qubit overhead compared to naive implementations while preserving desirable logarithmic depth.

We present a quantum algorithm for multiplying two n-bit integers with overall circuit depth and T-depth both bounded by O(n), while using O(n 2) gates and ancillary qubits. Our construction generates partial products via indicator-controlled copying and adds them using a tree of reversible 3-to- 2 adders followed by one quantum carry-lookahead adder. Building on the carry-save adders of Kim et al., we combine full input fanout, workspace reuse, and phase-corrected gate implementations to reduce T-depth. We provide explicit circuit constructions, proofs of correctness, and concrete closed-form resource bounds.