This page simulates Shor's Algorithm for integer factorization with a quantum computer. Since this page runs in javascript on your non-quantum browser, the quantum part of the algorithm is simulated using probabilities.
In order for Shor's Algorithm to work, n has to be:
Uh-oh, your number didn't pass the test. Try another number!
Thus, n is the product of two coprime numbers greater than 1. As a consequence of the Chinese remainder theorem, 1 has at least four distinct roots modulo n, two of them being 1 and - 1. The aim of the algorithm is to find a square root b of 1, other than 1 and - 1; such a b will lead to a factorization of n. In turn, finding such a b is reduced to finding an element a of even period with another certain additional property. The quantum algorithm is used for finding the period of randomly chosen elements a, as order-finding is a hard problem on a classical computer.
Now, a number a between 1 and n exclusive is randomly picked. For illustration, you can pick it yourself, or hit the 'randomize' button to have a value generated for you. Press 'continue' to continue the algorithm.
Now, gcd(a,n) is calculated, using the Euclidean algorithm.
If the result of the gcd isn't 1, then the result is itself a non-trivial factor of n.
You got lucky! is a factor of
Otherwise, we need to find the period of a^x mod n. This is where the quantum part of the algorithm comes in. A graph of a^x mod n for a few values is shown below. With small numbers, it's easy to see the periodicity.
However, we're not going for simplicity, so it's time for the quantum part!
First, we're going to need a quantum register big enough to hold Q numbers, such that N^2 ≤ Q ≤ 2N^2 . This gives enough room to see the periodicity of a^x mod n, even if the period is close to N/2. Do to this, we need a 'q'-qubit wide quantum register.
For 15, we need 8 qubits (Q = 256). These qubits can represent the numbers from 0 to Q-1. These numbers are initialized so that measuring the state of the quantum register gives us a random number from 0 to Q-1 with equal probability.
To illustrate the state of the quantum register, here's a graph of the probability density function of measuring the register, where the X axis represents the value that would be measured. With a real quantum register, a graph like this could never actually be measured, since taking one reading would collapse all future readings.
Of course, it's a pretty boring graph, if everything went right.
It gets more interesting now, though. We're going to apply a tranform to the register based on the a^x mod n function, where the x is represented by each possible state of the quantum register. The cool thing with a real quantum computer is that every single calculation of a^x mod n is done in parallel by the property of superposition. The result is stored within a second quantum register, which looks like this:
There should be now only a few peaks, with the probability of any other state at 0. This is because after taking a^x mod n for every x, the periodicity of that function means only a few values will show up randomly with equal probability, if we took a measurement of the second register. Which we will now do.
Measurement:
After the measurement, the probabilities of measuring any other number from the register drop to 0 (and the probability of making the same measurement is now 1). Also, because the second register is transformed from the first, the first register's state also collapses slightly to not give any measurements but those that are consistent with the measurement of register 2 (due to quantum entanglement.) In other words, measuring register 1 now will only return values x where a^x mod n would equal . Register 1's pdf now looks like (higher values are truncated for clarity):
It should be now easy to see that the distance between the peaks of probability is the same as the period of a^x mod n. However, measureing the register now would just return the number represented by one of those peaks randomly. To measure the period (or something close to it), we need to apply a Quantum Fourier Transform to the register. Without boring you too much on the details of a Fourier Transform, the register's pdf now looks like this:
The peaks are at the places where the amplitude of the specific frequencies of the fourier series are the highest for the register. Specifically, they are at k * Q/r, where k is a random number between 0 to r-1, and r is the period, so measuring register 1 now will give us one specific k*Q/r (As long as we don't get k=0. For the purposes of this simulation, we're going to fudge the probabilities so we don't. With a real quantum computer, we'd just have to try again.)
k*Q/r:
Now, all that's left is postprocessing, which can be done on a classical computer.
Since the period is not neccesarily an even divisor of Q, we need to find a fraction with a denominator less than n (the number we're factoring) that is closest to k/r, or the number we measured divided by Q. Then, the period should be equal to the denominator.
Q:
k/r:
period:
For some periods, there's a good chance that the period is divisible by k, in which case the fraction will be reduced so the denominator is equal to some fraction of the actual period. Unfortunately, there's no real way to account for this, so if the factors are reported wrong below, try running the algorithm again.
From the period, we can determine a factor of n, but only if:
Looks like this run didn't make the cut. Try a different a!
With a usable period, the factors of n are simply gcd( a^(period/2) + 1, n) and gcd( a^(period/2) - 1, n):
if these numbers don't look right, you'll have to run the quantum part of the algorithm again, with different numbers :( Press the button below to automatically populate and measure the registers, and hopefully you'll get better results.
If you got the right factors, then cool, you got through Shor's Algorithm! Go tell your friends how much smarter you are than them!