Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Information and Computation

A fast quantum circuit for addition with few qubits

Yasuhiro Takahashi, Noboru Kunihiro

Published Jul 1, 2008• 42 citations
Publisher

Abstract

We show how to construct a fast quantum circuit for computing the sum of two $n$-bit binary numbers with few qubits. The constructed circuit uses $O(n/\log n)$ ancillary qubits and its depth and size are $O(\log n)$ and $O(n)$, respectively. The number of ancillary qubits is asymptotically less than that in Draper et al.'s quantum carry-lookahead adder, and the depth and size are asymptotically the same as those of Draper et al.'s. Moreover, we show that the circuit is useful for constructing an efficient quantum circuit for Shor's factoring algorithm.

DOI
10.26421/qic8.6-7-5

Related papers

A fast quantum circuit for addition with few qubits

TakahashiYasuhiro, KunihiroNoboru

We show how to construct a fast quantum circuit for computing the sum of two n-bit binary numbers with few qubits. The constructed circuit uses O(n/ log n) ancillary qubits and its depth and size a...

Quantum Information and Computation•Jul 1, 2008•1 citation

A logarithmic-depth quantum carry-lookahead adder

Thomas G. Draper, Samuel Kutin, Eric M. Rains +1 more

We present an efficient addition circuit, borrowing techniques from classical carry-lookahead arithmetic. Our quantum carry-lookahead (\QCLA) adder accepts two n-bit numbers and adds them in O(\log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2^n and modulo 2^n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The \QCLA\ adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.

Quantum Information and Computation•Jul 1, 2006•101 citations

Quantum addition circuits and unbounded fan-out

Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro

We first show how to construct an $O(n)$-depth $O(n)$-size quantum circuit for addition of two $n$-bit binary numbers with no ancillary qubits. The exact size is $7n-6$, which is smaller than that of any other quantum circuit ever constructed for addition with no ancillary qubits. Using the circuit, we then propose a method for constructing an $O(d(n))$-depth $O(n)$-size quantum circuit for addition with $O(n/d(n))$ ancillary qubits for any $d(n) = \Omega(\log n)$. If we are allowed to use unbounded fan-out gates with length $O(n^{\varepsilon})$ for an arbitrary small positive constant $\varepsilon$, we can modify the method and construct an $O(e(n))$-depth $O(n)$-size circuit with $o(n)$ ancillary qubits for any $e(n) = \Omega(\log^* n)$. In particular, these methods yield efficient circuits with depth $O(\log n)$ and with depth $O(\log^* n)$, respectively. We apply our circuits to constructing efficient quantum circuits for Shor's discrete logarithm algorithm.

arXiv:0910.2530•Quantum Information and Computation•Sep 1, 2010•119 citations

A Logarithmic-Depth Quantum Multiplier

Fred Sun, Anton Borissov

We present a quantum algorithm for multiplying two $n$-bit integers with overall circuit depth and $T$-depth both bounded by $O(\log 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.

quant-pharXiv:2604.09847•Apr 14, 2026•0 citations

A logarithmic-depth quantum carry-lookahead adder

Thomas G. Draper, Samuel Kutin, Eric M. Rains +1 more

We present an efficient addition circuit, borrowing techniques from the classical carry-lookahead arithmetic circuit. Our quantum carry-lookahead (QCLA) adder accepts two n-bit numbers and adds them in O(log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2^n and modulo 2^n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The QCLA adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.

Quantum Information and Computation•Jul 1, 2006•146 citations

A logarithmic-depth quantum carry-lookahead adder

Draper, Thomas G., Kutin, Samuel A., Rains, Eric M. +1 more

We present an efficient addition circuit, borrowing techniques from the classical carry-lookahead arithmetic circuit. Our quantum carry-lookahead (QCLA) adder accepts two n-bit numbers and adds them in O(log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2^n and modulo 2^n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The QCLA adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.

arXiv:quant-ph/0406142•Jun 20, 2004•18 citations
We show how to construct a fast quantum circuit for computing the sum of two nnn-bit binary numbers with few qubits. The constructed circuit uses O(n/log⁡n)O(n/\log n)O(n/logn) ancillary qubits and its depth and size are O(log⁡n)O(\log n)O(logn) and O(n)O(n)O(n), respectively. The number of ancillary qubits is asymptotically less than that in Draper et al.'s quantum carry-lookahead adder, and the depth and size are asymptotically the same as those of Draper et al.'s. Moreover, we show that the circuit is useful for constructing an efficient quantum circuit for Shor's factoring algorithm.
We present an efficient addition circuit, borrowing techniques from classical carry-lookahead arithmetic. Our quantum carry-lookahead (\QCLA) adder accepts two n-bit numbers and adds them in O(\log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2^n and modulo 2^n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The \QCLA\ adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.
We first show how to construct an O(n)O(n)O(n)-depth O(n)O(n)O(n)-size quantum circuit for addition of two nnn-bit binary numbers with no ancillary qubits. The exact size is 7n−67n-67n−6, which is smaller than that of any other quantum circuit ever constructed for addition with no ancillary qubits. Using the circuit, we then propose a method for constructing an O(d(n))O(d(n))O(d(n))-depth O(n)O(n)O(n)-size quantum circuit for addition with O(n/d(n))O(n/d(n))O(n/d(n)) ancillary qubits for any d(n)=Ω(log⁡n)d(n) = \Omega(\log n)d(n)=Ω(logn). If we are allowed to use unbounded fan-out gates with length O(nε)O(n^{\varepsilon})O(nε) for an arbitrary small positive constant ε\varepsilonε, we can modify the method and construct an O(e(n))O(e(n))O(e(n))-depth O(n)O(n)O(n)-size circuit with o(n)o(n)o(n) ancillary qubits for any e(n)=Ω(log⁡∗n)e(n) = \Omega(\log^* n)e(n)=Ω(log∗n). In particular, these methods yield efficient circuits with depth O(log⁡n)O(\log n)O(logn) and with depth O(log⁡∗n)O(\log^* n)O(log∗n), respectively. We apply our circuits to constructing efficient quantum circuits for Shor's discrete logarithm algorithm.
We present a quantum algorithm for multiplying two nnn-bit integers with overall circuit depth and TTT-depth both bounded by O(log⁡n)O(\log n)O(logn), while using O(n2)O(n^2)O(n2) gates and ancillary qubits. Our construction generates partial products via indicator-controlled copying and adds them using a tree of reversible 333-to-222 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 TTT-depth. We provide explicit circuit constructions, proofs of correctness, and concrete closed-form resource bounds.
We present an efficient addition circuit, borrowing techniques from the classical carry-lookahead arithmetic circuit. Our quantum carry-lookahead (QCLA) adder accepts two n-bit numbers and adds them in O(log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2^n and modulo 2^n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The QCLA adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.
We present an efficient addition circuit, borrowing techniques from the classical carry-lookahead arithmetic circuit. Our quantum carry-lookahead (QCLA) adder accepts two n-bit numbers and adds them in O(log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2^n and modulo 2^n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The QCLA adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.