IEEE Transactions on Quantum Engineering · 2021 · 16 citations · 55 references
ComputingComputer EngineeringComputer ScienceFault ToleranceFault-tolerant ComputingQuantum ComputingFault-tolerant Quantum ComputingQuantum BitsQuantum CircuitsQuantum ComputationQuantum GatesQuantum Hardware ArchitecturesAccuracy-computational Cost TradeoffAdder DesignCarry Lookahead AdditionCarry-lookahead LogicFault-tolerant Gate ConstructionFault-tolerant Quantum CircuitsQuantum Arithmetic CircuitsToffoli Gate
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, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T$</tex-math></inline-formula> gates incur heavy cost due to distillation, which fabricates ancilla for running <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T$</tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T$</tex-math></inline-formula> gates. We propose a new control modular adder that uses only 20% of the number of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T$</tex-math></inline-formula> gates of the original. Moreover, when we take distillation into consideration, we find that we minimize <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\text{KQ}_{T}$</tex-math></inline-formula> (the product of the number of qubits and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T$</tex-math></inline-formula> -depth) by running <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\Theta (n / \sqrt{\log n})$</tex-math></inline-formula> <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T$</tex-math></inline-formula> gates simultaneously. In NISQ, <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">cnot</small> gates are the major error source. We propose a new control modular adder that uses only 35% of the number of <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">cnot</small> gates of the original. Moreover, we show that the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\text{KQ}_{\text{CX}}$</tex-math></inline-formula> (the product of the number of qubits and <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">cnot</small> -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.
55
<i>Quantum Computation and Quantum Information</i>
Michael A. Nielsen, Isaac L. Chuang, Lov K. Grover · American Journal of Physics · 2002 · 22.7K citations
Quantum computation and quantum information
Jim Law · ACM SIGSOFT Software Engineering Notes · 2001 · 19.2K citations
Computing, Computer Science, Physics +13
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996 · 8.6K citations · Full text