In this problem, we will carry out some steps of the quantum factoring algorithm for N=21.
(a) What is the period k of the periodic superposition set up by the quantum factoring algorithm if it chooses x=2? In other words, what is the period of f(j)=2^j (mod 21).
(b) Assume that we found this k using period finding algorithm. Use k to find a non-trivial square root of 1(mod 21). Write your answer as an integer between 0 and 21.
(c) Then, the algorithm proceeds by computing gcd(x,y) for some integers x and y. List these two numbers separated by a comma.
If there are more than one correct solution, provide any one of them.
To find the period k of the function f(j) = 2^j (mod 21), we can calculate the values of f(j) for increasing values of j until we find a repeated value.
(a) Let's start by calculating f(j) for j = 0, 1, 2, 3, ...
For j = 0: f(0) = 2^0 mod 21 = 1 mod 21 = 1
For j = 1: f(1) = 2^1 mod 21 = 2 mod 21 = 2
For j = 2: f(2) = 2^2 mod 21 = 4 mod 21 = 4
For j = 3: f(3) = 2^3 mod 21 = 8 mod 21 = 8
For j = 4: f(4) = 2^4 mod 21 = 16 mod 21 = 16
For j = 5: f(5) = 2^5 mod 21 = 32 mod 21 = 11
For j = 6: f(6) = 2^6 mod 21 = 64 mod 21 = 1 (repeated value)
Therefore, the period k of f(j) = 2^j (mod 21) when x=2 is 6.
(b) To find a non-trivial square root of 1 (mod 21) using k, we need to find an integer y that satisfies y^2 = 1 (mod 21) but y is not congruent to 1 or -1 modulo 21.
Using the period k = 6, we can calculate 2^(k/2) = 2^(6/2) = 2^3 = 8 (mod 21).
Now, let's find a non-trivial square root of 1 (mod 21) by calculating gcd(8 + 1, 21) and gcd(8 - 1, 21).
gcd(8 + 1, 21) = gcd(9, 21) = 3
gcd(8 - 1, 21) = gcd(7, 21) = 1
So, the non-trivial square root of 1 (mod 21) is 9.
(c) Finally, the algorithm proceeds by computing gcd(x,y) for some integers x and y.
Let's take x = 2 and y = 9, and calculate gcd(2, 9).
gcd(2, 9) = 1
Therefore, the two numbers separated by a comma are x = 2 and y = 9.
(a) To find the period k of the function f(j) = 2^j mod 21, we can calculate the values of f(j) for increasing values of j until we find the first repeated value. The period k is the smallest value of j for which f(j) repeats.
Starting with j = 0:
f(0) = 2^0 mod 21 = 1
Moving to the next values of j:
f(1) = 2^1 mod 21 = 2
f(2) = 2^2 mod 21 = 4
f(3) = 2^3 mod 21 = 8
f(4) = 2^4 mod 21 = 16
f(5) = 2^5 mod 21 = 11
f(6) = 2^6 mod 21 = 1 <-- repeated value
Therefore, the period k of f(j) = 2^j mod 21 when x = 2 is 6.
(b) To find a non-trivial square root of 1 (mod 21) using the period k, we can use the property that for any positive integer n, if a^n = b^n (mod n), then a = b (mod n) or a = -b (mod n).
In this case, we look for j such that 2^j = 1 (mod 21). Since 2^k = 1 (mod 21) by definition of the period, we have k = 6.
Let's find a non-trivial square root of 1:
2^(k/2) = 2^(6/2) = 2^3 = 8 (mod 21)
Therefore, a non-trivial square root of 1 (mod 21) is 8.
(c) The next step of the quantum factoring algorithm involves computing the greatest common divisor (gcd) of x and y, where x is the base number used in the period finding algorithm (in this case, x = 2) and y is given by y = 2^(k/2) mod 21. Using the value we found for y in (b), we can calculate the gcd:
gcd(2, 8) = 2
Therefore, two numbers that can be used for the gcd computation are 2 and 8, separated by a comma.