Abstract We decompose two implementations of Shor’s algorithm for prime factorization into universal gate units at the logical level and predict the number of physical qubits and execution time when surface codes are used. Logical qubit encoding using a rotated surface code and logical qubits with all-to-all connectivity are assumed. We express the number of physical qubits and execution time in terms of the bit length of the number to be factorized and error rate of the physical quantum gate. We confirm the relationship between the number of qubits and the execution time by analyzing two algorithms using various bit lengths and physical gate error rates .
Abstract We decompose two implementations of Shor’s algorithm for prime factorization into universal gate units at the logical level and predict the number of physical qubits and execution time when surface codes are used. Logical qubit encoding using a rotated surface code and logical qubits with all-to-all connectivity are assumed. We express the number of physical qubits and execution time in terms of the bit length of the number to be factorized and error rate of the physical quantum gate. We confirm the relationship between the number of qubits and the execution time by analyzing two algorithms using various bit lengths and physical gate error rates .
We estimate the number of physical qubits and execution time by decomposing an implementation of Shor's algorithm for elliptic curve discrete logarithms into universal gate units at the logical level when surface codes are used. We herein also present modified quantum circuits for elliptic curve discrete logarithms and compare our results with those of the original quantum circuit implementations at the physical level. Through the analysis, we show that the use of more logical qubits in quantum algorithms does not always lead to the use of more physical qubits. We assumed using rotated surface code and logical qubits with all-to-all connectivity. The number of physical qubits and execution time are expressed in terms of bit length, physical gate error rate, and probability of algorithm failure. In addition, we compare our results with the number of physical qubits and execution time of Shor's factoring algorithm to assess the risk of attack by quantum computers in RSA and elliptic curve cryptography.
We show how the execution time of algorithms on quantum computers depends on the architecture of the quantum computer, the choice of algorithms (including subroutines such as arithmetic), and the ``clock speed'' of the quantum computer. The primary architectural features of interest are the ability to execute multiple gates concurrently, the number of application-level qubits available, and the interconnection network of qubits. We analyze Shor's algorithm for factoring large numbers in this context. Our results show that, if arbitrary interconnection of qubits is possible, a machine with an application-level clock speed of as low as one-third of a (possibly encoded) gate per second could factor a 576-bit number in under one month, potentially outperforming a large network of classical computers. For nearest-neighbor-only architectures, a clock speed of around twenty-seven gates per second is required.
Abstract We consider Shor’s quantum factoring algorithm in the setting of noisy quantum gates. Under a generic model of random noise for (controlled) rotation gates, we prove that the algorithm does not factor integers of the form pq when the noise exceeds a vanishingly small level in terms of n —the number of bits of the integer to be factored, where p and q are from a well-defined set of primes of positive density. We further prove that with probability 1 − o (1) over random prime pairs ( p, q ), Shor’s factoring algorithm does not factor numbers of the form pq , with the same level of random noise present.
Quantum computers have the potential to perform computational tasks beyond the reach of classical machines. A prominent example is Shor's algorithm for integer factorization and discrete logarithms, which is of both fundamental importance and practical relevance to cryptography. However, due to the high overhead of quantum error correction, optimized resource estimates for cryptographically relevant instances of Shor's algorithm require millions of physical qubits. Here, by leveraging advances in high-rate quantum error-correcting codes, efficient logical instruction sets, and circuit design, we show that Shor's algorithm can be executed at cryptographically relevant scales with as few as 10,000 reconfigurable atomic qubits. Increasing the number of physical qubits improves time efficiency by enabling greater parallelism; under plausible assumptions, the runtime for discrete logarithms on the P-256 elliptic curve could be just a few days for a system with 26,000 physical qubits, while the runtime for factoring RSA-2048 integers is one to two orders of magnitude longer. Recent neutral-atom experiments have demonstrated universal fault-tolerant operations below the error-correction threshold, computation on arrays of hundreds of qubits, and trapping arrays with more than 6,000 highly coherent qubits. Although substantial engineering challenges remain, our theoretical analysis indicates that an appropriately designed neutral-atom architecture could support quantum computation at cryptographically relevant scales. More broadly, these results highlight the capability of neutral atoms for fault-tolerant quantum computing with wide-ranging scientific and technological applications.
We significantly reduce the cost of factoring integers and computing discrete logarithms in finite fields on a quantum computer by combining techniques from Shor 1994, Griffiths-Niu 1996, Zalka 2006, Fowler 2012, Ekerå-Håstad 2017, Ekerå 2017, Ekerå 2018, Gidney-Fowler 2019, Gidney 2019. We estimate the approximate cost of our construction using plausible physical assumptions for large-scale superconducting qubit platforms: a planar grid of qubits with nearest-neighbor connectivity, a characteristic physical gate error rate of 10 − 3 , a surface code cycle time of 1 microsecond, and a reaction time of 10 microseconds. We account for factors that are normally ignored such as noise, the need to make repeated attempts, and the spacetime layout of the computation. When factoring 2048 bit RSA integers, our construction's spacetime volume is a hundredfold less than comparable estimates from earlier works (Van Meter et al. 2009, Jones et al. 2010, Fowler et al. 2012, Gheorghiu et al. 2019). In the abstract circuit model (which ignores overheads from distillation, routing, and error correction) our construction uses 3 n + 0.002 n lg n logical qubits, 0.3 n 3 + 0.0005 n 3 lg n Toffolis, and 500 n 2 + n 2 lg n measurement depth to factor n -bit RSA integers. We quantify the cryptographic implications of our work, both for RSA and for schemes based on the DLP in finite fields.
The publication in 1994 of Shor's algorithm, which allows factorisation of composite number N in a time polynomial in its binary length L has been the primary catalyst for the race to construct a functional quantum computer. However, it seems clear that any practical system that may be developed will not be able to perform completely error free quantum gate operations or shield even idle qubits from inevitable error effects. Hence, the practicality of quantum algorithms needs to be investigated to not only determine limitations on such algorithms in a noisy quantum computer, but also to estimate what demands must be made of quantum error correction (QEC). Shor's algorithm is a combination of both classical pre and post-processing, and also a quantum period finding subroutine (QPF) which allows for the exponential speed up of this algorithm on a quantum device. This paper will look at the stability of this quantum subroutine under the effects of several error models. Direct simulation of the entire QPF subroutine required to factorise a given composite number N in the presence of errors shows that the circuit required to implement Shor's algorithm is very sensitive to a small number of errors within the entire calculation. Well designed and efficient error correction codes, quick gate times and very low gate error rates will be essential for any physical realisation of Shor's factoring algorithm.