Large-Scale Simulation of Shor's Quantum Factoring Algorithm

arXiv (Cornell University)

Abstract

Shor's factoring algorithm is one of the most anticipated applications of quantum computing. However, the limited capabilities of today's quantum computers only permit a study of Shor's algorithm for very small numbers. Here we show how large GPU-based supercomputers can be used to assess the performance of Shor's algorithm for numbers that are out of reach for current and near-term quantum hardware. First, we study Shor's original factoring algorithm. While theoretical bounds suggest success probabilities of only 3-4 %, we find average success probabilities above 50 %, due to a high frequency of "lucky" cases, defined as successful factorizations despite unmet sufficient conditions. Second, we investigate a powerful post-processing procedure, by which the success probability can be brought arbitrarily close to one, with only a single run of Shor's quantum algorithm. Finally, we study the effectiveness of this post-processing procedure in the presence of typical errors in quantum processing hardware. We find that the quantum factoring algorithm exhibits a particular form of universality and resilience against the different types of errors. The largest semiprime that we have factored by executing Shor's algorithm on a GPU-based supercomputer, without exploiting prior knowledge of the solution, is 549755813701 = 712321 * 771781. We put forward the challenge of factoring, without oversimplification, a non-trivial semiprime larger than this number on any quantum computing device.

Authors 5

1. Dennis Willsch

   Forschungszentrum Jülich · Jülich Supercomputing Centre

   Affiliation as printed

   Jülich Supercomputing Centre , Institute for Advanced Simulation , Forschungszentrum Jülich , 52425 Jülich , Germany

   Jülich Supercomputing Centre, Institute for Advanced Simulation, Forschungszentrum Jülich, 52425 Jülich, Germany

2. Madita Willsch

   Forschungszentrum Jülich · Jülich Supercomputing Centre

   Affiliation as printed

   AIDAS , 52425 Jülich , Germany

   Jülich Supercomputing Centre , Institute for Advanced Simulation , Forschungszentrum Jülich , 52425 Jülich , Germany

   AIDAS, 52425 Jülich, Germany

   Jülich Supercomputing Centre, Institute for Advanced Simulation, Forschungszentrum Jülich, 52425 Jülich, Germany

3. Fengping Jin

   Forschungszentrum Jülich · Jülich Supercomputing Centre

   Affiliation as printed

   Jülich Supercomputing Centre , Institute for Advanced Simulation , Forschungszentrum Jülich , 52425 Jülich , Germany

   Jülich Supercomputing Centre, Institute for Advanced Simulation, Forschungszentrum Jülich, 52425 Jülich, Germany

4. Hans A. De Raedt

   University of Groningen · Forschungszentrum Jülich · Jülich Supercomputing Centre · Zernike Institute for Advanced Materials

   Affiliation as printed

   Jülich Supercomputing Centre , Institute for Advanced Simulation , Forschungszentrum Jülich , 52425 Jülich , Germany

   Zernike Institute for Advanced Materials , University of Groningen , Nijenborgh 4 , 9747 AG Groningen , The Netherlands

   Jülich Supercomputing Centre, Institute for Advanced Simulation, Forschungszentrum Jülich, 52425 Jülich, Germany

   Zernike Institute for Advanced Materials, University of Groningen, Nijenborgh 4, 9747 AG Groningen, The Netherlands

5. Kristel F. L. Michielsen Aachen Department of Physics

   Forschungszentrum Jülich · Jülich Supercomputing Centre · RWTH Aachen University

   Affiliation as printed

   AIDAS, 52425 Jülich, Germany

   Department of Physics, RWTH Aachen University, 52056 Aachen, Germany

   Jülich Supercomputing Centre, Institute for Advanced Simulation, Forschungszentrum Jülich, 52425 Jülich, Germany