Large-scale simulation of Shor's quantum factoring algorithm

• URL: http://arxiv.org/abs/2308.05047v1
• Date: Wed, 9 Aug 2023 16:19:52 GMT
• Title: Large-scale simulation of Shor's quantum factoring algorithm
• Authors: Dennis Willsch, Madita Willsch, Fengping Jin, Hans De Raedt, Kristel Michielsen
• Abstract summary: We show how large GPU-based supercomputers can be used to assess the performance of Shor's algorithm. We find average success probabilities above 50 %, due to a high frequency of "lucky" cases. We find that the quantum factoring algorithm exhibits a particular form of universality and resilience against the different types of errors.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• A quantum implementation of high-order power method for estimating geometric entanglement of pure states [39.58317527488534]
  This work presents a quantum adaptation of the iterative higher-order power method for estimating the geometric measure of entanglement of multi-qubit pure states. It is executable on current (hybrid) quantum hardware and does not depend on quantum memory. We study the effect of noise on the algorithm using a simple theoretical model based on the standard depolarising channel.
  arXiv  Detail & Related papers  (2024-05-29T14:40:24Z)
• Scalable Quantum Algorithms for Noisy Quantum Computers [0.0]
  This thesis develops two main techniques to reduce the quantum computational resource requirements. The aim is to scale up application sizes on current quantum processors. While the main focus of application for our algorithms is the simulation of quantum systems, the developed subroutines can further be utilized in the fields of optimization or machine learning.
  arXiv  Detail & Related papers  (2024-03-01T19:36:35Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• On proving the robustness of algorithms for early fault-tolerant quantum computers [0.0]
  We introduce a randomized algorithm for the task of phase estimation and give an analysis of its performance under two simple noise models. We calculate that the randomized algorithm can succeed with arbitrarily high probability as long as the required circuit depth is less than 0.916 times the dephasing scale.
  arXiv  Detail & Related papers  (2022-09-22T21:28:12Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
  We introduce a reduced version of Shor's algorithm that proposes a step forward in increasing the range of numbers that can be factorized on noisy Quantum devices. In particular, we have found noteworthy results in most cases, often being able to factor the given number with only one of the proposed algorithm.
  arXiv  Detail & Related papers  (2021-12-23T15:36:59Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)
• Quadratic Sieve Factorization Quantum Algorithm and its Simulation [16.296638292223843]
  We have designed a quantum variant of the second fastest classical factorization algorithm named "Quadratic Sieve" We have constructed the simulation framework of quantized quadratic sieve algorithm using high-level programming language Mathematica.
  arXiv  Detail & Related papers  (2020-05-24T07:14:19Z)
• An Application of Quantum Annealing Computing to Seismic Inversion [55.41644538483948]
  We apply a quantum algorithm to a D-Wave quantum annealer to solve a small scale seismic inversions problem. The accuracy achieved by the quantum computer is at least as good as that of the classical computer.
  arXiv  Detail & Related papers  (2020-05-06T14:18:44Z)
• A Gentle Introduction to Quantum Computing Algorithms with Applications to Universal Prediction [21.344529157722366]
  This technical report gives an elementary introduction to Quantum Computing for non-physicists. We describe some of the foundational Quantum Algorithms including: the Deutsch-Jozsa Algorithm, Shor's Algorithm, Grocer Search, and Quantum Counting Algorithm. We then attempt to use Quantum computing to find better algorithms for the approximation of Solomonoff Induction.
  arXiv  Detail & Related papers  (2020-04-29T11:46:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.