What is the fastest algorithm for factoring large integers using quantum computers?

1 Shor's algorithm

The fastest known algorithm for factoring large integers using quantum computers is Shor's algorithm, named after Peter Shor, who proposed it in 1994. Shor's algorithm can factor any integer N in polynomial time, that is, in a number of steps that grows as a power of the number of digits of N. In contrast, the best classical algorithms take exponential time, that is, a number of steps that grows exponentially with the number of digits of N. Shor's algorithm works by finding the period of a function related to N, which can be done efficiently using quantum Fourier transform, a quantum analogue of the discrete Fourier transform.

2 Quantum Fourier transform

Quantum Fourier transform (QFT) is a key ingredient of Shor's algorithm, and many other quantum algorithms. QFT is a linear transformation that maps a quantum state of n qubits, which can represent 2^n complex amplitudes, to another quantum state of n qubits, which can represent the coefficients of a discrete Fourier series. QFT can be implemented using a circuit of n(n+1)/2 quantum gates, which is much faster than the classical fast Fourier transform, which requires n2^n classical gates. QFT can reveal hidden periodicities and symmetries in quantum states, which can be useful for solving mathematical problems.

3 Period finding

Period finding is the main mathematical problem that Shor's algorithm solves to factor large integers. Period finding is the problem of finding the smallest positive integer r such that f(x) = f(x+r) for some function f and some integer x. For example, if f(x) = x^2 mod 15, then the period of f is 4, because f(x) = f(x+4) for any x. Shor's algorithm uses QFT to find the period of the function f(x) = a^x mod N, where a is a random integer coprime with N, the integer to be factored. The period of this function is related to the factors of N by Fermat's little theorem.

5 Cryptography applications

The main application of Shor's algorithm for factoring large integers using quantum computers is to break the security of some widely used cryptographic schemes, such as RSA and Diffie-Hellman. These schemes rely on the assumption that factoring large integers is hard for classical computers, and therefore, they use large prime numbers as keys to encrypt and decrypt messages. However, if quantum computers can run Shor's algorithm efficiently, they can factor these large integers and recover the keys, rendering these schemes vulnerable. This poses a serious threat to the current and future security of many communication and information systems.

6 Number theory implications

Another application of Shor's algorithm for factoring large integers using quantum computers is to advance the field of number theory, which studies the properties and relationships of integers. Factoring large integers is a fundamental problem in number theory, and many open questions and conjectures depend on it. For example, the Riemann hypothesis, one of the most famous and important unsolved problems in mathematics, is equivalent to finding an efficient algorithm for factoring integers of the form N = p^k, where p is prime and k is a positive integer. If quantum computers can run Shor's algorithm, they can potentially solve or disprove some of these problems and conjectures, or at least provide new insights and data.

7 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?