Shor's Algorithm: The Quantum Approach to Factoring |…

What is Shor's Algorithm?

Shor's algorithm is a quantum algorithm designed to solve the discrete logarithm problem and integer factorization problems. It was developed by Peter Shor in 1994 and represents one of the first practical applications of quantum computing, demonstrating its potential to outperform classical computers for certain tasks.

The algorithm works on a quantum computer with multiple qubits and leverages principles such as modular exponentiation, quantum Fourier transform (QFT), and continued fractions to efficiently find factors of large integers.

Modular Exponentiation

At the heart of Shor's algorithm is the process of modular exponentiation, which involves computing $a^x mod N$. This operation is crucial because it helps in identifying patterns that can be used to find the period of a function. The result of this computation is essential for the subsequent steps of the algorithm.

For example, when factoring 15, you would compute powers of a number modulo 15 and look for repeating sequences.

live demo · related simulation● LIVE

Quantum Fourier Transform (QFT) Peaks

The quantum Fourier transform is used to extract the period of the function derived from modular exponentiation. The QFT converts the probability amplitudes in a superposition state into frequency components, which can be observed as peaks in a histogram.

These peaks correspond to the periods found during the computation and are critical for determining the factors of N.

Continued Fractions and Factor Extraction

Once the period is determined, continued fractions are used to extract the factors of N. The algorithm converts the period into a fraction and then uses this fraction to find the factors by solving a simple equation.

For instance, if the period is found to be 2 for $a^x mod 15$, you can use it to factorize 15 as $(a^{period/2} + 1)(a^{period/2} - 1)$. This method works because of the properties of modular arithmetic and the structure of the problem.

Frequently asked questions

How does Shor's algorithm compare to classical algorithms?

Classical algorithms like Pollard’s rho algorithm or the quadratic sieve are much slower for large numbers compared to Shor’s quantum algorithm. For sufficiently large N, Shor’s algorithm can factorize it in polynomial time, whereas classical methods take exponential time.

Why is Shor's algorithm significant?

Shor's algorithm demonstrates the potential of quantum computers to solve problems that are practically impossible for classical computers. It has profound implications for cryptography and security protocols based on integer factorization, such as RSA encryption.

Can Shor’s algorithm be implemented classically?

While the full power of Shor's algorithm can only be harnessed with a quantum computer, some aspects like modular exponentiation and continued fractions can be simulated classically. However, these classical simulations do not capture the speedup provided by quantum interference.

What are the practical limitations of Shor’s algorithm?

Shor's algorithm requires a large number of qubits and high-fidelity operations, which current technology struggles to achieve. Additionally, error correction and decoherence are significant challenges that need to be addressed for practical implementation.

Try it live

Everything above runs in your browser — open Shor Factoring Workbench: Modular Exponentiation, QFT Peaks and Continued Fractions and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Shor Factoring Workbench: Modular Exponentiation, QFT Peaks and Continued Fractions simulation