Quantum Period Finding
Now that we understand what the quantum Fourier transform (QFT) does, and we know what the period of a function is, we can talk about how the QFT is used to execute the period finding function.
You probably have a pretty good idea how this works already. In the last phase of the discussion of the QFT, we saw that the QFT operating on a superposition state behaves in striking ways. If the input superposition is something like (|0rangle+|4rangle) then some of the terms cancel, and the output is (|0rangle+|2rangle+|4rangle+|6rangle).
Note that all of the values in the output superposition are multiples of two. Two happens to be the number of terms in our input superposition! Is that significant?
Turns out that it is. We can set up our algorithm so that the number of terms in that output superposition is the period of the function.
Letโs walk through an example. Can we factor the number (N = 21) using Shorโs algorithm? Consider the sequence (2^i), for some long series of numbers:
(2^0 = 1 bmod 21 = 1)
(2^1 = 2 bmod 21 = 2)
(2^2 = 4 bmod 21 = 4)
(2^3 = 8 bmod 21 = 8)
(2^4 = 16 bmod 21 = 16)
(2^5 = 32 bmod 21 = 11)
(2^6 = 64 bmod 21 = 1)
(2^7 = 128 bmod 21 = 2)
(vdots)
(Instead of 2, we could have picked almost any number greater than one and less than the number we are trying to factor, but 2 makes a nice, simple case. Sometimes by accident we choose a number that doesnโt work well, but that should be rare.)
We can see that every six steps we come back to 1. The period of this function is six. If we write out the sequence, we get (1, 2, 4, 8, 16, 11, 1, 2, 4, 8, 16, 11, 1, 2, 4, 8, 16, 11, 1, โฆ).
Letโs pair each input number with its output number:
input | โ | output | ย | input | โ | output |
---|---|---|---|---|---|---|
0 | โ | 1 | ย | 13 | โ | 2 |
1 | โ | 2 | ย | 14 | โ | 4 |
2 | โ | 4 | ย | 15 | โ | 8 |
3 | โ | 8 | ย | 16 | โ | 16 |
4 | โ | 16 | ย | 17 | โ | 11 |
5 | โ | 11 | ย | 18 | โ | 1 |
6 | โ | 1 | ย | 19 | โ | 2 |
7 | โ | 2 | ย | 20 | โ | 4 |
8 | โ | 4 | ย | 21 | โ | 8 |
9 | โ | 8 | ย | 22 | โ | 16 |
10 | โ | 16 | ย | 23 | โ | 11 |
11 | โ | 11 | ย | 24 | โ | 1 |
12 | โ | 1 | ย | โฆ | ย | ย |
and on and on. Now, letโs sort those lines by the output number:
input | โ | output | ย | input | โ | output |
---|---|---|---|---|---|---|
0 | โ | 1 | ย | 3 | โ | 8 |
6 | โ | 1 | ย | 9 | โ | 8 |
12 | โ | 1 | ย | 15 | โ | 8 |
18 | โ | 1 | ย | 21 | โ | 8 |
24 | โ | 1 | ย | 4 | โ | 16 |
1 | โ | 2 | ย | 10 | โ | 16 |
7 | โ | 2 | ย | 16 | โ | 16 |
13 | โ | 2 | ย | 22 | โ | 16 |
19 | โ | 2 | ย | 5 | โ | 11 |
2 | โ | 4 | ย | 11 | โ | 11 |
8 | โ | 4 | ย | 17 | โ | 11 |
14 | โ | 4 | ย | 23 | โ | 11 |
20 | โ | 4 | ย | โฆ | ย | ย |
In Shorโs algorithm, the modular exponentiation step does exactly this. It groups input values that all have the same output value: give me a list of all of the values for (x) for which (2^x bmod 21) equals the same value.
Before we run the QFT, we measure some of our qubits (just the ones holding the output value), which causes the quantum state to partially collapse. This measurement causes one of the output values to be picked at random. If the output value we find is 1, for example, we would have left a superposition like this:
[|0rangle+|6rangle+|12rangle+|18rangle+|24rangle โฆ]
If instead we found the output value 11, we would have the list
[|5rangle+|11rangle+|17rangle+|23rangle+|29rangle โฆ]
In any case, we have a superposition with the period six.
If we have nine qubits, there are (2^9 = 512) basis states, 0 through 511, and we are creating interference across them. Since we have divided them up into 6 roughly equal sets, there are about (512/6 approx 85) members of each set. This number shows up in the QFT of our superposition
where the peaks (corresponding to high probability of being measured) appear at 0, 85, 171, 256, 341, and 427. As you can see in the picture, the six peaks arenโt all the same size, but they are all between 11% and 17%, so very, very roughly we can say that there is a similar probability of getting each of those results when we measure our register at the end of the quantum part of the computation.
Once we have the result, we then take that and turn it into the period. If we measure and find, for example, the value 85, then we use the value (512 / 85 approx 6). The procedure for finding the period is actually a little more complicated than this, but we donโt need to go into the details. That complexity is needed when we get one of the numbers larger than 85, which will happen most of the time. Occassionally, we find the number 0 when we measure, which we canโt use, so we rerun the quantum part of the algorithm and hope for a different result the next time, which probability suggests we are likely to get.
The Final Step: Euclid
Earlier, we saw how Euclidโs algorithm can be used to find the greatest common denominator (gcd) of two integers. Now, weโre going to need it.
Take the period we just found (call it (r); in this case, (r = 6)), and use the number we picked to exponentiate (call it (a); in this case, (a = 2)). Calculate the numbers (a^{(r/2)}+1 = 2^{(6/2)}+1=2^3+1 = 9) and (a^{(r/2)}-1 = 2^3-1 = 7).
Finally, take each of those two numbers and our number weโre trying to factor ((N = 21)), and
use Euclidโs algorithm to find the gcd:
gcd(9,21) = 3
gcd(7,21) = 7
and of course (21 = 7 times 3), so we have found the two factors of our number!
้ๅญๅจๆใฎ็บ่ฆ
้ๅญใใผใชใจๅคๆ๏ผQFT๏ผใฎๅใใ็่งฃใใ้ขๆฐใฎๅจๆใ็ฅใฃใใฎใงใQFTใไฝฟ็จใใฆๅจๆๆข็ฅ้ขๆฐใๅฎ่กใใๆนๆณใซใคใใฆ่ฉฑใใพใใ
ใฉใฎใใใซๅจๆ้ขๆฐใๆฉ่ฝใใฆใใใฎใใๆขใซไบๆณใไปใใฆใใใใใใใพใใใ QFTใฎ่ญฐ่ซใฎๆๅพใซใ้ใญๅใใ็ถๆ ใงQFTใๅไฝใใใฎใ่ฆใฆๆฅใพใใใใใๅ ฅๅใใใ้ใญๅใใ็ถๆ ใ (vert0rangle+vert4rangle)ใฎใใใชใใฎใ ใจใใใใคใใฎ้ ใใญใฃใณใปใซใใใฆๅบๅใฏ(vert0rangle+vert2rangle+vert4rangle+vert6rangle)ใซใชใใพใใ
ๅบๅใใใ้ใญๅใใใฎๅคใฏๅ จใฆ2ใฎๅๆฐใงใใใใจใซๆณจๆใใฆใใ ใใใ 2ใคใฏๅ ฅๅใใใ้ใญๅใใใฎ้ ใฎๆฐใซใชใใพใ๏ผ ใใฎไบๅฎใฏ้่ฆใงใใ
ใใใซใใฃใฆๅบๅใใใ้ใญๅใใ็ถๆ ใฎ้ ใฎๆฐใ้ขๆฐใฎๅจๆใซใชใใใใซใขใซใดใชใบใ ใ่จญๅฎใใใใจใใงใใพใใ
ไพใ่ฆใฆใฟใพใใใใ็งใใกใฏใทใงใขใฎใขใซใดใชใบใ ใไฝฟใฃใฆ(N=21)ใๅ ๆฐๅ่งฃใงใใใงใใใใใ2ใฎ(i)ไน ใซๅฏพใใฆๅคงใใๆฐใง่ใใฆใฟใพใใใใ
(2^0 = 1 bmod 21 = 1)
(2^1 = 2 bmod 21 = 2)
(2^2 = 4 bmod 21 = 4)
(2^3 = 8 bmod 21 = 8)
(2^4 = 16 bmod 21 = 16)
(2^5 = 32 bmod 21 = 11)
(2^6 = 64 bmod 21 = 1)
(2^7 = 128 bmod 21 = 2)
(vdots)
ๅ ๆฐๅ่งฃใใๆฐใใๅฐใใ1ใใๅคงใใๆฐๅญใฎใใใใใใ2ใฎไปฃใใใซ้ธใถใใจใใงใใพใใ๏ผใฏๅ็ดใงใใใใใใใฑใผในใงใใ่ชคใฃใฆใใพใใใใชใๆฐใ้ธๆใใใใจใใใใพใใใใใใฏ็จใงใใ)
6ในใใใใใจใซ๏ผใซๆปใใใจใใใใใพใใใใฎใใใใใฎ้ขๆฐใฎๅจๆใฏ๏ผใงใใ้ ็ชใซๆธใใ ใใจ(1, 2, 4, 8, 16, 11, 1, 2, 4, 8, 16, 11, 1, 2, 4, 8, 16, 11, 1, โฆ)ใจใชใใพใใ
ๅๅ ฅๅ็ชๅทใจใใฎๅบๅ็ชๅทใใใขใซใใพใใใ:
input | โ | output | ย | input | โ | output |
---|---|---|---|---|---|---|
0 | โ | 1 | ย | 13 | โ | 2 |
1 | โ | 2 | ย | 14 | โ | 4 |
2 | โ | 4 | ย | 15 | โ | 8 |
3 | โ | 8 | ย | 16 | โ | 16 |
4 | โ | 16 | ย | 17 | โ | 11 |
5 | โ | 11 | ย | 18 | โ | 1 |
6 | โ | 1 | ย | 19 | โ | 2 |
7 | โ | 2 | ย | 20 | โ | 4 |
8 | โ | 4 | ย | 21 | โ | 8 |
9 | โ | 8 | ย | 22 | โ | 16 |
10 | โ | 16 | ย | 23 | โ | 11 |
11 | โ | 11 | ย | 24 | โ | 1 |
12 | โ | 1 | ย | โฆ | ย | ย |
็ถใใฆใใใใใฎ่กใๅบๅ็ชๅทใงใฝใผใใใพใใใ:
input | โ | output | ย | input | โ | output |
---|---|---|---|---|---|---|
0 | โ | 1 | ย | 3 | โ | 8 |
6 | โ | 1 | ย | 9 | โ | 8 |
12 | โ | 1 | ย | 15 | โ | 8 |
18 | โ | 1 | ย | 21 | โ | 8 |
24 | โ | 1 | ย | 4 | โ | 16 |
1 | โ | 2 | ย | 10 | โ | 16 |
7 | โ | 2 | ย | 16 | โ | 16 |
13 | โ | 2 | ย | 22 | โ | 16 |
19 | โ | 2 | ย | 5 | โ | 11 |
2 | โ | 4 | ย | 11 | โ | 11 |
8 | โ | 4 | ย | 17 | โ | 11 |
14 | โ | 4 | ย | 23 | โ | 11 |
20 | โ | 4 | ย | โฆ | ย | ย |
Shorใฎใขใซใดใชใบใ ใงใฏใๅชไนไฝใฎในใใใใงใใใ่กใใพใใๅใๅบๅๅคใๆใคๅ จใฆใฎๅ ฅๅๅคใใฐใซใผใๅใใพใใใคใพใ(2^x bmod 21)ใ็ญใใใในใฆใฎ(x)ใฎๅคใฎใชในใใๆฑใใพใใ
QFTใๅฎ่กใใๅใซใใใใคใใฎ้ๅญใใใ๏ผๅบๅๅคใไฟๆใใ้ๅญใใใ๏ผใๆธฌๅฎใใ้ๅญ็ถๆ ใ้จๅ็ใซๅดฉๅฃใใใพใใ ใใฎๆธฌๅฎใซใใใๅบๅๅคใฎ1ใคใใฉใณใใ ใซ้ธๆใใใพใใ ใใจใใฐใ่ฆใคใใฃใๅบๅๅคใ1ใฎๅ ดๅใๆฌกใฎใใใซ้ใญใฆ่กจ็คบใใใพใใ
[|0rangle+|6rangle+|12rangle+|18rangle+|24rangle โฆ]
ๅบๅๅค11ใ่ฆใคใใฃใๅ ดๅใฏใไปฅไธใฎใชในใใๅพใพใใ
[|5rangle+|11rangle+|17rangle+|23rangle+|29rangle โฆ]
ใใใใซใใใ็ง้ใฏ6ๅจๆใฎ้ใญๅใใใๅพใพใใ
ใใ9้ๅญใใใใใใๅ ดๅใ(2^9 = 512)ใฎ็ถๆ ใใคใพใ0ใใ511ใใใใใใใใฎ้ใซๅนฒๆธใ็ใใฆใใพใใใใใใ6ใคใฎใปใผๆฐใฎ็ญใใใฐใซใผใใซๅใใใใใๅใฐใซใผใใฎไธญใซใฏ(512/6 approx 85)ๅใใใพใใใใฎๆฐใฏใ้ใญๅใใใฎQFTใซ็พใใพใใ
(ๆธฌๅฎใใใๅฏ่ฝๆงใฎ้ซใ็ขบ็ใซๅฏพๅฟใใ)ใใผใฏใฏใ0, 85, 171, 256, 341,427ใซ็พใใพใใ็ปๅใฎใใใซใ6ใคใฎใใผใฏใฏใในใฆๅใใตใคใบใงใฏใใใพใใใใใในใฆ 11๏ผ ใใ17๏ผ ใฎ้ใซใใใฎใงใๅคงใพใใซ่จใฃใฆใ่จ็ฎใฎ้ๅญ้จๅใฎ็ตใใใซใฌใธในใฟใๆธฌๅฎใใใจใใใใใใฎ็ตๆใๅพใ็ขบ็ใฏใใใใๅใใงใใ
็ตๆใๅพใใใใใใใใๅใฃใฆๅจๆใซๅคใใพใใ ใใจใใฐใๅค85ใๆธฌๅฎใใฆ่ฆใคใใใจใ(512 / 85 approx 6)ใฎๅคใๅพใใใพใใ ๅจๆใ่ฆใคใใๆ็ถใใฏๅฎ้ใซใฏใใใใ่ค้ใงใใใใใใงใฏ่งฆใใพใใใ
ใใฎ่ค้ใใฏใ็งใใกใ85ใใใๅคงใใๆฐใๅพใใจใใซๅฟ ่ฆใจใใใพใใใใใฏใปใจใใฉใฎๅ ดๅ่ตทใใใพใใ ๆใซใฏใๆใ ใไฝฟ็จใใใใจใใงใใชใๆธฌๅฎๆใซๆฐๅญ0ใ่ฆใคใใใฎใงใใขใซใดใชใบใ ใฎ้ๅญ้จๅใๅๅฎ่กใใๆฌกๅใซๅฅใฎ็ตๆใๅพใใใใใจใๆๅพ ใใฆใใพใใ
ๆๅพใฎในใใใ๏ผใฆใผใฏใชใใ
ๅ ใปใฉใใฆใผใฏใชใใใฎใขใซใดใชใบใ ใไฝฟใฃใฆใ2ใคใฎๆดๆฐใฎๆๅคงๅ ฌ็ดๆฐ๏ผgcd๏ผใ่ฆใคใใๆนๆณใ่ฆใฆใใพใใใ ไปใใใใใๅฉ็จใใพใใ
่ฆใคใใฃใๅจๆ((r)ใจๅผใถใใใฎๅ ดๅใฏ(r=6))ใใจใใใใใ็ดฏไนใซไฝฟ็จใใพใ๏ผ(ฮฑ)ใจๅผใถใใใฎๅ ดๅใฏ(ฮฑ=2))ใ
(a^{(r/2)}+1 = 2^{(6/2)}+1=2^3+1 = 9) and (a^{(r/2)}-1 = 2^3-1 = 7)
ๆๅพใซใใใใใฎ2ใคใฎๆฐๅญใจๅ ๆฐๅ่งฃใใใใจใใฆใใๆฐๅญ((N=21)) ใซใฆใผใฏใชใใใฎใขใซใดใชใบใ ใไฝฟใใ
gcd(9,21) = 3
gcd(7,21) = 7
(21 = 7 times 3)ใงใ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