Improved quantum circuits for division

• URL: http://arxiv.org/abs/2603.18110v1
• Date: Wed, 18 Mar 2026 13:41:43 GMT
• Title: Improved quantum circuits for division
• Abstract summary: 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.
• Score: 42.76841620787673
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Arithmetic operations are an important component of many quantum algorithms. As such, coming up with optimized quantum circuits for these operations leads to more efficient implementations of the corresponding algorithms. In this paper, we develop new fault-tolerant quantum circuits for various integer division algorithms (both reversible and non-reversible). These circuits, when implemented in the Clifford+T gate set, achieve an up to 76.08\% and 68.35\% reduction in T-count and CNOT-count, respectively, compared to previous circuit constructions. Some of our circuits also improve the asymptotic T-depth from $O(n^2)$ to $O(n \log n),$ where $n$ is the bit-length of the dividend. The qubit counts are also lower than in previous works. We achieve this by expressing the division algorithms in terms of a primitive we call COMP-N-SUB, that compares two integers and conditionally subtracts them. We show that this primitive can be implemented at a cost, in terms of both Clifford and non-Clifford gates, that is comparable to one addition. This is in contrast to performing comparison and conditional subtraction separately, whose cost would be comparable to a controlled addition plus a regular addition.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• 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)
• Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations [1.1694898979785655]
  We present optimized quantum circuits for multiplication and division operations.<n>Our ancilla-free GF multiplication circuit has the gate count complexity of $O(mlog3)$.<n>We demonstrate practical advantages for cryptographically relevant values of $m$, including reductions in both CNOT and Toffoli gate counts.
  arXiv  Detail & Related papers  (2025-11-25T18:43:08Z)
• Optimization and Synthesis of Quantum Circuits with Global Gates [41.99844472131922]
  We use global interactions, such as the Global Molmer-Sorensen gate present in ion trap hardware, to optimize and synthesize quantum circuits.<n>The algorithm is based on the ZX-calculus and uses a specialized circuit extraction routine that groups entangling gates into Global MolmerSorensen gates.<n>We benchmark the algorithm in a variety of circuits, and show how it improves their performance under state-of-the-art hardware considerations.
  arXiv  Detail & Related papers  (2025-07-28T10:25:31Z)
• Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
  CNOT circuits are a common building block of general quantum circuits. This article presents state-of-the-art algorithms for optimizing the number of CNOT gates. A simulated evaluation shows that the suggested is almost always beneficial and reduces the number of CNOT gates by up to 10%.
  arXiv  Detail & Related papers  (2024-08-07T19:51:22Z)
• Lower T-count with faster algorithms [2.488003578430483]
  We contribute to the $T$-count reduction problem by proposing efficient $T$-counts with low execution times.<n>We greatly improve the complexity of TODD, an algorithm currently providing the best $T$-count reduction on various quantum circuits.<n>We propose another algorithm which has an even lower complexity and that achieves a better or equal $T$-count than the state of the art on most quantum circuits evaluated.
  arXiv  Detail & Related papers  (2024-07-11T17:31:20Z)
• Efficient Implementation of a Quantum Search Algorithm for Arbitrary N [0.0]
  This paper presents an enhancement to Grover's search algorithm for instances where $N$ is not a power of 2.<n>By employing an efficient algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, we demonstrate that a considerable reduction in the number of oracle calls (and Grover's iterations) can be achieved in many cases.
  arXiv  Detail & Related papers  (2024-06-19T19:16:40Z)
• Quantum Circuit Optimization with AlphaTensor [47.9303833600197]
  We develop AlphaTensor-Quantum, a method to minimize the number of T gates that are needed to implement a given circuit. Unlike existing methods for T-count optimization, AlphaTensor-Quantum can incorporate domain-specific knowledge about quantum computation and leverage gadgets. Remarkably, it discovers an efficient algorithm akin to Karatsuba's method for multiplication in finite fields.
  arXiv  Detail & Related papers  (2024-02-22T09:20:54Z)
• Asymptotically optimal synthesis of reversible circuits [0.0]
  We propose an algorithm to implement an arbitrary $n$wire circuit with no more than $ (2n n/log n)$ elementary gates.
  arXiv  Detail & Related papers  (2023-02-13T03:08:55Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)
• Improved quantum circuits for elliptic curve discrete logarithms [6.058525641792685]
  We present improved quantum circuits for elliptic curve scalar multiplication. We optimize low-level components such as reversible integer and modular arithmetic. We provide a full implementation of point addition in the Q# quantum programming language.
  arXiv  Detail & Related papers  (2020-01-27T04:08:49Z)

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.