Scalability of Shor's algorithm with a limited set of rotation gates

Abstract

Typical circuit implementations of Shor's algorithm involve controlled rotation gates of magnitude $\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 $\pi /2^d$ rotation gate to within $\delta =O(1/2^d)$ currently requires both a number of qubits and 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 $d_{\max }$. It is found that integers up to length $L_{\max }=O(4^{d_{\max }})$ 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 $\pi /64$ if integers thousands of bits long are desired factored. Explicit fault-tolerant constructions of such gates are also discussed.

Substantially revised version, twice as long as original. Two tables converted into one 8-part figure, new section added on the construction of arbitrary single-qubit rotations using only the fault-tolerant gate set. Substantial additional discussion and explanatory figures added throughout. (8 pages, 6 figures)

References in corpus (5)

• Good Quantum Error-Correcting Codes Exist
• Multiple Particle Interference and Quantum Error Correction
• Quantum Networks for Elementary Arithmetic Operations
• Charge-based quantum computing using single donors in semiconductors
• Spintronics and Quantum Dots for Quantum Computing and Quantum Communication

Cited by in corpus (19)

• Simulating chemistry efficiently on fault-tolerant quantum computers
• Approximate Quantum Fourier Transform with $O(n\log (n))$ T gates
• Efficient Decomposition of Single-Qubit Gates into $V$ Basis Circuits
• Arithmetic Circuits for Multilevel Qudits Based on Quantum Fourier Transform
• Designing a Million-Qubit Quantum Computer Using Resource Performance Simulator
• Large-Scale Simulation of Shor's Quantum Factoring Algorithm
• Scaling laws for Shor's algorithm with a banded quantum Fourier transform
• Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries
• Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise
• Towards Large-Scale Quantum Computation
• Logic Synthesis for Fault-Tolerant Quantum Computers
• Shor's factorization algorithm with a single control qubit and imperfections
• Effects of imperfections for Shor's factorization algorithm
• Distillation protocols for Fourier states in quantum computing
• Everything You Always Wanted to Know About Quantum Circuits
• Shor's Factoring Algorithm and Modular Exponentiation Operators
• The modular multiplication operator and the quantized bakers maps
• Entanglement and its Role in Shor's Algorithm
• Quantum Algorithms for Discrete Log Require Precise Rotations