TY - JOUR

T1 - Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-Phase Toffoli Gates

AU - Oonishi, Kento

AU - Tanaka, Tomoki

AU - Uno, Shumpei

AU - Satoh, Takahiko

AU - Van Meter, Rodney

AU - Kunihiro, Noboru

N1 - Publisher Copyright:
© 2020 IEEE

PY - 2022

Y1 - 2022

N2 - Control modular addition is a core arithmetic function, and we must consider the computational cost for actual quantum computers to realize efficient implementation. To achieve a low computational cost in a control modular adder, we focus on minimizingKQ (where K is the number of logical qubits required by the algorithm, and Q is the elementary gate step), defined by the product of the number of qubits and the depth of the circuit. In this article, we construct an efficient control modular adder with small KQ by using relative-phase Toffoli gates in two major types of quantum computers: fault-tolerant quantum computers (FTQ) on the logical layer and noisy intermediate-scale quantum computers (NISQ). We give a more efficient construction compared with Van Meter and Itoh’s, based on a carry-lookahead adder. In FTQ, T gates incur heavy cost due to distillation, which fabricates ancilla for running T gates with high accuracy but consumes a lot of especially prepared ancilla qubits and a lot of time. Thus, we must reduce the number of T gates. We propose a new control modular adder that uses only 20% of the number of T gates of the original. Moreover, when we take distillation into consideration, we find that we minimize \textKQ_T (the product of the number of qubits and T-depth) by running \Theta (n / \sqrt\log n) T gates simultaneously. In NISQ, cnot gates are the major error source. We propose a new control modular adder that uses only 35% of the number of cnot gates of the original. Moreover, we show that the \textKQ_\textCX (the product of the number of qubits and cnot-depth) of our circuit is 38% of the original. Thus, we realize an efficient control modular adder, improving prospects for the efficient execution of arithmetic in quantum computers.

AB - Control modular addition is a core arithmetic function, and we must consider the computational cost for actual quantum computers to realize efficient implementation. To achieve a low computational cost in a control modular adder, we focus on minimizingKQ (where K is the number of logical qubits required by the algorithm, and Q is the elementary gate step), defined by the product of the number of qubits and the depth of the circuit. In this article, we construct an efficient control modular adder with small KQ by using relative-phase Toffoli gates in two major types of quantum computers: fault-tolerant quantum computers (FTQ) on the logical layer and noisy intermediate-scale quantum computers (NISQ). We give a more efficient construction compared with Van Meter and Itoh’s, based on a carry-lookahead adder. In FTQ, T gates incur heavy cost due to distillation, which fabricates ancilla for running T gates with high accuracy but consumes a lot of especially prepared ancilla qubits and a lot of time. Thus, we must reduce the number of T gates. We propose a new control modular adder that uses only 20% of the number of T gates of the original. Moreover, when we take distillation into consideration, we find that we minimize \textKQ_T (the product of the number of qubits and T-depth) by running \Theta (n / \sqrt\log n) T gates simultaneously. In NISQ, cnot gates are the major error source. We propose a new control modular adder that uses only 35% of the number of cnot gates of the original. Moreover, we show that the \textKQ_\textCX (the product of the number of qubits and cnot-depth) of our circuit is 38% of the original. Thus, we realize an efficient control modular adder, improving prospects for the efficient execution of arithmetic in quantum computers.

KW - Adders

KW - Computers

KW - Costs

KW - Logic gates

KW - Optimization

KW - Quantum computing

KW - Qubit

UR - http://www.scopus.com/inward/record.url?scp=85121826791&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85121826791&partnerID=8YFLogxK

U2 - 10.1109/TQE.2021.3136195

DO - 10.1109/TQE.2021.3136195

M3 - Article

AN - SCOPUS:85121826791

SN - 2689-1808

VL - 3

JO - IEEE Transactions on Quantum Engineering

JF - IEEE Transactions on Quantum Engineering

ER -