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

arXiv:0910.2530 · Quantum Information and Computation

Quantum addition circuits and unbounded fan-out

Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro

Published Sep 1, 2010• 119 citations
arXivHTMLPDF

Abstract

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.

DOI
10.26421/qic10.9-10-12

Related papers

Quantum addition circuits and unbounded fan-out

TakahashiYasuhiro, TaniSeiichiro, KunihiroNoboru

We first show how to construct an O(n)-depth O(n)-size quantum circuit for additionof two n-bit binary numbers with no ancillary qubits. The exact size is 7n-6, whichis smaller than that of any oth...

Quantum Information and Computation•Sep 1, 2010•6 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

Shallow Quantum Circuits with Uninitialized Ancillary Qubits.

Yasuhiro Takahashi, Seiichiro Tani

We study the computational power of shallow quantum circuits with $n$ input qubits, one output qubit, and two types of ancillary qubits: $O(\log n)$ initialized and $O({\rm poly}(n))$ uninitialized qubits. The initial state of the uninitialized ancillary qubits is arbitrary, and we have to return their state into the initial one at the end of the computation. First, to show the strengths of such circuits, we consider a class of symmetric functions on $n$ bits, including those (such as threshold functions) for which it is not known whether there exist shallow quantum circuits with only $O(\log n)$ initialized ancillary qubits. We show that there exists an $O(\log^2 n)$-depth quantum circuit for any function in the class with $O(\log n)$ initialized and $O(n\log^2 n)$ uninitialized ancillary qubits. Its existence shows the possibility that augmenting uninitialized ancillary qubits increases the computational power of shallow quantum circuits. The depth decreases to $O(\log n)$ when we use unbounded fan-out gates and unbounded Toffoli gates. Then, we consider the limitations of shallow quantum circuits with uninitialized ancillary qubits, which include unbounded fan-out gates and unbounded Toffoli gates. We show that, when the number of qubits on which unbounded fan-out gates act is $O({\rm poly}(\log n))$, for any constant $0 \leq \delta <1$, there does not exist an $O(\log^{\delta} n)$-depth quantum circuit for the parity function on $n$ bits with $O(\log n)$ initialized and $O({\rm poly}(n))$ uninitialized ancillary qubits.

•Aug 25, 2016•0 citations

Quantum Circuits with Unbounded Fan-out

Peter Høyer, Robert Špalek

We demonstrate that the unbounded fan-out gate is very powerful. Constant-depth polynomial-size quantum circuits with bounded fan-in and unbounded fan-out over a fixed basis (denoted by $\mathrm{QNC}_{\mathrm{f}}^0$) can approximate with polynomially small error the following gates: parity, mod[q], And, Or, majority, threshold[t], exact[t], and Counting. Classically, we need logarithmic depth even if we can use unbounded fan-in gates. If we allow arbitrary one-qubit gates instead of a fixed basis, then these circuits can also be made exact in log-star depth. Sorting, arithmetic operations, phase estimation, and the quantum Fourier transform with arbitrary moduli can also be approximated in constant depth.

arXiv:quant-ph/0208043•Theory of Computing•Jan 1, 2005•90 citations

The power of constant-depth quantum circuits of unbounded size

Sergii Strelchuk, Sathyawageeswar Subramanian, Máté Weisz

Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth. We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential. The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy. Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension $d$ and $M\geq d^2-1$ ports, we construct a unitary circuit of depth $O(\sqrt d)$, independent of $M$ and including resource preparation and port selection, with entanglement fidelity at least $(1-(d^2-1)/(2M))^2$. Thus, at fixed $d$, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on $d$ can also be removed remains open.

quant-pharXiv:2609.40294•Oct 1, 2026•0 citations

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

Yasuhiro Takahashi, Noboru Kunihiro

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.

Quantum Information and Computation•Sep 1, 2005•64 citations
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 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 study the computational power of shallow quantum circuits with nnn input qubits, one output qubit, and two types of ancillary qubits: O(log⁡n)O(\log n)O(logn) initialized and O(poly(n))O({\rm poly}(n))O(poly(n)) uninitialized qubits. The initial state of the uninitialized ancillary qubits is arbitrary, and we have to return their state into the initial one at the end of the computation. First, to show the strengths of such circuits, we consider a class of symmetric functions on nnn bits, including those (such as threshold functions) for which it is not known whether there exist shallow quantum circuits with only O(log⁡n)O(\log n)O(logn) initialized ancillary qubits. We show that there exists an O(log⁡2n)O(\log^2 n)O(log2n)-depth quantum circuit for any function in the class with O(log⁡n)O(\log n)O(logn) initialized and O(nlog⁡2n)O(n\log^2 n)O(nlog2n) uninitialized ancillary qubits. Its existence shows the possibility that augmenting uninitialized ancillary qubits increases the computational power of shallow quantum circuits. The depth decreases to O(log⁡n)O(\log n)O(logn) when we use unbounded fan-out gates and unbounded Toffoli gates. Then, we consider the limitations of shallow quantum circuits with uninitialized ancillary qubits, which include unbounded fan-out gates and unbounded Toffoli gates. We show that, when the number of qubits on which unbounded fan-out gates act is O(poly(log⁡n))O({\rm poly}(\log n))O(poly(logn)), for any constant 0≤δ<10 \leq \delta <10≤δ<1, there does not exist an O(log⁡δn)O(\log^{\delta} n)O(logδn)-depth quantum circuit for the parity function on nnn bits with O(log⁡n)O(\log n)O(logn) initialized and O(poly(n))O({\rm poly}(n))O(poly(n)) uninitialized ancillary qubits.
We demonstrate that the unbounded fan-out gate is very powerful. Constant-depth polynomial-size quantum circuits with bounded fan-in and unbounded fan-out over a fixed basis (denoted by QNCf0\mathrm{QNC}_{\mathrm{f}}^0QNCf0​) can approximate with polynomially small error the following gates: parity, mod[q], And, Or, majority, threshold[t], exact[t], and Counting. Classically, we need logarithmic depth even if we can use unbounded fan-in gates. If we allow arbitrary one-qubit gates instead of a fixed basis, then these circuits can also be made exact in log-star depth. Sorting, arithmetic operations, phase estimation, and the quantum Fourier transform with arbitrary moduli can also be approximated in constant depth.
Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth. We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential. The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy. Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension ddd and M≥d2−1M\geq d^2-1M≥d2−1 ports, we construct a unitary circuit of depth O(d)O(\sqrt d)O(d​), independent of MMM and including resource preparation and port selection, with entanglement fidelity at least (1−(d2−1)/(2M))2(1-(d^2-1)/(2M))^2(1−(d2−1)/(2M))2. Thus, at fixed ddd, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on ddd can also be removed remains open.
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.