Structure of Shor’s algorithm
Letโs talk about the structure of Peter Shorโs algorithm for factoring large numbers.
As we saw, a โquantumโ algorithm is really a hybrid quantum-classical algorithm. It begins with some classical processing, then uses the quantum computer to execute a particular part of the algorithm (a subroutine or function) and measures the result. It then takes those results and does some more classical post-processing. The quantum computer essentially serves as a coprocessor to the classical computer.
In the case of Shorโs algorithm, the quantum subroutine is known as the period finding routine, which uses an important technique known as the quantum Fourier transform, or QFT, to create interference that gives us the period. We then use a classical technique known as Euclidโs algorithm to find the prime factors of the number (N). We will go through each of these steps briefly, then there is an article for each of the parts that goes into more detail.
Fig.1. Block structure of Shorโs algorithm
Modulo Arithmetic
Recall that modulo arithmetic means that any time our result gets to be greater than or equal to the modulus, we subtract the modulus until weโre back between zero and that number minus one.
Doing arithmetic modulo ten is just like keeping track of only the last digit of any addition or multiplication operation, so for example (9 times 9 bmod 10) is just 1, rather than 81.
Consider a function where you add four every step, and do the whole thing modulo seven. If you start with zero, your sequence goes 0, 4, then it should go 8, but since 8 is greater than 7, we subtract 7 and weโre back to 1. Then the next step would be 5. Modulo seven, then, is just like doing math in base seven and keeping only the last digit.
The Period of a Function
A lot of mathematical functions are periodic. That is, if you start by evaluating the function in some place and move forward, eventually youโll come back to where you started. In fact, the entire sequence of values repeats itself. The time it takes for that repetition to occur is called the period.
Weโve already talked a lot about waves, so you might suspect that the period of a function is like the period of a wave. In fact, itโs exactly like that!
Rather than a continuous function like a sine wave, letโs look at what happens just with discrete steps, like modulo arithmetic. Go back to the function of adding four modulo seven, which we can write like this: (x_{i+1} = x_i + 4 bmod 7). Our sequence of numbers goes
[0, 4, 1, 5, 2, 6, 3, 0]
After seven steps we are back to zero, where we started. If you keep going, the sequence just repeats itself:
[0, 4, 1, 5, 2, 6, 3, 0, 4, 1, 5, 2, 6, 3, 0, 4, 1, 5, 2, 6, 3, โฆ]
Every 0 is seven steps apart, and even 4 is seven steps apart in that sequence. We say that the period of our function is seven, and we can say that
(f(x + 7) = f(x)).
The Quantum Fourier Transform
Select a prime number (a < N). It turns out that, if we can find the period (r) of the function (f(x) = a^x bmod N) as we increment the variable (x), then we can find the factors of (N). The simplest way to do this, of course, is just to repeat calculating (f(x)) until we find two identical results; the number of steps in between will be the period. While itโs theoretically possible, itโs impractical, because the period grows roughly exponentially as the length of the number grows. For large numbers, that period could be enormous, so big that we could calculate for the lifetime of the universe and never find the period. Itโs less efficient than the number field sieve we already have. We need a different approach.
A common classical technique for finding the frequency of a signal, which we can easily invert to find the period, is the Fourier transform. If we could take the Fourier transform of a sequence of these results, we might find the period. Doing so classically, unfortunately, would require data from a sequence of results like the one we just described. Still obviously impractical.
With a quantum computer, though, the finding of the period of a function suddenly becomes practical. We take all of the possible values of (x) in superposition, calculate (f(x)), and now we have a superposition of all of the function results. If we can pick two different values of (x) out of the superposition that produce the same (f(x)), then we can find the period.
Unfortunately, we canโt do that directly. As we have seen, any time you measure a superposition, you get one of the possible values randomly, depending on the quantum probability amplitudes. Finding only one value for (x) doesnโt help us at all. Instead, though, we can apply the quantum form of the Fourier transform (the QFT), and it will create interference among all of values of (x), in a fashion that lets us directly read out the period (r)!
Of course, this is still no help if either calculating (f(x)) or doing the QFT is computationally expensive. The modular exponentiation and the QFT both turn out to have a cost that is polynomial in the length of the number in bits, a profound reduction compared to the exponential effort necessary to find the period classically.
This is the core of Shorโs algorithm, and one of the most exciting technical results in any field in the last several decades, in our opinion.
Euclidโs Algorithm
The final classical step is take (r) and use it to find the factors. This is done on a classical computer, using Euclidโs algorithm for finding the greatest common denominator (gcd) of two numbers. Euclidโs algorithm is polynomial in the size of the numbers, and indeed is fairly fast on a classical computer, so there is no need to be concerned about the difficulty of this step.
Assuming we have correctly found the period (r), calculating the gcd of (N) with the numbers (a^{(r/2)}+1) and (a^{(r/2)}-1) will give us two prime factors of the number (N).
Putting It All Together
Summarizing, letโs assume weโre trying to factor the number (N), which is written using (n) bits. The algorithm consists of the following steps:
- Pick a prime number (a < N).
- Use Euclidโs algorithm to check if (a) is a factor of (N); if so, youโre done.
- Otherwise, prepare your quantum computer and a program for it to execute quantum period finding.
- The first important quantum step is to calculate the superposition of (a^x) for all values of (x), all done modulo (N). (|xrangle) and the remainder both appear in our quantum register.
- Measure the remainder. (Technically, this is unnecessary, but it simplifies the explanation, so we will assume we use it.)
- Take the quantum Fourier transform (QFT) of (|xrangle.)
- Measure the register (|xrangle); call the result (r), which should be a multiple of the period of the modular exponentiation function.
- If (r) is even and greater than zero, calculate the numbers (a^{(r/2)}+1) and (a^{(r/2)}-1); if not, rerun the quantum portion of the algorithm to find a new (r).
- Use Euclidโs algorithm to calculate the gcd of each of those numbers and (N), and you should have two factors of (N)!
Now, letโs go look at each of the individual techniques, before putting it all together.
ย
Shorใฎใขใซใดใชใบใ ใฎๆง้
Peter Shorใฎ็ด ๅ ๆฐๅ่งฃใขใซใดใชใบใ ใซใคใใฆ่ฆใฆใใใพใใใใ
็งใใกใ่ฆใใใใซใโ้ๅญโใขใซใดใชใบใ ใจใใใฎใฏๅฎ้ใฏใ้ๅญใจๅคๅ ธใฎใใคใใชใใใขใซใดใชใบใ ใงใใๅใใฏๅคๅ ธ่จ็ฎๆฉใง็จใใใใฆใใใใฎใใใใฎๅพ้ๅญใณใณใใฅใผใฟใซใใฃใฆใขใซใดใชใบใ ใฎ็นๅฎใฎ้จๅใๅฎ่ก๏ผ็นฐใ่ฟใใ้ขๆฐ๏ผใใใใจใซ็จใใใใใใฎ็ตๆใ่จๆธฌใใฆใใพใใใใใใฎ็ตๆใ็จใใใใๅคๅ ธ็ใชๅพๅฆ็ใซ็จใใใใฆใใพใใ้ๅญใณใณใใฅใผใฟใผใฏใๅคๅ ธใณใณใใฅใผใฟใฎ่ฃๅฉ็ใชใใญใปใใตใจใใฆๆดป่บใใใฎใงใใ
Shorใฎใขใซใดใชใบใ ใซใใใฆใฏใ้ๅญ็ใช็นฐใ่ฟใไฝๆฅญใฏใ็นฐใ่ฟใใฎๅไฝใ่ฆใคใใไธใงๅฉ็จใใใพใใใใใฏใ้ๅญใใผใชใจๅคๆ(Quantum Fourier Transform)ใจๅผใฐใใๆๆณใชใฉใซใใใฆใๅไฝใไธใใๆณขใฎๅนฒๆธใไฝใๅบใไธใง็จใใใใพใใ็งใใกใฏใใฎไธใงใ N ใฎ็ด ๅ ๆฐใ่ฆใคใใใใใซใใฆใผใฏใชใใใฎใขใซใดใชใบใ ๏ผใฆใผใฏใชใใใฎไบ้คๆณ๏ผใ็จใใพใใใใใใฎในใใใใ็ฐกๅใซ่ฆใฆใใใไธใคไธใคใฎ็ดฐใใ่จไบใ่ฆใฆใใใพใใใใ
Fig.1. Block structure of Shorโs algorithm
ใขใธใฅใญๆผ็ฎ
ใขใธใฅใญๆผ็ฎ๏ผmodใชใฉใจๅผใฐใใ)ใจใฏใๆณ๏ผๅบๆบใจใชใๆฐ(N)๏ผใซๅฏพใใฆ็ญใใใใพใใฏใฉใใ ใๅคงใใๆฐใซใชใฃใฆใใใใฎๆฐใ0ใใ(N โ 1)ใพใงใฎ้ใซใชใใพใงใ(N)ๅผใ็ถใใใใฎใงใใฃใใจ ใใใใจใๆใๅบใใฆใใ ใใใ
ใใฎmodใซใใใฆใฏใใฉใฎใใใชๅ ๆณใไนๆณใซใใใฆใใๆๅพใฎๆกใ่ฆใใ ใใงๆผ็ฎใๅฏ่ฝใงใใไพใใฐใ(9 times 9 bmod 10 equiv 1( neq 81))ใจใชใใพใใ
(bmod 7)ใงใๆฏๅ๏ผใ่ถณใใฆใใใจใใ้ขๆฐใ่ใใฆใฟใพใใใใ๏ผใใๅใใใจใใใจใ0, 4ใใใฆ8ใจใใใใใซๅขใใฆใใใพใใใ8ใฏ7ใใๅคงใใใฎใงใ7ใๅผใใฆใ1ใซๆปใใพใใใใใฆๅใณ4ใ่ถณใใฆ5ใจใชใใพใใ(bmod 7)ใจใใใฎใฏใ7ใๅบๆบใจใใๆฐๅญฆใจใชใใๆ็ตๆกใ ใใ่ฟฝใฃใฆใใใฐ่ฏใใฎใงใใ
้ขๆฐใฎๅจๆ
ๅคใใฎๆฐๅญฆ็้ขๆฐใฏๅจๆ็ใงใใใคใพใใใใฏใใใๅฐ็นใง้ขๆฐใ่ฉไพกใใคใคใๆฎตใ ใจๅ ใธ้ฒใใงใใใจใ็ตๆใฏ่ฉไพกใๅงใใ็นใซ่ฟใฅใใฆใใใจใใใใจใงใใๅฎ้ใฏใใทใผใฑใณในๅ จไฝใงใใใฎ็นฐใ่ฟใใ่กใใใฆใใพใใใใฎ็นฐใ่ฟใใซใใใๆ้ใฎๅคงใใใใๅจๆใจๅผใณใพใใ
็งใใกใฏๆณขใซใคใใฆใๆงใ ใซ่ฉฑใใฆใใพใใใใใฎใใใ้ขๆฐใฎๅจๆใจใฏใๆณขใฎๅจๆใฎใใใชใใฎใจ่ใใใใใใใพใใใๅฎ้ใใใฎใใใชใใฎใชใฎใงใ๏ผ
ๆญฃๅผฆๆณขใฎใใใชใ้ฃ็ถ้ขๆฐใงใฏใชใใใขใธใฅใญๆผ็ฎใฎใใใช้ขๆฃ็ใช้ขๆฐใซใคใใฆ่ฆใฆใใใพใใใใ(bmod 7)ใงใ๏ผใๅ ใใฆใใ้ขๆฐใซใคใใฆ่ฆใฆใใใพใใใใใใใ่กจใใจใใฎใใใซใชใใพใใ(x_{i+1} = x_i + 4 bmod 7)ๆฐๅญใฎ้ ็ชใจใใฆใฏใ
[0,4,1,5,2,6,3,0]
ใจใใใใใซใชใใพใใ 7ๆฎต้่ธใใ ใใจใๅใใจๅใ0ใซๆปใใพใใใใใ็นฐใ่ฟใใฆใใใจใไธใฎใใใซใๅใๆฐๅญใฎ็นฐใ่ฟใใ็พใใพใใ
[0,4,1,5,2,6,3,0,4,1,5,2,6,3,0,4,1,5,2,6,3,โฆ]
0ใ4ใๅ จใฆใฎๆฐๅญใใ7ใคใใใซๅบใฆใใฆใใพใใใใฎใใใใใฎ้ขๆฐใฎๅจๆใฏ7ใงใใใจ่จใใใจใใงใใพใใใใใฆใใใ่กจใใจใ
[f(x+7)=f(x)]
ใจใใใใใซๆธใใใจใใงใใพใใ
้ๅญใใผใชใจๅคๆ
(a < N)ใๆบใใ็ด ๆฐใไธใค้ธใณใพใใใใฎๆฐใซใคใใฆ(f(x) = a^x bmod N)ใจใใ้ขๆฐ(r)ใฎๅจๆใ็บ่ฆใงใใๅ ดๅใ(N)็ด ๅ ๆฐใ็ฅใใใจใใงใใพใใๆใๅ็ดใชๆนๆณใฏใใกใใใ(f(x))ใ2ใคใฎๅใ็ตๆใๅพใใใใพใง่จ็ฎใ็ถใใใใจใงใใ็ขบๅฎใซๅจๆใพใงใฎๆฎต้ใง็ตใใใใใใจใๅฏ่ฝใงใใใใใฏ็่ซ็ใซใฏๅฏ่ฝใงใใใ็พๅฎ็ใงใฏใใใพใใใใชใใชใใๆฐใๅคงใใใชใใซ้ฃใใฆใๅจๆใฏๆๆฐ้ขๆฐ็ใซๅคงใใใชใฃใฆใใใใใงใใใใใฏใใใงใซใใใใใชๆฐใฎใตใใใจๅผใฐใใๆๆณใใใใๅน็็ใงใฏใใใพใใใไปใฎๆๆณใๅฟ ่ฆใจใชใใพใใ
้ขๆฐใฎๅจๆใ่ฆใคใใใใใซใๅ่ปขใใใใไฟกๅทใฎๅจๆณขๆฐใ่ฆใคใใใใใฎใๅคๅ ธ็ๆๆณใจใใฆใใใผใชใจๅคๆใ็จใใใใพใใใใใใใใฎ็ตๆใฎ้ฃ็ถๅคใฎใใผใชใจๅคๆใฎๅคใๅพใใใจใใงใใใฐใๅจๆใๅพใใใจใใงใใพใใไธ้ใซใใใใพใใซๅคๅ ธ็ใซ่กใใจใ็งใใกใๆใใใใใช็ตๆใฎใทใผใฑใณในใใใใผใฟใๅใใชใใใฐใชใใชใใชใฃใฆใใพใใพใใ
ใใใ้ๅญใณใณใใฅใผใฟใผใซใใใฆใฏใ้ขๆฐใฎๅจๆใ่ฆใคใใใใจใฏ้ๅธธใซ็พๅฎ็ใซใชใฃใฆใใพใใๅ จใฆใฎๅฏ่ฝใชๅค(x)ใ้ใญๅใใ็ถๆ ใจใใ(f(x))ใ่จ็ฎใใพใใใใใใใใจใงใ้ขๆฐใฎ็ตๆใฎๅ จใฆใฎ้ใญๅใใ็ถๆ ใๅพใใใจใใงใใพใใใใ2ใคใฎ็ฐใชใๅค(x)ใๅใ(f(x))ๅคใ่ฟใใใจใใใใใใใฎ้ขๆฐใฎๅจๆใจใชใใพใใ
ไธ้ใซใใ็งใใกใฏใใใ็ดๆฅ่กใใใจใฏใงใใพใใใไปใพใง่ฆใฆใใใใใซใ้ใญๅใใใฎ็ถๆ ใ่ฆณๆธฌใใใใจใใใจใ้ๅญ็็ขบ็ใฎๆฏๅน ใซไพๅญใใใใฉใณใใ ใชๅคใๅบใฆใใฆใใพใใพใใ(x)ใฎๅคไธใคใ ใใงใฏๅ จใๅฝนใซ็ซใกใพใใใใใฎใใใใใใผใชใจๅคๆใ้ๅญๅฝขๅผใซๅฟ็จใใฆใ(x)ใฎๅ จใฆใฎ้ใงๅนฒๆธใไฝๆใใใใจใงใๆฒใใใชใใซใๅจๆ(r)ใ็ดๆฅๅพใใใจใใงใใพใใ
ใใกใใใใใใฏ(f(x))ใฎ่จ็ฎใใ้ๅญใใผใชใจๅคๆใใๆ่ก็ใซๅณใใใจๅฝนใซใฏ็ซใกใพใใใๅชๅฐไฝใจ้ๅญใใผใชใจๅคๆใฏใๆฐใฎๅคงใใใซใใฃใฆใๅค้ ๅผๆ้ใงใฎ่จ็ฎใณในใใใใใใๅคๅ ธ็ๆนๆณใงๅจๆใ่ฆใคใใ่ถ ๅค้ ๅผ็ใชๆ้ใซๆฏในใใจใ่จ็ฎๆ้ใ้ๅธธใซๅๆธใงใใพใใ
ใใใฏShorใฎใขใซใดใชใบใ ใฎไธญๅฟใงใไปๅพๆฐๅๅนดใงๆใๆ่ก็็ตๆใฎๅบใใใชๅ้ใฎไธใคใซใชใใจๆใใพใใ
ใฆใผใฏใชใใใฎใขใซใดใชใบใ
ๆๅพใฎๅคๅ ธ็ๆฎต้ใฏใๅจๆ(r)ใ็บ่ฆใใใใใ็จใใฆ็ด ๅ ๆฐใ็บ่ฆใใใใจใงใใใใใฏๅคๅ ธใณใณใใฅใผใฟใงใ2ใคใฎๆฐใฎๆๅคงๅ ฌ็ดๆฐใ่ฆใคใใใใใฎใใฆใผใฏใชใใใฎใขใซใดใชใบใ ใ็จใใฆ่กใใใพใใใฆใผใฏใชใใใฎใขใซใดใชใบใ ใฏๆฐๅญใฎๅคงใใใซใใฃใฆๅค้ ๅผๆ้็ใซ่จ็ฎๆ้ใๅคๅใใๅฎ้ใๅคๅ ธใณใณใใฅใผใฟใจ่จ็ฎ้ๅบฆใฏๅคๅใใชใใใใใใฎในใใใใฏ้ฃใใ่ใใๅฟ ่ฆใฏใใใพใใใ
ๅจๆ(r)ใๆญฃใใ่ฆใคใใใใใจใใใจใ(N)ใจ(a^{(r/2)}+1)ใจ(a^{(r/2)}-1)ใฎๆๅฐๅ ฌๅๆฐใ่ฆใคใใใใจใงใ(N)ใฎ็ด ๅ ๆฐใๅฐใใใจใใงใใพใใ
ไปฅไธใฎใพใจใ
(n)bitใง่กจใใใใ(N)ใฎ็ด ๅ ๆฐใฎๆฑใๆนใใใใใใใฆใฟใพใใใใใขใซใดใชใบใ ใฏไปฅไธใฎในใใใใงๆงๆใใใฆใใพใใ
- (N)ใใๅฐใใ็ด ๆฐ(a)ใ้ธใถ
- (a)ใใ(N)ใฎ็ด ๅ ๆฐใงใใใใ็ขบใใใพใใใใใใใงใใใฐใใใง็ตใใใงใใ
- ใใใงใชใๅ ดๅใ้ๅญใณใณใใฅใผใฟใจใใญใฐใฉใ ใ็จใใฆใๅจๆใๆฑใใพใใ
- ้ๅญใณใณใใฅใผใฟใซใใใๆใ้่ฆใชในใใใใฏใๅ จใฆใฎ(x)ใซๅฏพใใ(a^x)้ใญๅใใ็ถๆ ใ่จ็ฎใใใใจใงใใๅ จใฆ(bmod N) ใซใใฃใฆ่กใใใพใใ(vert xrangle)ใจใใพใใฏใฉใกใใ้ๅญใฌใธในใฟใฎไธญใซ็พใใพใใ
- ไฝใใ่จ็ฎใใพใใ๏ผๆ่ก็ใซใฏๅฟ ่ฆใใใพใใใใ่ชฌๆใ็ฐกๅใซใใใใใซใใใฎๆๆณใ็จใใฆใใใพใใ)
- (vert xrangle)ใซๅฏพใใฆ้ๅญใใผใชใจๅคๆใ่กใใพใใ
- ใฌใธในใฟ(vert xrangle)ๆธฌๅฎใใพใใใใฎ็ตๆใฏใๅชๅฐไฝใฎๅจๆใฎๅฎๆฐๅใจใชใฃใฆใใพใใ
- ใใ(r)ใ0ใใๅคงใใใใฐ(a^{(r/2)}+1)ใจ(a^{(r/2)}-1)ใ่จ็ฎใใ0ใพใใฏ0ใใๅฐใใใฎใชใใฐใๆฐใใ(r)ใ่ฆใคใใใใใซๅใณ้ๅญ่จ็ฎใธๆปใใพใใ
- ใฆใผใฏใชใใใฎใขใซใดใชใบใ ใ็จใใฆใๅๅคใจ(N)ใฎๆๅคงๅ ฌ็ดๆฐใๆฑใใใใจใงใ(N)ใฎ็ด ๅ ๆฐใงใใ2ใคใฎๆฐๅญใๅพใใใจใใงใใพใใ
ๅใ ใฎๆ่กใซใคใใฆใใใ่ฉณใใ่ฆใฆใใใพใใใใ
Share this
Reach your personal and professional goals
Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.
Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.
Register to receive updates
-
Create an account to receive our newsletter, course recommendations and promotions.
Register for free