There are two important, and potentially interconnecting, avenues to the realization of large-scale quantum algorithms: improvement of the hardware, and reduction of resource requirements demanded by algorithm components. In focusing on the latter, one crucial subroutine to many sought-after applications is the quantum adder. A variety of different implementations exist with idiosyncratic pros and cons. One of these, the Draper quantum Fourier adder, offers the lowest qubit count of any adder, but requires a substantial number of gates as well as extremely fine rotations. In this work we present a modification of the Draper adder which eliminates small-angle rotations to highly coarse levels, matched with some strategic corrections. This reduces hardware requirements without sacrificing the qubit saving. We show that the inherited loss of fidelity is directly given by the rate of carry and borrow bits in the computation. We derive formulas to predict this, complemented by complete gate-level matrix product state simulations of the circuit. Moreover, we analytically describe the effects of possible stochastic control error. We present an in-depth analysis of this approach in the context of Shor's algorithm, focusing on the factoring of RSA-2048. Surprisingly, we find that each of the $7\ifmmode\times\else\texttimes\fi{}{10}^{7}$ quantum Fourier transforms may be truncated down to $\ensuremath{\pi}/64$, with additive rotations left only slightly finer. This result is much more efficient than previously realized. We quantify savings in terms of both logical resources and raw magic states, demonstrating that phase adders can be competitive with Toffoli-based constructions.
There are two important, and potentially interconnecting, avenues to the realization of large-scale quantum algorithms: improvement of the hardware, and reduction of resource requirements demanded by algorithm components. In focusing on the latter, one crucial subroutine to many sought-after applications is the quantum adder. A variety of different implementations exist with idiosyncratic pros and cons. One of these, the Draper quantum Fourier adder, offers the lowest qubit count of any adder, but requires a substantial number of gates as well as extremely fine rotations. In this work we present a modification of the Draper adder which eliminates small-angle rotations to highly coarse levels, matched with some strategic corrections. This reduces hardware requirements without sacrificing the qubit saving. We show that the inherited loss of fidelity is directly given by the rate of carry and borrow bits in the computation. We derive formulas to predict this, complemented by complete gate-level matrix product state simulations of the circuit. Moreover, we analytically describe the effects of possible stochastic control error. We present an in-depth analysis of this approach in the context of Shor's algorithm, focusing on the factoring of RSA-2048. Surprisingly, we find that each of the 7\ifmmode×\else\texttimes\fi107 quantum Fourier transforms may be truncated down to \ensuremathπ/64, with additive rotations left only slightly finer. This result is much more efficient than previously realized. We quantify savings in terms of both logical resources and raw magic states, demonstrating that phase adders can be competitive with Toffoli-based constructions.
The quantum Fourier transform (QFT) is a fundamental component in various quantum algorithms, including Shor's factoring algorithm and the Harrow-Hassidim-Lloyd (HHL) algorithm for solving systems of linear equations. Efficient implementation of the QFT is essential for the practical realization of large-scale quantum algorithms, especially in fault-tolerant quantum computing. In fault-tolerant implementations, the Clifford + T gate library is the standard choice for building quantum circuits. As the most resource-intensive component within this framework, the T gate's associated cost poses a significant challenge to the efficient implementation of the QFT and its dependent algorithms. While approximate QFT (AQFT) circuits reduce this cost, state-of-the-art implementations still require a T-count of [Formula: see text] and a T-depth of [Formula: see text]. Although these results represent a notable achievement, the associated resource cost remains a primary bottleneck for practical, large-scale quantum algorithms, motivating further optimization. To address this bottleneck, this paper introduces two novel [Formula: see text]-qubit AQFT circuits with an approximation error of [Formula: see text]. Our first design, AQFT Circuit 1, halves the T-count to [Formula: see text] by constructing inverse phase gradient transformation (PGT) circuits without using additional non-Clifford gates and by implementing the inverse PGTs using quantum adders. Our second design, AQFT Circuit 2, reduces the T-depth to [Formula: see text] through parallelization of the inverse PGTs that add only [Formula: see text] additional T gates. For both AQFT circuits, the state-of-the-art linear-depth quantum adder is employed. We demonstrate that employing the linear-depth quantum adder provides advantages over the currently known logarithmic-depth quantum adder, not only in terms of T-count but also in T-depth optimization for the AQFT, particularly within the range [Formula: see text], which encompasses practical system sizes.
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.
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.
The Quantum Fourier Transform (QFT) grants competitive advantages, especially in resource usage and circuit approximation, for performing arithmetic operations on quantum computers, and offers a potential route towards a numerical quantum-computational paradigm. In this paper, we utilize efficient techniques to implement QFT-based integer addition and multiplications. These operations are fundamental to various quantum applications including Shor's algorithm, weighted sum optimization problems in data processing and machine learning, and quantum algorithms requiring inner products. We carry out performance evaluations of these implementations based on IBM's superconducting qubit architecture using different compatible noise models. We isolate the sensitivity of the component quantum circuits on both one-/two-qubit gate error rates, and the number of the arithmetic operands' superposed integer states. We analyze performance, and identify the most effective approximation depths for quantum add and quantum multiply within the given context. We observe significant dependency of the optimal approximation depth on the degree of machine noise and the number of superposed states in certain performance regimes. Finally, we elaborate on the algorithmic challenges - relevant to signed, unsigned, modular and non-modular versions - that could also be applied to current implementations of QFT-based subtraction, division, exponentiation, and their potential tensor extensions. We analyze performance trends in our results and speculate on possible future development within this computational paradigm.
Quantum phase estimation~(QPE) is central to numerous quantum algorithms, yet its standard implementation demands an $\calO(m^{2})$-gate quantum Fourier transform~(QFT) on m control qubits-a prohibitive overhead on near-term noisy intermediate-scale quantum (NISQ) devices. We introduce the \emph{Phase-Fidelity-Aware Truncated QFT} (PFA-TQFT), a family of approximate QFT circuits parameterised by a truncation depth~d that omits controlled-phase rotations below a hardware-calibrated fidelity threshold~$\eps$. Our central result establishes $\TV(P_{\varphi},P_{\varphi}^{d})\leqπ(m{-}d)/2^{d}$, showing that for $d=\calO(\log m)$ circuit size collapses from $\calO(m^{2})$ to $\calO(m\log m)$ while estimation error grows by at most $\calO(2^{-d})$. We characterise $\dstar=\Floor{\log_{2}(2π/\eps_{2q})}$ directly from native gate fidelities, demonstrating 31.3 -43.7\% at m = 30, gate-count reduction on IBM Eagle/Heron and IonQ~Aria with negligible accuracy loss. Numerical experiments on the transverse-field Ising model confirm all theoretical predictions and reveal a \emph{noise-truncation synergy}: PFA-TQFT outperforms full QFT under NISQ noise $\eps_{2q}\gtrsim 2\times10^{-3}$.
Abstract The Quantum Fourier Transform (QFT) grants competitive advantages, especially in resource usage and circuit approximation, for performing arithmetic operations on quantum computers , and offers a potential route towards a numerical quantum-computational paradigm. In this paper, we utilize efficient techniques to implement QFT-based integer addition and multiplications. These operations are fundamental to various quantum applications including Shor’s algorithm, weighted sum optimization problems in data processing and machine learning, and quantum algorithms requiring inner products. We carry out performance evaluations of these implementations based on IBM’s superconducting qubit architecture using different compatible noise models. We isolate the sensitivity of the component quantum circuits on both one-/two-qubit gate error rates, and the number of the arithmetic operands’ superposed integer states. We analyze performance, and identify the most effective approximation depths for unsigned quantum addition and quantum multiplication within the given context. We then perform a similar analysis of signed addition and compare to the unsigned results. We observe significant dependency of the optimal approximation depth on the degree of machine noise and the number of superposed states in certain performance regimes. Finally, we elaborate on the algorithmic challenges - relevant to signed, unsigned, modular and non-modular versions - that could also be applied to current implementations of QFT-based subtraction, division, exponentiation, and their potential tensor extensions. We analyze the performance trends in our results and speculate on possible future developments within this computational paradigm.