An Efficient Quantum Addition Circuit

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

Efficient quantum circuits for arithmetic operations and their applications

康博高橋

Jan 1, 20081 citation

Quantum Fourier addition simplified to Toffoli addition

Alexandru Paler

Quantum addition circuits are considered being of two types: (1) Toffoli-adder circuits which use only classical reversible gates (controlled-not and Toffoli), and (2) QFT-adder circuits based on the quantum Fourier transformation. We present a systematic translation of the QFT addition circuit into a Toffoli-based adder. This result shows that QFT addition has fundamentally the same fault-tolerance cost (e.g., T count) as the most cost-efficient Toffoli adder: instead of using approximate decompositions of the gates from the QFT circuit, it is more efficient to merge gates. In order to achieve this, we formulated circuit identities for multicontrolled gates and apply the identities algorithmically. The employed techniques can be used to automate quantum circuit optimization heuristics.Quantum addition circuits are considered being of two types: (1) Toffoli-adder circuits which use only classical reversible gates (controlled-not and Toffoli), and (2) QFT-adder circuits based on the quantum Fourier transformation. We present a systematic translation of the QFT addition circuit into a Toffoli-based adder. This result shows that QFT addition has fundamentally the same fault-tolerance cost (e.g., T count) as the most cost-efficient Toffoli adder: instead of using approximate decompositions of the gates from the QFT circuit, it is more efficient to merge gates. In order to achieve this, we formulated circuit identities for multicontrolled gates and apply the identities algorithmically. The employed techniques can be used to automate quantum circuit optimization heuristics.

arXiv:2209.15193Physical Review AOct 27, 202212 citations

Quantum adder circuits

Hafiz Md. Hasan Babu

Institute of Physics eBooksMay 1, 20200 citations

The addition and subtraction of quantum matrix based on GNEQR

Hai-Sheng Li, Yusi Xu, Yunbai Qin +2 more

The efficient quantum circuits of arithmetic operations are important to perform quantum algorithms. To implement efficient matrix operations, we first modify the generalized model of the novel enhanced quantum representation of digital images (GNEQR) to store unsigned and signed integer matrices. Next, we design the circuits of the circuits of quantum addition, quantum modulo addition, quantum subtraction, and quantum modulo subtraction, these operations all keeping two operands unchanged. Then, we propose the circuits of quantum matrix addition, quantum matrix modulo addition, quantum matrix subtraction, and quantum matrix modulo subtraction for the first time. Furthermore, we present a simulation method to verify the correctness of the proposed arithmetic operations of matrix. The results of simulation experiment show that the propose arithmetic operations of matrix are efficient and correct.The efficient quantum circuits of arithmetic operations are important to perform quantum algorithms. To implement efficient matrix operations, we first modify the generalized model of the novel enhanced quantum representation of digital images (GNEQR) to store unsigned and signed integer matrices. Next, we design the circuits of the circuits of quantum addition, quantum modulo addition, quantum subtraction, and quantum modulo subtraction, these operations all keeping two operands unchanged. Then, we propose the circuits of quantum matrix addition, quantum matrix modulo addition, quantum matrix subtraction, and quantum matrix modulo subtraction for the first time. Furthermore, we present a simulation method to verify the correctness of the proposed arithmetic operations of matrix. The results of simulation experiment show that the propose arithmetic operations of matrix are efficient and correct.

International Journal of Quantum InformationOct 1, 20194 citations

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.