We use a new technique for manipulating controlled quantum circuits to convert between two distinct types of quantum adders, one based on the Quantum Fourier Transform and the other based on the Ripple-Carry technique from classical reversible logic. This conversion takes the form of an explicit gate-level transpilation. We also present a new quantum adder with a natural interpretation as a kind of Carry-Lookahead adder that uses no ancillas.
We use a new technique for manipulating controlled quantum circuits to convert between two distinct types of quantum adders, one based on the Quantum Fourier Transform and the other based on the Ripple-Carry technique from classical reversible logic. This conversion takes the form of an explicit gate-level transpilation. We also present a new quantum adder with a natural interpretation as a kind of Carry-Lookahead adder that uses no ancillas.
Quantum computing (Q-computing) is a revolutionary technology that applies quantum mechanics (QM) to implement calculations significantly quicker than traditional computers. Q-computing employs Q-bits (qubits) rather than classical bits, which can take on a superposition state, making it possible to represent both 0 and 1 at once. This distinctive property allows qubits to perform multiple calculations simultaneously, making Q computers exponentially more powerful as more qubits are added, compared to the linear scaling of classical computers. However, challenges such as qubit instability and error rates remain significant obstacles to fully realizing this potential. A vital aspect of this technology is the development of Q arithmetic circuits, which act as the foundational blocks for efficiently executing Q algorithms. Q half-adder and full-adder circuits are integral to performing fundamental arithmetic operations within Q computers. In contrast to classical adders, Q adders rely on Q gates such as Controlled NOT (CNOT) and Toffoli gates. These gates exploit Q phenomena like entanglement and superposition, allowing for more efficient computations. The Q half-adder consists of two qubits and adds two single bits, producing a carry and sum output. It utilizes the CNOT gate to compute the sum and the Toffoli gate (controlled-controlled-NOT [CCNOT]) to compute the carry. The Q full-adder builds on this, adding three qubits to produce a sum and a carry output, further increasing computational capacity. Through the entanglement of qubits, these circuits allow for more parallelism and speed compared to classical adders. Q carry-look-ahead adders (QCLAs) and Q ripple-carry adders (QRCAs) are used to perform more complex arithmetic operations based on these half-adder and full-adder structures. Q arithmetic circuits have broad applications, boosting secure key generation in cryptography, speeding up matrix operations for faster model training in machine learning, and enabling more precise, efficient image transformations in Q image processing, benefiting fields like medical imaging and computer vision.
In this study, we construct the quantum reversible counterparts of the logical AND, OR, XOR, NOR, and NAND gates. We utilize a quantum Fourier transform (QFT)-based adder circuit that replicates the functionality of a digital half-adder, which computes the sum and carry of two input bits using XOR and AND gates, respectively. To realize different logic gate operations, we apply pre- and post-processing to the QFT-adder using quantum gates, leveraging Boolean algebra properties to enable conversions between various logical functions. Although the number of elementary quantum logic gates increases for a small number of inputs-making the approach appear inefficient at first glance-the overall required qubit count is reduced compared to non-QFT-based designs as the number of inputs increases.
The state of the art of quantum circuits using the ripple-carry strategy for the addition and comparison of two n-bit numbers is presented, as well as optimizations in the Clifford+ <?TeX T?> Math 1 gate set, both in terms of <?TeX CNOT?> Math 2 -depth and <?TeX T?> Math 3 -depth, or <?TeX CNOT?> Math 4 -count and <?TeX T?> Math 5 -count. In particular, we consider the adders presented by Cuccaro et al. and Takahashi et al., and exhibit an adder with a <?TeX T?> Math 6 -depth of 3n and a <?TeX CNOT?> Math 7 -depth of 8n, while without optimization of the original circuits, a <?TeX T?> Math 8 -depth of 6n is expected. Note that we have focused here on quantum ripple-carry adders using at most one ancilla, without any approximation of the 3-qubit gates involved (Toffoli, Peres and TR) or any strategy involving a measurement.
We improve the number of T gates needed to perform an n-bit adder from 8 n + O ( 1 ) to 4 n + O ( 1 ) . We do so via a "temporary logical-AND" construction which uses four T gates to store the logical-AND of two qubits into an ancilla and zero T gates to later erase the ancilla. This construction is equivalent to one by Jones, except that our framing makes it clear that the technique is far more widely applicable than previously realized. Temporary logical-ANDs can be applied to integer arithmetic, modular arithmetic, rotation synthesis, the quantum Fourier transform, Shor's algorithm, Grover oracles, and many other circuits. Because T gates dominate the cost of quantum computation based on the surface code, and temporary logical-ANDs are widely applicable, this represents a significant reduction in projected costs of quantum computation. In addition to our n-bit adder, we present an n-bit controlled adder circuit with T-count of 8 n + O ( 1 ) , a temporary adder that can be computed for the same cost as the normal adder but whose result can be kept until it is later uncomputed without using T gates, and discuss some other constructions whose T-count is improved by the temporary logical-AND.
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.
We present a quantum algorithm for multiplying two n-bit integers with overall circuit depth and T-depth both bounded by O(logn), while using O(n2) gates and ancillary qubits. Our construction generates partial products via indicator-controlled copying and adds them using a tree of reversible 3-to-2 adders followed by one quantum carry-lookahead adder. Building on the carry-save adders of Kim et al., we combine full input fanout, workspace reuse, and phase-corrected gate implementations to reduce T-depth. We provide explicit circuit constructions, proofs of correctness, and concrete closed-form resource bounds.