We present an arithmetic circuit performing constant modular addition having $O(n)$ depth of Toffoli gates and using a total of $n+3$ qubits. This is an improvement by a factor of two compared to the width of the state-of-the-art Toffoli-based constant modular adder. The advantage of our adder, compared to the ones operating in the Fourier basis, is that it does not require small-angle rotations and their $\text{Clifford}+T$ decomposition. Our circuit uses a recursive adder combined with the modular addition scheme proposed by Vedral et al. The circuit is implemented and verified exhaustively with quantify, an open-sourced framework. We also report on the $\text{Clifford}+T$ cost of the circuit.
We present an arithmetic circuit performing constant modular addition having O(n) depth of Toffoli gates and using a total of n+3 qubits. This is an improvement by a factor of two compared to the width of the state-of-the-art Toffoli-based constant modular adder. The advantage of our adder, compared to the ones operating in the Fourier basis, is that it does not require small-angle rotations and their Clifford+T decomposition. Our circuit uses a recursive adder combined with the modular addition scheme proposed by Vedral et al. The circuit is implemented and verified exhaustively with quantify, an open-sourced framework. We also report on the Clifford+T cost of the circuit.
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,Tgates incur heavy cost due to distillation, which fabricates ancilla for runningTgates with high accuracy but consumes a lot of especially prepared ancilla qubits and a lot of time. Thus, we must reduce the number ofTgates. We propose a new control modular adder that uses only 20% of the number ofTgates of the original. Moreover, when we take distillation into consideration, we find that we minimizeKQT(the product of the number of qubits andT-depth) by runningΘ(n/logn)Tgates simultaneously. In NISQ,cnotgates are the major error source. We propose a new control modular adder that uses only 35% of the number ofcnotgates of the original. Moreover, we show that theKQCX(the product of the number of qubits andcnot-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.
Since an n-qubit circuit consisting of CNOT gates can have up to Ω(n2/logn) CNOT gates, it is natural to expect that Ω(n2/logn) Toffoli gates are needed to apply a controlled version of such a circuit. We show that the Toffoli count can be reduced to at most n. The Toffoli depth can also be reduced to O(1), at the cost of 2n Toffoli gates, even without using any ancilla or measurement. In fact, using a measurement-based uncomputation, the Toffoli depth can be further reduced to 1. From this, we give two corollaries: any controlled Clifford circuit can be implemented with O(1) T-depth, and any Clifford+T circuit with T-depth D can be controlled with T-depth O(D), even without ancillas. As an application, we show how to catalyze a rotation by any angle up to precision ε in T-depth exactly 1 using a universal ⌈log2(8/ε)⌉-qubit catalyst state.
In 2004, Cuccaro et al found a quantum-quantum adder with O(n) gate cost and O(1) ancilla qubits. Since then, it's been an open question whether classical-quantum adders can achieve the same asymptotic complexity. These costs are particularly relevant to modular arithmetic circuits, which often offset by the classically known modulus. In this paper, I construct an adder that uses 3 clean ancillae and 4n±O(1) Toffoli gates to add a classical offset into a quantum register. I also present an adder with a Toffoli cost of 3n±O(1) that uses 2 clean ancillae and n−2 dirty ancillae. I further show that applying the presented adders conditioned on a control qubit requires no additional workspace or Toffolis.
Efficient quantum arithmetic circuits are commonly found in numerous quantum algorithms of practical significance. To date, the logarithmic-depth quantum adders include a constant coefficient k ≥ 2 while achieving the Toffoli-Depth of k log n + 𝒪(1). In this work, 160 alternative compositions of the carry-propagation structure are comprehensively explored to determine the optimal depth structure for a quantum adder. By extensively studying these structures, it is shown that an exact Toffoli-Depth of log n + 𝒪(1) is achievable. This presents a reduction of Toffoli-Depth by almost 50% compared to the best known quantum adder circuits presented to date. We demonstrate a further possible design by incorporating a different expansion of propagate and generate forms, as well as an extension of the modular framework. Our article elaborates on these designs, supported by detailed theoretical analyses and simulation-based studies, firmly substantiating our claims of optimality within all possible configurations outlined in this work. The results also mirror similar improvements, recently reported in classical adder circuit complexity.
In this work, we revisit prefix sums through the lens of linear algebra. We describe an identity that decomposes triangular all-ones matrices as a sum of two Kronecker products, and apply it to design recursive prefix sum algorithms and circuits. Notably, the proposed family of circuits is the first one that achieves the following three properties simultaneously: (i) zero-deficiency, (ii) constant fan-out per-level, and (iii) depth that is asymptotically strictly smaller than 2log(n) for input length n. As an application, we show how to use these circuits to design quantum adders with 1.893log(n)+O(1) Toffoli depth, O(n) Toffoli gates, and O(n) additional qubits, improving the Toffoli depth and/or Toffoli size of existing constructions.
We construct an exact n-bit quantum adder with O(n) gates and O(logn) 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(nloglogn) gates and O(logn) 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.