n this problem, we will carry out some steps of the quantum factoring algorithm for N=15.
(a) What is the period k of the periodic superposition set up by the quantum factoring algorithm if it chooses x=2?
(b) Assume that we found this k using period finding algorithm. Use k to find a non-trivial square root of 1(mod15). Write your answer as an integer between 0 and 15.
(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.
(a) To find the period k of the periodic superposition set up by the quantum factoring algorithm, we need to use the formula:
k = 2^r
where r is the number of qubits used to represent N. In this case, N = 15, so we can represent it using 4 qubits.
Therefore, k = 2^4 = 16.
(b) To find a non-trivial square root of 1 (mod15) using the period k = 16, we can use the formula:
x = (a^(k/2)) mod N
where a is any non-trivial factor of N. Since we know that 15 = 3 * 5, we can choose a = 3.
Calculating:
x = (3^(16/2)) mod 15
x = 3^8 mod 15
Using modular exponentiation, we can calculate x as follows:
3^2 mod 15 = 9
(3^2)^2 mod 15 = 6
(3^4)^2 mod 15 = 6
(3^8)^2 mod 15 = 1
Therefore, a non-trivial square root of 1 (mod15) is x = 1.
(c) The next step in the algorithm is to compute gcd(x, N), where x is the non-trivial square root of 1 (mod15) that we found in the previous step.
Computing gcd(1, 15):
We can use the Euclidean algorithm to find the greatest common divisor (gcd):
gcd(1, 15) = gcd(15, 1)
= 15 mod 1
= 0 (remainder)
Therefore, the two numbers x and y are 1 and 15, respectively, separated by a comma: 1, 15.
To solve this problem, let's go step by step:
(a) To find the period k of the periodic superposition set up by the quantum factoring algorithm if it chooses x=2, we need to use the period finding algorithm. The period finding algorithm is a key step in Shor's algorithm for factorization.
The period finding algorithm:
1. Initialize two quantum registers, one for input values (x) and one for output values (y).
2. Apply Hadamard gates to the input register, creating a superposition of all possible input values.
3. Apply a quantum function f(x) that computes the modular exponentiation of x^a mod N, where a is an integer chosen as a power of 2 that is larger than the maximum period expected.
4. Apply a quantum Fourier transform to the input register.
5. Measure the input register and obtain a set of output values (y). The period k can be derived from these output values.
For our problem, the input value x=2. So, we need to apply step 2, 3, and 4 to find the period k.
(b) Assuming we found the period k using the period finding algorithm, we can use k to find a non-trivial square root of 1 (mod 15). To do this, we need to find an integer x such that x^2 ≡ 1 (mod 15) and x is not equal to 1 or -1 (mod 15).
One approach to find the non-trivial square root of 1 (mod 15) is to find the smallest positive integer r such that x^r ≡ 1 (mod 15) but x^(r/2) is not equivalent to 1 (mod 15).
(c) Finally, the algorithm proceeds by computing gcd(x, y) for some integers x and y. The greatest common divisor (gcd) of x and y is a step in the factorization process.
To find the gcd:
1. Choose values for x and y, which can be any integer values.
2. Compute the gcd(x, y) using an algorithm like Euclid's algorithm or the extended Euclidean algorithm.
If there are multiple correct solutions, any one of them can be provided.