A Classical-Quantum Adder with Constant Workspace and Linear Gates

• URL: http://arxiv.org/abs/2507.23079v1
• Date: Wed, 30 Jul 2025 20:24:03 GMT
• Title: A Classical-Quantum Adder with Constant Workspace and Linear Gates
• Authors: Craig Gidney,
• Abstract summary: I construct an adder that uses 3 clean ancillae and $4n pm O(1)$ Toffoli gates to add a classical offset into a quantum register.<n>I show that applying the presented adders conditioned on a control qubit requires no additional workspace or Toffolis.
• Score: 0.03922370499388702
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In 2004, Cuccaro et al found a quantum-quantum adder with $O(n)$ gate cost and $O(1)$ ancilla qubits. Since then, it's been an open question whether classical-quantum adders can achieve the same asymptotic complexity. These costs are particularly relevant to modular arithmetic circuits, which often offset by the classically known modulus. In this paper, I construct an adder that uses 3 clean ancillae and $4n \pm O(1)$ Toffoli gates to add a classical offset into a quantum register. I also present an adder with a Toffoli cost of $3n \pm O(1)$ that uses 2 clean ancillae and $n-2$ dirty ancillae. I further show that applying the presented adders conditioned on a control qubit requires no additional workspace or Toffolis.

Related papers

• Ancilla-free Quantum Adder with Sublinear Depth [2.784223169208082]
  We present the first exact quantum adder with sublinear depth and no ancilla qubits.<n>Our construction is based on classical reversible logic only.
  arXiv  Detail & Related papers  (2025-01-28T09:05:49Z)
• Entanglement-assisted Quantum Error Correcting Code Saturating The Classical Singleton Bound [44.154181086513574]
  We introduce a construction for entanglement-assisted quantum error-correcting codes (EAQECCs) that saturates the classical Singleton bound with less shared entanglement than any known method for code rates below $ frackn = frac13 $. We demonstrate that any classical $[n,k,d]_q$ code can be transformed into an EAQECC with parameters $[n,k,d;2k]]_q$ using $2k$ pre-shared maximally entangled pairs.
  arXiv  Detail & Related papers  (2024-10-05T11:56:15Z)
• Rise of conditionally clean ancillae for efficient quantum circuit constructions [0.06640389895742692]
  We introduce conditionally clean ancilla qubits, a new quantum resource, recently explored by [NZS24], that bridges the gap between traditional clean and dirty ancillae.<n>They begin and end in an unknown state and can be borrowed from existing system qubits, avoiding the space overhead of explicit qubit allocation.<n>We present new circuit constructions leveraging conditionally clean ancillae to achieve lower gate counts and iteration, particularly with limited ancilla availability.
  arXiv  Detail & Related papers  (2024-07-25T11:38:04Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Quantum Fourier Addition, Simplified to Toffoli Addition [92.18777020401484]
  We present the first systematic translation of the QFT-addition circuit into a Toffoli-based adder. Instead of using approximate decompositions of the gates from the QFT circuit, it is more efficient to merge gates.
  arXiv  Detail & Related papers  (2022-09-30T02:36:42Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• Halving the width of Toffoli based constant modular addition to n+3 qubits [69.43216268165402]
  We present an arithmetic circuit performing constant modular addition having $mathcalO(n)$ depth of Toffoli gates. This is an improvement by a factor of two compared to the width of the state-of-the-art Toffoli-based constant modular adder.
  arXiv  Detail & Related papers  (2021-02-06T17:07:48Z)
• Quantum block lookahead adders and the wait for magic states [0.0]
  We present a block lookahead adder that parallelizes across blocks of bits of size $b$, instead of over all bits. We estimate the spacetime volume of these adders, and adders from previous work, for various register sizes and factory counts under plausible assumptions for a large scale quantum computer based on the surface code and superconducting qubits.
  arXiv  Detail & Related papers  (2020-12-03T01:15:43Z)
• Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-phase Toffoli Gates [0.9697877942346909]
  We construct an efficient control modular adder with small KQ by using relative-phase Toffoli gates in two major types of quantum computers. In FTQ, $T$ gates incur heavy cost due to distillation, which fabricates ancilla for running $T$ gates with high accuracy but consumes a lot of specially prepared ancilla qubits. We propose a new control modular adder that uses only 20% of the number of $T$ gates of the original.
  arXiv  Detail & Related papers  (2020-10-01T08:55:53Z)

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.