Quantum Information and Computation

A fast quantum circuit for addition with few qubits

TakahashiYasuhiro, KunihiroNoboru

Published Jul 1, 2008• 1 citation

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 a...

DOI: 10.5555/2016976.2016981

Related papers

A fast quantum circuit for addition with few qubits

Yasuhiro Takahashi, Noboru Kunihiro

Quantum Information and ComputationJul 1, 200842 citations

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 ComputationSep 1, 20055 citations

Quantum addition circuits and unbounded fan-out

Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro

arXiv:0910.2530Quantum Information and ComputationSep 1, 2010119 citations

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

Yasuhiro Takahashi, Noboru Kunihiro

Quantum Information and ComputationSep 1, 200564 citations

Ancilla-free optimal quantum adder

Junhong Nie, Jialiang Tang, Xiaoming Sun +1 more

quant-pharXiv:2610.34446Oct 27, 20260 citations

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 ComputationSep 1, 20106 citations

Quantum Information and Computation

A fast quantum circuit for addition with few qubits

TakahashiYasuhiro, KunihiroNoboru

Published Jul 1, 2008• 1 citation

Publisher

Abstract

DOI: 10.5555/2016976.2016981

Related papers

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.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 ComputationJul 1, 200842 citations

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

TakahashiYasuhiro, KunihiroNoboru

Quantum Information and ComputationSep 1, 20055 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.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.2530Quantum Information and ComputationSep 1, 2010119 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.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 ComputationSep 1, 200564 citations

Ancilla-free optimal quantum adder

Junhong Nie, Jialiang Tang, Xiaoming Sun +1 more

We construct an exact $n$ -bit quantum adder with $O(n)$ gates and $O(\log n)$ depth that requires no ancillary qubits. The circuit uses only $X$ , CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with $O(n\log\log n)$ gates and $O(\log n)$ depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with $O(n)$ gates. Both the gate count and circuit depth are asymptotically optimal.We construct an exact $n$-bit quantum adder with $O(n)$ gates and $O(\log n)$ depth that requires no ancillary qubits. The circuit uses only $X$, CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with $O(n\log\log n)$ gates and $O(\log n)$ depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with $O(n)$ gates. Both the gate count and circuit depth are asymptotically optimal.

quant-pharXiv:2610.34446Oct 27, 20260 citations

Quantum addition circuits and unbounded fan-out

TakahashiYasuhiro, TaniSeiichiro, KunihiroNoboru

Quantum Information and ComputationSep 1, 20106 citations

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.

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.

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.

We construct an exact

n

-bit quantum adder with

O(n)

gates and

O(\log n)

depth that requires no ancillary qubits. The circuit uses only

X

, CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with

O(n\log\log n)

gates and

O(\log n)

depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with

O(n)

gates. Both the gate count and circuit depth are asymptotically optimal.