A Polylogarithmic-Depth Quantum Multiplier

• URL: http://arxiv.org/abs/2604.09847v1
• Date: Fri, 10 Apr 2026 19:21:07 GMT
• Title: A Polylogarithmic-Depth Quantum Multiplier
• Abstract summary: We present a quantum algorithm for multiplying two $n$-bit integers with overall circuit depth and $T$-depth.<n>Our construction generates partial products via indicator-controlled copying and adds them using a binary adder tree.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions [8.46046792536661]
  Hamming weight maps an $n$-bit input to the number of ones it contains.<n> symmetric Boolean functions are among the most common primitives in quantum computing.<n> Efficient circuits for both problems are important for the efficiency of many quantum algorithms.
  arXiv  Detail & Related papers  (2026-08-05T09:42:03Z)
• Improved quantum circuits for division [42.76841620787673]
  We develop new fault-tolerant quantum circuits for various integer division algorithms.<n> circuits achieve an up to 76.08% and 68.35% reduction in T-count and CNOT-count.
  arXiv  Detail & Related papers  (2026-03-18T13:41:43Z)
• Asymptotically Optimal Quantum Circuits for Comparators and Incrementers [2.488003578430483]
  We present quantum circuits for comparison and increment operations that achieve anally optimal gate count of $(n)$ and depth of $(log n)$ over the Clifford+Toffoli gate set.<n>We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count.
  arXiv  Detail & Related papers  (2026-03-13T11:41:14Z)
• Prefix Sums via Kronecker Products [47.600794349481966]
  We show how to design quantum adders with $1.893log(n)+O(1)$ Toffoli depth, $O(n)$ Toffoli gates, and $O(n)$ additional qubits.<n>As an application, we show how to use these circuits to design quantum adders with $1.893log(n)+O(1)$ Toffoli depth, $O(n)$ Toffoli gates, and $O(n)$ additional qubits.
  arXiv  Detail & Related papers  (2025-12-18T08:49:18Z)
• Efficient circuits for leaf-separable state preparation [0.0]
  We present a state preparation algorithm that combines logarithmic-depth Dicke state circuits with Hamming weight encoders for efficiently preparing leaf-separable" quantum states.<n>We evaluate the performance of the algorithm by numerically simulating it on randomly generated target states with between 4 and 15 qubits.<n>These results contribute to scalable state preparation for quantum algorithms that require structured inputs such as Dicke or near-Dicke states.
  arXiv  Detail & Related papers  (2025-11-14T12:30:08Z)
• Unitary designs in nearly optimal depth [40.28216388589026]
  We construct unitary designs on qubits in circuit depth $O(log k log log n k / varepsilon)$.<n>The depth is exponentially improved over all known results in all three parameters $n$, $k$, $varepsilon$.<n>We also develop a new analytical framework for bounding errors in quantum experiments involving many queries to random unitaries.
  arXiv  Detail & Related papers  (2025-07-08T17:48:33Z)
• Depth-Efficient Quantum Circuit Synthesis for Deterministic Dicke State Preparation [5.755460769073285]
  Dicke states represent an important class of entangled quantum states with broad applications in quantum computing.<n>We propose deterministic quantum circuits for Dicke state preparation under two commonly seen qubit connectivity constraints.
  arXiv  Detail & Related papers  (2025-05-21T11:55:17Z)
• Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA [45.810803542748495]
  Windowed arithmetic is a technique for reducing the cost of quantum circuits with space--time tradeoffs.<n>In this work we introduce four optimizations to windowed modular exponentiation.<n>This leads to a $3%$ improvement in Toffoli count and Toffoli depth for modular exponentiation circuits relevant to cryptographic applications.
  arXiv  Detail & Related papers  (2025-02-24T16:59:16Z)
• Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost [3.129187821625805]
  We present an algorithm for constructing quantum circuits that perform multiplication over $GF (2n)$ with $mathcalO(nlog_(n))bits.<n>For some primitives, such as trinomials, the multiplication can be done in logarithmic depth and with $mathcalO(nlog_(n))bits.
  arXiv  Detail & Related papers  (2025-01-27T15:26:11Z)
• Random unitaries in extremely low depth [0.8680580889074451]
  We prove that random quantum circuits on any geometry, including a 1D line, can form approximate unitary designs over $n$ qubits in $log n$ depth.<n>In a similar manner, we construct pseudorandom unitaries (PRUs) in 1D circuits in $textpoly(log n)$ depth, and in all-to-all-connected circuits in $textpoly(log log n)$ depth.
  arXiv  Detail & Related papers  (2024-07-10T15:27:48Z)
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates [40.56175933029223]
  We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. We obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices.
  arXiv  Detail & Related papers  (2023-08-16T17:54:56Z)
• On the average-case complexity of learning output distributions of quantum circuits [33.76498647184212]
  We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model.<n>This learning model is widely used as an abstract computational model for most generic learning algorithms.
  arXiv  Detail & Related papers  (2023-05-09T20:53:27Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.