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 linear-size quantum circuit for addition with no ancillary qubits

Yasuhiro Takahashi, Noboru Kunihiro

Published Sep 1, 2005• 64 citations
Publisher

Abstract

We construct a quantum circuit for addition of two $n$-bit binary numbers that uses no ancillary qubits. The circuit is based on the ripple-carry approach. The depth and size of the circuit are $O(n)$. This is an affirmative answer to the question of Kutin \cite{Kutin} as to whether a linear-depth quantum circuit for addition can be constructed without ancillary qubits using the ripple-carry approach. We also construct quantum circuits for addition modulo $2^n$, subtraction, and comparison that use no ancillary qubits by modifying the circuit for addition.

DOI
10.26421/qic5.6-2

Related papers

A linear-size quantum circuit for addition with no ancillary qubits

TakahashiYasuhiro, KunihiroNoboru

We construct a quantum circuit for addition of two n-bit binary numbers that uses no ancillary qubits. The circuit is based on the ripple-carry approach. The depth and size of the circuit are O(n)....

Quantum Information and Computation•Sep 1, 2005•5 citations

A fast quantum circuit for addition with few qubits

Yasuhiro Takahashi, Noboru Kunihiro

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.

Quantum Information and Computation•Jul 1, 2008•42 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 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

A new quantum ripple-carry addition circuit

Steven A. Cuccaro, Thomas G. Draper, Samuel Kutin +1 more

We present a new linear-depth ripple-carry quantum addition circuit. Previous addition circuits required linearly many ancillary qubits; our new adder uses only a single ancillary qubit. Also, our circuit has lower depth and fewer gates than previous ripple-carry adders.

arXiv:quant-ph/0410184•Oct 22, 2004•344 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

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
We construct a quantum circuit for addition of two nnn-bit binary numbers that uses no ancillary qubits. The circuit is based on the ripple-carry approach. The depth and size of the circuit are O(n)O(n)O(n). This is an affirmative answer to the question of Kutin \cite{Kutin} as to whether a linear-depth quantum circuit for addition can be constructed without ancillary qubits using the ripple-carry approach. We also construct quantum circuits for addition modulo 2n2^n2n, subtraction, and comparison that use no ancillary qubits by modifying the circuit for addition.
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 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 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.