Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Review A

Analytical formulas for the performance scaling of quantum processors with a large number of defective gates

Yunseong Nam, R. Blümel

Published Oct 1, 2015• 8 citations
Publisher

Abstract

Removing a single logical gate from a classical information processor renders this processor useless. This is not so for a quantum information processor. A large number of quantum gates may be removed without significantly affecting the processor's performance. In this paper, focusing on the quantum Fourier transform (QFT) and quantum adder, we show even more: Even if most of its gates are eliminated and the remaining gates are selected from a randomly generated set, the QFT, one of the most useful quantum processors, and the quantum adder, one of the most basic building blocks of a universal quantum computer, still operate with satisfactory success probability, comparable to that of a quantum computer constructed with perfect gates. We support these conclusions by first laying out a general analytical framework and then deriving analytical scaling relations, which are in excellent agreement with our numerical simulations. The demonstrated robustness of the QFT and quantum adder, to the point where randomly generated quantum gates take the place of the exact gates, is an important boon for the construction of quantum computers, since it shows that stringent gate error tolerances do not have to be met to obtain satisfactory performance of the corresponding quantum processors. Our analytical techniques are powerful enough to generate asymptotic scaling laws for any gate defect model of quantum information processors and we illustrate this point by explicitly computing asymptotic analytical scaling formulas for several other defect models as well.

DOI
10.1103/physreva.92.042301

Related papers

Performance scaling of the quantum Fourier transform with defective rotation gates

Yun Seong Nam, Reinhold Blume

Addressing Landauer's question concerning the influence of static gate defects on quantum information processor performance, we investigate analytically and numerically the case of the quantum Fourier transform (QFT) with defective controlled rotation (CROT) gates. Two types of defects are studied, separately and in combination: systematic and random. Analytical scaling laws of QFT performance are derived with respect to the number of qubits $n$, the size $\delta$ of systematic defects, and the size $\epsilon$ of random defects. The analytical results are in excellent agreement with numerical simulations. In addition, we present an unexpected result: The performance of the defective QFT does not deteriorate with increasing $n$, but approaches a constant that scales in $\epsilon$. We derive an analytical formula that accurately reproduces the $\epsilon$ scaling of the performance plateaus. Overall, we observe that the CROT gates may exhibit static and random defects of the order of 30\% and larger, and still result in satisfactory QFT performance. Thus we answer Landauer's question in the case of the QFT: far from being lethal, the QFT can tolerate tremendous static gate defects and still perform its function. The extraordinary robustness of the QFT with respect to static gate defects displayed in our numerical and analytical calculations should be a welcome boon for laboratory and industrial realizations of quantum circuitry.

Quantum Information and Computation•Jul 1, 2015•3 citations

Robustness and Performance Scaling of Large-Scale Quantum Computers with Faulty Gates

Yunseong Nam

This thesis presents an overview of my published work on streamlining and optimizing quantum processors. Complete, microscopic, quantum-gate–by–quantum-gate simulations of a variety of quantum circuits are implemented and executed on state-of-the-art multi-processor parallel computers. A host of analytical scaling formulas addressing the quality of quantum processors, e.g., in the presence of realistic gate errors and defects, are presented. These formulas reliably describe the practically interesting, large-number-of-qubit regime, inaccessible to simulations on classical computers. Much of the technical details may be found in my published articles, which appear in the Appendix. This thesis also presents the generic and specific directions into which my current investigations are headed. In addition, several preliminary results are presented and discussed.

•Jan 1, 2016•0 citations

Robustness of the quantum Fourier transform with respect to static gate defects

Yunseong Nam, R. Blümel

The quantum Fourier transform (QFT) is one of the most widely used quantum algorithms, ranging from its primary role in finding the periodicity hidden in a quantum state to its use in constructing a quantum adder. Testing how the QFT performs under more realistic conditions, we find that the QFT, when used for period finding, shows extraordinary robustness with respect to static gate defects. For instance, replacing all rotation angles $\ensuremath{\pi}/{2}^{j}$ of the controlled rotation gates in the QFT circuit by $\ensuremath{\pi}(1+r)/{2}^{j}$, where $r$ is a uniformly distributed random variable taking values in the range $[\ensuremath{-}1,1]$, effectively resulting in a QFT with random gates, the QFT performs well above the expected random result. However, it is important to keep the ${2}^{j}$ terms in the denominators of the rotation angles, resulting in random, but hierarchically random, gates. Relaxing this hierarchical structure of the QFT circuit, we find that the performance of the QFT deteriorates significantly. This observation indicates that the hierarchical structure of the quantum circuit of the QFT is more important for the observed robustness in performance than the precise actions of individual gates. In addition to the specific example of the QFT circuit studied here, this observation also corroborates our experience with more general and more complex quantum circuits. Thus, backed by our detailed numerical and analytical results, we may condense the results of our research into the following general principle: The topology of a quantum circuit is more important than the precise actions of its gates.

Physical Review A•Apr 30, 2014•10 citations

Robustness and performance scaling of a quantum computer with respect to a class of static defects

Yunseong Nam, R. Blümel

Competing computationally with experimental groups for the construction of scaling quantum computers, we simulate a complete quantum-gate by quantum-gate implementation of Shor's algorithm on a classical 128-core cluster computer. The resulting virtual quantum computer serves as a convenient quantum laboratory for the investigation of the effect of defects in the quantum circuitry. The class of defects studied here is the removal of all rotation gates with rotation angles $\ensuremath{\theta}<\ensuremath{\pi}/{2}^{b}$. Factoring semiprimes $N=21,33,35,39,55,57$, we find that the quantum computer still operates with acceptable performance (success probability of factoring) down to $b=2$. This is surprising since the deletion of rotation gates results in large errors in the arithmetic circuitry of the quantum computer. Extrapolating on the basis of these results we conclude that for quantum computers of practical interest more than 99% of rotation gates may be discarded with acceptable consequences in quantum computer performance. This result may be of interest to experimental physicists and quantum engineers currently embarked on designing efficient circuitry for scaling quantum computers.

Physical Review A•Dec 10, 2013•8 citations

The exact lower bound of CNOT-complexity for fault-tolerant quantum Fourier transform

Qiqing Xia, Huiqin Xie, Yang, Li

The quantum Fourier transform (QFT) is a crucial subroutine in many quantum algorithms. In this paper, we study the exact lower bound problem of CNOT gate complexity for fault-tolerant QFT. First, we consider approximating the ancilla-free controlled-$R_k$ in the QFT logical circuit with a standard set of universal gates, aiming to minimize the number of T gates. Various single-qubit gates are generated in addition to CNOT gates when the controlled-$R_k$ is decomposed in different ways, we propose an algorithm that combines numerical and analytical methods to exactly compute the minimum T gate count for approximating any single-qubit gate with any given accuracy. Afterwards, we prove that the exact lower bound problem of T gate complexity for the QFT is NP-complete. Furthermore, we provide the transversal implementation of universal quantum gates and prove that it has the minimum number of CNOT gates and analyze the minimum CNOT count for transversally implementing the T gate. We then exactly compute the exact lower bound of CNOT gate complexity for fault-tolerant QFT with the current maximum fault-tolerant accuracy 10^{-2}. Our work can provide a reference for designing algorithms based on active defense in a quantum setting.

arXiv:2409.02506•Sep 4, 2024•0 citations

Truncated phase-based quantum arithmetic: Error propagation and resource reduction

Gregory A. L. White, Charles D. Hill, Lloyd C. L. Hollenberg

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.

arXiv:2110.00217•Physical Review A•Nov 16, 2023•0 citations
Removing a single logical gate from a classical information processor renders this processor useless. This is not so for a quantum information processor. A large number of quantum gates may be removed without significantly affecting the processor's performance. In this paper, focusing on the quantum Fourier transform (QFT) and quantum adder, we show even more: Even if most of its gates are eliminated and the remaining gates are selected from a randomly generated set, the QFT, one of the most useful quantum processors, and the quantum adder, one of the most basic building blocks of a universal quantum computer, still operate with satisfactory success probability, comparable to that of a quantum computer constructed with perfect gates. We support these conclusions by first laying out a general analytical framework and then deriving analytical scaling relations, which are in excellent agreement with our numerical simulations. The demonstrated robustness of the QFT and quantum adder, to the point where randomly generated quantum gates take the place of the exact gates, is an important boon for the construction of quantum computers, since it shows that stringent gate error tolerances do not have to be met to obtain satisfactory performance of the corresponding quantum processors. Our analytical techniques are powerful enough to generate asymptotic scaling laws for any gate defect model of quantum information processors and we illustrate this point by explicitly computing asymptotic analytical scaling formulas for several other defect models as well.
Addressing Landauer's question concerning the influence of static gate defects on quantum information processor performance, we investigate analytically and numerically the case of the quantum Fourier transform (QFT) with defective controlled rotation (CROT) gates. Two types of defects are studied, separately and in combination: systematic and random. Analytical scaling laws of QFT performance are derived with respect to the number of qubits nnn, the size δ\deltaδ of systematic defects, and the size ϵ\epsilonϵ of random defects. The analytical results are in excellent agreement with numerical simulations. In addition, we present an unexpected result: The performance of the defective QFT does not deteriorate with increasing nnn, but approaches a constant that scales in ϵ\epsilonϵ. We derive an analytical formula that accurately reproduces the ϵ\epsilonϵ scaling of the performance plateaus. Overall, we observe that the CROT gates may exhibit static and random defects of the order of 30\% and larger, and still result in satisfactory QFT performance. Thus we answer Landauer's question in the case of the QFT: far from being lethal, the QFT can tolerate tremendous static gate defects and still perform its function. The extraordinary robustness of the QFT with respect to static gate defects displayed in our numerical and analytical calculations should be a welcome boon for laboratory and industrial realizations of quantum circuitry.
This thesis presents an overview of my published work on streamlining and optimizing quantum processors. Complete, microscopic, quantum-gate–by–quantum-gate simulations of a variety of quantum circuits are implemented and executed on state-of-the-art multi-processor parallel computers. A host of analytical scaling formulas addressing the quality of quantum processors, e.g., in the presence of realistic gate errors and defects, are presented. These formulas reliably describe the practically interesting, large-number-of-qubit regime, inaccessible to simulations on classical computers. Much of the technical details may be found in my published articles, which appear in the Appendix. This thesis also presents the generic and specific directions into which my current investigations are headed. In addition, several preliminary results are presented and discussed.
The quantum Fourier transform (QFT) is one of the most widely used quantum algorithms, ranging from its primary role in finding the periodicity hidden in a quantum state to its use in constructing a quantum adder. Testing how the QFT performs under more realistic conditions, we find that the QFT, when used for period finding, shows extraordinary robustness with respect to static gate defects. For instance, replacing all rotation angles $\ensuremath{\pi}/{2}^{j}$ of the controlled rotation gates in the QFT circuit by $\ensuremath{\pi}(1+r)/{2}^{j}$, where rrr is a uniformly distributed random variable taking values in the range $[\ensuremath{-}1,1]$, effectively resulting in a QFT with random gates, the QFT performs well above the expected random result. However, it is important to keep the 2j{2}^{j}2j terms in the denominators of the rotation angles, resulting in random, but hierarchically random, gates. Relaxing this hierarchical structure of the QFT circuit, we find that the performance of the QFT deteriorates significantly. This observation indicates that the hierarchical structure of the quantum circuit of the QFT is more important for the observed robustness in performance than the precise actions of individual gates. In addition to the specific example of the QFT circuit studied here, this observation also corroborates our experience with more general and more complex quantum circuits. Thus, backed by our detailed numerical and analytical results, we may condense the results of our research into the following general principle: The topology of a quantum circuit is more important than the precise actions of its gates.
Competing computationally with experimental groups for the construction of scaling quantum computers, we simulate a complete quantum-gate by quantum-gate implementation of Shor's algorithm on a classical 128-core cluster computer. The resulting virtual quantum computer serves as a convenient quantum laboratory for the investigation of the effect of defects in the quantum circuitry. The class of defects studied here is the removal of all rotation gates with rotation angles $\ensuremath{\theta}<\ensuremath{\pi}/{2}^{b}$. Factoring semiprimes N=21,33,35,39,55,57N=21,33,35,39,55,57N=21,33,35,39,55,57, we find that the quantum computer still operates with acceptable performance (success probability of factoring) down to b=2b=2b=2. This is surprising since the deletion of rotation gates results in large errors in the arithmetic circuitry of the quantum computer. Extrapolating on the basis of these results we conclude that for quantum computers of practical interest more than 99% of rotation gates may be discarded with acceptable consequences in quantum computer performance. This result may be of interest to experimental physicists and quantum engineers currently embarked on designing efficient circuitry for scaling quantum computers.
The quantum Fourier transform (QFT) is a crucial subroutine in many quantum algorithms. In this paper, we study the exact lower bound problem of CNOT gate complexity for fault-tolerant QFT. First, we consider approximating the ancilla-free controlled-RkR_kRk​ in the QFT logical circuit with a standard set of universal gates, aiming to minimize the number of T gates. Various single-qubit gates are generated in addition to CNOT gates when the controlled-RkR_kRk​ is decomposed in different ways, we propose an algorithm that combines numerical and analytical methods to exactly compute the minimum T gate count for approximating any single-qubit gate with any given accuracy. Afterwards, we prove that the exact lower bound problem of T gate complexity for the QFT is NP-complete. Furthermore, we provide the transversal implementation of universal quantum gates and prove that it has the minimum number of CNOT gates and analyze the minimum CNOT count for transversally implementing the T gate. We then exactly compute the exact lower bound of CNOT gate complexity for fault-tolerant QFT with the current maximum fault-tolerant accuracy 10^{-2}. Our work can provide a reference for designing algorithms based on active defense in a quantum setting.
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.