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.
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.
We describe an implementation of Shor’s quantum algorithm to factor n-bit integers using only 2n+2 qubits. In contrast to previous space-optimized implementations, ours features a purely Toffoli based modular multiplication circuit. The circuit depth and the overall gate count are in O(n 3 ) and O(n 3 log n), respectively. We thus achieve the same space and time costs as Takahashi et al. [1], while using a purely classical modular multiplication circuit. As a consequence, our approach evades most of the cost overheads originating from rotation synthesis and enables testing and localization of some faults in both, the logical level circuit and an actual quantum hardware implementation. Our new (in-place) constant-adder, which is used to construct the modular multiplication circuit, uses only dirty ancilla qubits and features a circuit size and depth in O(n log n) and O(n), respectively.
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.
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.
ABSTRACT Quantum arithmetic is a basic computational layer for reversible processing in quantum processors, yet its implementation cost grows rapidly with operand width and multi-qubit gate requirements. This paper presents a modular quantum arithmetic and logic unit (QALU) designed with resource-aware reversible primitives and Clifford+T decomposition. The architecture separates addition, subtraction, multiplication, and division into reusable submodules and evaluates their circuit cost in terms of T-count, T-depth, CNOT-count, CNOT-depth, qubit width, and total gate count. Hermitian LI gates and approximate Toffoli decompositions are incorporated to reduce redundant non-Clifford operations and circuit depth. The circuits are constructed and validated in Qiskit for small operand sizes, followed by symbolic resource analysis for scalable forms. For the demonstrated instances, the optimized adder is reduced from 10 to 7 total gates, the subtractor from 9 to 5, the multiplier from 12 to 8, and the divider from 11 to 6, while preserving the intended arithmetic mappings. The resulting modular framework provides a compact circuit-level approach for quantum arithmetic and is relevant to emerging quantum technology and quantum nanoelectronic systems where qubit count and fault-tolerant gate overhead are critical design constraints. Key words: quantum arithmetic, quantum ALU, reversible logic, Clifford+T, Hermitian LI gate, approximate Toffoli, Qiskit, quantum nanoelectronics.
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.