QC — Period finding in Shor’s Algorithm
Finally, it is time to put everything together to solve the prime factorization — the key component in hacking the RSA algorithm that guards the security of the Internet. In the previous article, we discuss the phase estimation. It is a very abstract concept. But yet, it is an important tool in quantum computing. Now we are going to put it into practical use to find the period of a modulo function.
The phase estimation algorithm can be summarised in the following quantum circuit with a chain of unitary operator U.
To crack RSA, we need to find the period of the modulo function below,
- We will “magically” define an operator U with its eigenvalue containing the period of the f.
- Phase estimation is about finding the eigenvalue of a unitary operator. Therefore, we can use it to compute the period above.
- Finally, we find ways to implement the chain of unitary operators U effectively.
Unitary operator
U will be defined as:
Its eigenvalue and the eigenvector of U are (with proof here):
In the proof, we introduce the period r to simplify the expression. That establishes a relationship between the eigenvalue and the period of f. i.e.
Period finding
This is very important. We reformulate our period finding problem into a phase estimation problem. To find the period of
We find the eigenvalue of U.
Since U have r eigenvectors, the phase ϕ in the phase estimation equals s/r where s is an integer in the range of 0 to (r-1). And each eigenvector corresponds to a different value of s.
But there is one big catch here. To solve the eigenvalue, we need to know the eigenvector. But we don’t know the period r and therefore we don’t know the eigenvectors. Fortunately, we don’t need to. We know the superposition of all eigenvectors. Let’s create a superposition with all the eigenvectors.
It equals |1⟩. The concept of quantum parallelism allows us to compute the outputs of a function in parallel.
We just compute the superposition of all the inputs. If we pass it to the phase estimation, we will compute the phases of all eigenvectors in parallel. i.e. when we make measurements, each peak below represents the phase value of one of the eigenvector.
Next, we will find the value of r from these measurements.
Continued fraction algorithm
A number can be expressed with a continued fraction representation by expanding the reciprocal iteratively. For example, 415/93 can be exactly defined as [4, 2, 6, 7].
The last step in the period finding converts the measurements into the period r. The measurements approximate s/r (with s and r as an integer). So let’s use one of the peak measurements above (say, 427) to compute r.
This first register used to estimate the phase has a range from 0 to 511 (this subjects to the number of qubits we use to estimate the phase). So our measurement is 427/512 (0.83398). We want to approximate it so it will fit some value of s/r. We apply the continued fraction and check whether the corresponding answer makes sense. If not, we expand the reciprocal further until we find the answer we want. Without detailing it, the continued fraction can be calculated with the following equations.
The first expansion result (d0, r0) is d=0 (d is the same as s — we just have the example above coming from a different source) and r=1. This is not the answer we want. “Period equals 1” is obviously not the non-trivial answer we want. So we will reject it. The next approximation (r1) is 1 again and we will reject it. For the third iteration, d=5 and r=6. i.e. s/r = 5/6 (0.83333). s=5 with a period of 6 makes a lot of sense to us. Let’s verify a few more things before we proceed further:
- 5 and 6 are coprime (no common factors),
- r = 6 is even and
After this is verified, we can proceed to the classical post-processing part of the Shor’s Algorithm to compute the prime factors.
Put it together
So let’s put everything together. We want to find the period of f below.
We have two registers, the second register should have enough bits to hold N. (For N = 15, that will be 4.) The first register has t qubits (say) which have enough precision to estimate the phase. We can pick t as:
We use t Hadamard gates to prepare the first register into a uniform superposition. And prepare the second register to be |1⟩.
Then we apply a series of Controlled-U gates.
This will bring the system to
The circuit above can be viewed as a nice approximation to:
We apply the inverse Quantum Fourier transform to the first register, the superposition becomes
We run the programs many times and the corresponding measurements are:
Then we use the continued fraction and finally compute the period to be 6.
Here is the summary of the whole flow:
Congratulations! We have a complete period-finding algorithm for Shor’s algorithm. The remaining sections will just close up some details that we have not covered.
Modular Exponentiation
The last piece of the puzzle is the implementation of the chain of U gates below. We will go through the explanation relatively fast with the intention of demonstrating the major steps only.
Let’s make some definitions.
U operator
Modular multiplication
Modular squaring
Now, we can use the modular multiplication and the modular squaring above to build the modular exponentiation below.
We start with some ancilla bits |1⟩ and the eigenvector |u⟩.
We apply the U operator:
Then we apply the modular squaring repetitively.
Finally, we apply the modular multiplication. The output is what we want.
Here is the final circuit using those modules in producing the modular multiplication. The second half of the circuit simply reverse the operation to recover the ancilla qubits.
Just for the demonstration on the complexity (without explaining them), here are the circuit for some of the module implementations.
This is the circuit for factorizing 15 with x=11. The circuit described required needs 12 qubits. To fit into a 5-qubit machine, it is further optimized as:
Here are the measurements. The left one is from the quantum simulation and the right one is from the IBM Q quantum machine.
Thoughts
This is a pretty long journey to discover how to factorize 15 (3 × 5). To beat the 2014 key strength in SSL, it is estimated that we need 100 million qubits. So there are still a lot of works to do. But, we are done! :-) Hope you enjoy the journey. For those interested in the whole series, here is the link:
