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.
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θ<\ensuremathπ/2b. 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.
We constructed a virtual quantum computer by running a complete, scaling, quantum-gate--by--quantum-gate implementation of Shor's algorithm on a 128-core classical cluster computer. In mode A [quantum period finding (PF) only, supplied with classical results for the modular exponentiation (ME) part of Shor's algorithm], factoring semiprimes up to N=557993 with up to n=39 qubits, we confirm earlier, smaller-n results concerning the performance scaling of Shor's algorithm equipped with a truncated (banded) quantum Fourier transform. Running our virtual quantum computer in mode B (full quantum implementation of ME and PF), we find that a large number of gates may be discarded in a scalable way in both the ME and PF parts of Shor's algorithm in exchange for only a small reduction in performance. We explicitly state the associated scaling laws. Implying significant savings in quantum gates, we suggest that these results are of importance for future experimental and technical large-n implementations of quantum computers.
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.
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 δ of systematic defects, and the size ϵ 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 ϵ. We derive an analytical formula that accurately reproduces the ϵ 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.
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.
Typical circuit implementations of Shor's algorithm involve controlled rotation gates of magnitude $\ensuremath{\pi}∕{2}^{2L}$ where L is the binary length of the integer N to be factored. Such gates cannot be implemented exactly using existing fault-tolerant techniques. Approximating a given controlled $\ensuremath{\pi}∕{2}^{d}$ rotation gate to within $\ensuremath{\delta}=O(1∕{2}^{d})$ currently requires both a number of qubits and a number of fault-tolerant gates that grows polynomially with d. In this paper we show that this additional growth in space and time complexity would severely limit the applicability of Shor's algorithm to large integers. Consequently, we study in detail the effect of using only controlled rotation gates with d less than or equal to some dmax. It is found that integers up to length Lmax=O(4dmax) can be factored without significant performance penalty implying that the cumbersome techniques of fault-tolerant computation only need to be used to create controlled rotation gates of magnitude $\ensuremath{\pi}∕64$ if integers thousands of bits long are desired factored. Explicit fault-tolerant constructions of such gates are also 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 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 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.