Quantum Factorization

Shor’s algorithm

Published in

Towards Data Science

11 min readSep 11, 2020

The factorization problem is one of those problems that everyone can understand and most of us feel that it is their opportunity: the divine breach to mathematics hole of fame:

Let N, an odd integer with a relatively big binary representation ( e.g. hundreds of bits) and p,q prime numbers such that:

1. p and q are about the same size (it is not essential but clearly you don’t construct N from an easy to achieve prime number)

2. N is known

3 N =pq

Find p & q in a polynomial time of log(n).

Indeed, extremely easy to understand. However, less easy to implement. It is so “less easy” that the massive amount of the encryption industry relies on a legendary algorithm RSA that exploits this particular manner.

The leading algorithms that handle the factorization problem are:

GNFS (General number field sieve) with the complexity of:

2. QS (Quadratic Sieve) with complexity of

The question whether this algorithm may have a polynomial solution is still open.

However, as numbers theory have been developed it appears that one can find to factorization equivalent question. Such question is the “Period Finding”

Period Finding

As we described in the section beyond Period finding is an equivalent problem for factorization.

Let N as in the section beyond (i.e. an odd composite number that can be written as a product of two primes p & q ).

Definition: Let a, an integer s.t. 0< a < N. a is invertible modulo N (i.e. there exists 0<b< N and K integer s.t a *b=K N +1

Claim: a is invertible mod N <> GCD(a, N) =1

Notation: We denote b modulo N by b(N)

Fermat’s little theorem implies that

This hints us that such exponents may have periods.

Definition: a function f has a period r if:

r is an integer

For all x f (x+ r) = f(x)

There is no integer m<r s.t f(x+ m) = f(x)

Let a an invertible number mod N

We define a function F

Assume that F has a period r, one can easily see that F (r) =1 ,then

The second factor is a multiplication of N, namely we have a trivial factorization.

Example

Let N=65, a =47. The period of 47 in this ring is 4. We observe the equation that we got:

One can see that the second term is a multiplication of 65. Hence factorization has not been achieved

Let’s re- observe the formula beyond. We can see that:

1 None of the terms is a multiplication of N

2 Every prime factor of N exists in the left hand side.

We can conclude that both :

We can therefore factorize N when we have a period such that

Example

Let N =15 ,a =7 . The period of 7 (15) is 4.

We have thus

GCD(49–1,15) = 3 GCD(49+1,15) = 5

3,5 are the prime factors of 15 so we obtained the required

We can summarize the process as follow:

Cool! We can factorize… one tiny thing:

How can we find the period!!?!

Quantum Part

For the readers that are not familiar with quantum computing I added tutorials below. I will briefly describe basic objects such as qubit and quantum gate but I suggest you to learn them in a wider frame work. Basically quantum computer appeared in the early 80’s when the legendary physicist Richard Feynman “challenged”computer scientist to develop a computer that is based on quantum physics. The main motivation was the understanding that simulation quantum systems is impossible :process are always exponential in the number of particles. Feynman was also concern whether quantum computing is at least as universal as classical computing. An additional motivation appeared as engineers learned that chips miniaturization begins to suffer quantum effects. In the last decades quantum computing is often associated with NP problems and whether quantum computing makes them tractable.

Basic Quantum Entities

Qubit- The basic unit of quantum computing. In contrast to classical bits, the general structure of a qubit has the form

q= a|0> +b|1>

The qubit is considered in a superposition. a and b are complex numbers which the sum of their magnitudes is 1.

|0>, |1> are vectors in the basis which upon we measure

Tensor Product

A vector space that consist of two smaller vector spaces X,Y is denoted as

The operators over this space are bilinear operators over each of the sub spaces. In terms of matrices tensor product has the following form:

Quantum Gate

A logic gate that operates over a qubit or a set of qubits. In the world of quantum computing these gates are implemented using unitary matrices

Common Gates

QUANTUM Fourier Transform

Quantum Fourier transform is the quantum analogue to the commonly known FFT. Over a quantum state x, QFT It is defined as follow:

Where N is a power of 2 (log(N)=n) n is therefore the number of qubits. It is easy to see that QFT is a unitary operator:

|QFT|x>| =|x|

<x,y> =0 => <QFT|x>,QFT|y> = 0

We can observe QFT as a matrix of dimension N x N (a giant one ) that its (x,y) entry is the coefficient beyond . When Shor published his algorithm one of his achievements focused on improving QFT for bits string input.

QFT for Binary Strings

“Traditionally” FFT converts complex numbers to complex numbers but here we consider an input x s.t. x is an integer and x<N . It has therefore a unique binary representation using n bits In a paper from 1994 Coppersimth has shown that we can decompose QFT to a tensor product on n qubits [CopperSmith] . If we define the giant matrix by D, we can rewrite the transform:

Where b’s are the qubit and

Clearly I had to present here the entire rigorous development but I’d like the readers to stay around. The main benefit of this representation is that we can write QFT using n(n-1)/2 Hadamard and phase shift operations, namely in a polynomial number of operations:

In Shor’s terminology he used the following notations:

and for

The algorithm becomes:

So we got the motivation to develop an algorithm for period finding and the benefit of using QFT for this algorithm (naturally every engineer knows that FFT is used for finding frequencies, so it is a natural step) . Now let’s combine the packet.

Shor’s Algorithm

You may guess that Shor’s algorithm aims to find the period r which we discussed in the first sections. It can be observed as :

Where Hn is n order Hadamard matrix. Let N the number which we wish to factorize . We choose q such that:

Namely q is a power of 2, which is the order of QFT matrix and l is the amount of qubits

We will also define a function f as follow:

Recall that N is the number to factorize and x is the number which we search for its period. We need two registers the first one contains l qubits, the second needs enough place to get the entire plausible results mod N (i.e. more than log(N)) we denote it by w. The register has therefore the form

In some places the notion for the right register is “output register”

In order to make the qubits in superposition we perform the l order Hadamard matrix

The next step is simply calculating the function f to the second register

Note that now the registers are entangled (clearly each a is mapped to its own function value)

In the original paper of Shor performed QFT at this stage. However in later versions the common approach is to perform a measurement over the second register. The right (output) register is then collapsed to a single value and leaves in the first registers only with states that f maps them to this value we denote the amount of these states by A. We denote this values by m where m is integer and m<N . The system has now the form:

Assume that x0 is the a state such f(x0)=m and r is the period of x0 We can write our quantum state as follow:

where

Clearly x0<r (otherwise r is not the period)

We now perform QFT of order q over the first register.

The next step will be to measure a state in this quantum state. We wish to verify that we have high probability to get an outcome that will lead to a correct period.We need therefore to show the probability analysis.

As a first step we can see that we can rewrite the current quantum state as

We wish to estimate probability for a certain state |y>

We have :

That leaves us with

We are interested in y’s that satisfy

(In some books they are called “good y’s”) We can see that the the prob term is actually a geometric sequence. Hence we can do the following:

The summation of this sequence is give by :

Law of cosines implies that

For the nominator we have :

Thus the probability we estimate is

Since we have about r y’s (|ry(q)|<0.5r), the probability is

which is about 0.4.

Why do we care about such y’s ?

Claims?! now? Let’s do some algebra

We have

Since y and q are known, we can conclude from the claim beyond that around the y/q there is only a single fraction with such a small denominator (smaller than N in a distance lower 1/(2q)) .

We have now to provide an efficient method to find such a denominator (namely r)

Continued Fraction Expansion

Continued fraction expansion is a method for representing a number using a series of integers through a fraction calculation. If x is the number to approximate, the general form will be :

Where the a’s are integers. Note that the process always terminates when the last fraction has a nominator 1

A nice result shows that rational numbers has a finite expansion where as irrational result has an infinite one.

Example

We wish to approximate the fraction 867/42

The results are of this form

The fraction 79/14 has the expansion

Sometimes we are interested in the nth convergent of a fraction namely taking only the first j steps. For instance in our example we will take j=4 hence we will take the vector [5,1,1,1] and reconstruct a rational number that is close to the original fraction.

How can we exploit it ?

So we have the fraction y/q and we wish to find a fraction that both:

Approximate y/q (has distance smaller than 1/(2q) )

Has a denominator which is smaller than N. We will therefore develop a continue fraction expansion in various orders as long as the denominator is smaller than N