QC — Period finding in Shor’s Algorithm

Image for post
Image for post
Photo by Vincent Botta

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.

Image for post
Image for post

To crack RSA, we need to find the period of the modulo function below,

Image for post
Image for post
Image for post
Image for post

Unitary operator

U will be defined as:

Image for post
Image for post

Its eigenvalue and the eigenvector of U are (with proof here):

Image for post
Image for post

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.

Image for post
Image for post

Period finding

This is very important. We reformulate our period finding problem into a phase estimation problem. To find the period of

Image for post
Image for post

We find the eigenvalue of U.

Image for post
Image for post

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.

Image for post
Image for post

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.

Image for post
Image for post

It equals |1⟩. The concept of quantum parallelism allows us to compute the outputs of a function in parallel.

Image for post
Image for post

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.

Image for post
Image for post
Measurement in factorizing 21 Source

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].

Image for post
Image for post

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.

Image for post
Image for post
Source (d is the same as s in our context)

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:

Image for post
Image for post

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.

Image for post
Image for post

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:

Image for post
Image for post

We use t Hadamard gates to prepare the first register into a uniform superposition. And prepare the second register to be |1⟩.

Image for post
Image for post

Then we apply a series of Controlled-U gates.

Image for post
Image for post
Modified from source

This will bring the system to

Image for post
Image for post

The circuit above can be viewed as a nice approximation to:

Image for post
Image for post
Image for post
Image for post

We apply the inverse Quantum Fourier transform to the first register, the superposition becomes

Image for post
Image for post

We run the programs many times and the corresponding measurements are:

Image for post
Image for post
Measurement in factorizing 21 Source

Then we use the continued fraction and finally compute the period to be 6.

Image for post
Image for post

Here is the summary of the whole flow:

Image for post
Image for post
Source

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.

Image for post
Image for post

Let’s make some definitions.

U operator

Image for post
Image for post

Modular multiplication

Image for post
Image for post

Modular squaring

Image for post
Image for post

Now, we can use the modular multiplication and the modular squaring above to build the modular exponentiation below.

Image for post
Image for post

We start with some ancilla bits |1⟩ and the eigenvector |u⟩.

Image for post
Image for post

We apply the U operator:

Image for post
Image for post
Image for post
Image for post

Then we apply the modular squaring repetitively.

Image for post
Image for post

Finally, we apply the modular multiplication. The output is what we want.

Image for post
Image for post

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.

Image for post
Image for post
Modified from source

Just for the demonstration on the complexity (without explaining them), here are the circuit for some of the module implementations.

Image for post
Image for post

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:

Image for post
Image for post
Factorize 15 with x=11 source

Here are the measurements. The left one is from the quantum simulation and the right one is from the IBM Q quantum machine.

Image for post
Image for post

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:

Written by

Deep Learning

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store