Shor's Algorithm: Phasor-Sum Interference Map |…

What is Shor's Algorithm?

Shor's algorithm is a quantum computing method designed for efficiently factoring large composite numbers into their prime factors. It operates on the principles of quantum mechanics, specifically leveraging superposition and interference to achieve exponential speedup over classical algorithms.

The algorithm was developed by Peter Shor in 1994 and has profound implications for cryptography, as many security protocols rely on the difficulty of factoring large integers.

How Does It Work?

Shor's algorithm begins with a classical input: two numbers, N (the composite number to be factored) and a (a random integer coprime to N). The quantum part involves creating a superposition of states representing these inputs.

The core operation is the quantum Fourier transform (QFT), which maps the phase space of the quantum state into a frequency domain. This transformation helps identify periodicity, crucial for factoring.

live demo · related simulation● LIVE

Phasor-Sum Interference Map

In this visualization, each qubit is represented by a phasor in the complex plane, with its angle corresponding to the phase of the quantum state. The interference pattern emerges as these phasors are summed up.

Constructive and destructive interference patterns indicate periodicity, which can be used to find the period of the function f(x) = a^x mod N, essential for factoring N.

Recovering the Period

Once the QFT reveals the period k, it is converted back into a classical form using continued fractions. This process allows us to find two non-trivial factors of N: gcd(a^(k/2) + 1, N) and gcd(a^(k/2) - 1, N).

The success of Shor's algorithm hinges on the ability to accurately measure these periodic patterns and convert them into usable classical information.

Frequently asked questions

Why is Shor’s algorithm significant?

Shor’s algorithm demonstrates that quantum computers can solve problems intractable for classical computers, posing a threat to current cryptographic systems.

How does the QFT help find the period?

The QFT transforms the problem into a form where periodicity becomes visible as peaks in the interference pattern. These peaks correspond to the period k of the function f(x) = a^x mod N.

What is constructive and destructive interference in this context?

Constructive interference occurs when phasors align, amplifying their sum, while destructive interference happens when they cancel each other out. These patterns are crucial for identifying the period k.

Can Shor’s algorithm be used to factor any number?

Shor's algorithm is most effective with large composite numbers and requires that a and N are coprime. For small or trivial cases, classical methods remain more efficient.

Try it live

Everything above runs in your browser — open Shor's Algorithm: Phasor-Sum Interference Map and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Shor's Algorithm: Phasor-Sum Interference Map simulation