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

Austin G. Fowler and Lloyd C. L. Hollenberg
Phys. Rev. A 70, 032329 – Published 29 September 2004; Erratum Phys. Rev. A 75, 029905 (2007)

Abstract

Typical circuit implementations of Shor’s algorithm involve controlled rotation gates of magnitude π22L 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 π2d rotation gate to within δ=O(12d) 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 π64 if integers thousands of bits long are desired factored. Explicit fault-tolerant constructions of such gates are also discussed.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Received 15 December 2003

DOI:https://doi.org/10.1103/PhysRevA.70.032329

©2004 American Physical Society

Erratum

Authors & Affiliations

Austin G. Fowler and Lloyd C. L. Hollenberg

  • Centre for Quantum Computer Technology, School of Physics, University of Melbourne, Victoria 3010, Australia

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 70, Iss. 3 — September 2004

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×