Improving large-Scale Simulation efficiency of Shor’s Quantum Factoring Algorithm

Abstract

Shor’s factoring algorithm is one of the most eagerly awaited applications of quantum computing, promising to revolutionise fields such as cryptography by efficiently factoring large integers, a task that is computationally intensive for classical computers. Currently, the limited capabilities of today's quantum computers allow for testing Shor’s algorithm only on very small numbers, as they do not yet possess the qubit count or error rates necessary to handle larger, more complex computations. In this study, we demonstrate how large GPU-based supercomputers can be leveraged to evaluate the performance of Shor’s algorithm on numbers that are beyond the reach of current and near-term quantum hardware. By simulating the algorithm on powerful classical machines, we can gain insights into its behaviour and performance under various conditions. Initially, we examine Shor’s original factoring algorithm and find that, despite theoretical success probabilities being quite low, the average success rates are significantly higher due to frequent "lucky" cases. These are instances where factorization succeeds even when the sufficient conditions of the algorithm are not met. This phenomenon suggests that practical implementations of Shor’s algorithm may benefit from a higher-than-expected probability of success. We then explore a robust post-processing method designed to increase the success probability of Shor’s algorithm to nearly one with just a single execution. This method involves additional classical computational steps that refine the output of the quantum algorithm, making the overall factorization process much more reliable. Finally, we analyse the effectiveness of this post-processing method in the presence of typical quantum processing hardware errors, such as decoherence and gate errors. Our findings show that the quantum factoring algorithm displays a unique form of universality and resilience against various errors. This resilience suggests that Shor’s algorithm, when combined with efficient post-processing techniques, can remain viable even in less-than-ideal quantum hardware environments. The largest semiprime we have factored using Shor’s algorithm on a GPU-based supercomputer, without prior knowledge of the factors, represents a significant milestone. It poses a formidable challenge for the quantum computing community to exceed without resorting to oversimplifications on any quantum computing device. This achievement underscores the potential of classical-quantum hybrid approaches in advancing our understanding and implementation of quantum algorithms.