# Why does solving integer factorization by using Shor’s algorithm surpass the conventional computation

What is the reason that solving integer factorization by using Shor’s algorithm surpass the conventional computation? Can these quantum characteristics be used for different problems? I would like to understand why in this specific case the quantum solution surpasses the conventional computing solution, whereas in many other cases, the quantum has not showed yet a better solutions? What is so unique in Shor’s algorithm that enable the quantum to work better?

## 2 Answers

This question is actually related to the open problem in computer Science about is there any theoretically provable quantum advantage. I don't think people have already solved the problem yet. However, from my perspective, I think there is a simple answer to the question: All quantum algorithms that is believed to be exponentially faster than all classical counterparts are equivalent to "finding a hidden subgroup" in some Abelian group. In other words, the quantum algorithm is finding the non trivial period in some discrete structure, if there is any.

Let's take a look, first, on the Shor's algorithm. The most important observation, for solving the factoring, is that we only need to find the even order $$d=2r$$, by randomly choosing a basis $$a$$, of the modular group of the number $$N$$ that we want to factor (the order $$d$$ is defined to be the minimum integer such that $$a^d \equiv 1 \mod N$$, $$a$$ has to be coprime with $$N$$), which is defined as:

$$a^d=a^{2r} \equiv 1 \mod N$$

After factoring the above equation, we get

$$(a^r-1)(a^r+1) \equiv 0 \mod N \qquad$$

This implies two possibilities, for any prime factor $$p$$ of $$N$$:

1.$$p$$ is a factor of $$(a^r+1)$$

2.$$p$$ is a factor of $$(a^r-1)$$.

We are happy now because now we can use the famous Euclid's algorithm (GCD) for both $$gcd(N,a^r+1)$$ and $$gcd(N,a^r-1)$$ to get $$p$$. (There are bad cases, however, when $$N$$ is a factor of $$(a^r+1)$$. But the possibility of such case is bounded.)

Now we can come back to the most important conclusion:

The quantum computer, in its nature, is pretty good at finding such $$r$$. Because $$r$$ is the period of the subgroup generated by $$a$$ in the Abelian multiplication group of modular $$N$$.

The "trick" used by quantum computer, is called Quantum Fourier Transform (QFT). First, we create a quantum circuit which do the modular exponentiation with respect to $$a$$ modular $$N$$. Then we prepare a uniform superposition off all $$n$$ qubits state. We can prove that, after using inverse QFT, we will finally measure a good approximation of $$1/r$$, with high probability.

Take a look at the example of $$N=15$$ and $$a=7$$. The right answer for the even order, should be $$7^4 \equiv 1 \mod 15$$. And we can take $$gcd(7^2-1,15)=3$$ as the answer of our factoring.

The hidden subgroup here, is $$\{1,7, 7^2 \mod 15 =4, 7^3 \mod 15 = 13\}=\{1,7,4,13\}$$. We can check that this is a subgroup of modular $$15$$ group because every element has an inverse. The goal of shor's algorithm, is exactly finding the period of this hidden subgroup! $$(1 \rightarrow 7 \rightarrow 4 \rightarrow 13 \rightarrow 1 \rightarrow 7 \cdots)$$.

We can even take a look at the quantum circuit for solving the problem:

$N=15$ when $$a=7$$" />

The measuring result of 20000 shot, of the above circuit is :

Now we can see that with high probability, we will measure $$010$$, which means $$1/r \approx 0.010= 1/4$$. So shor's circuit, in this case, indeed help us find the non trivial even order $$4$$!

The magic of the whole thing behind the period finding, is that there is a period in the quantum phase of a qubit. We can carefully match the period of our problem to the period of "phase" of a quantum state that we can construct.

The trick of phase manipulation, is also used in all other quantum algorithms, such as Grover algorithm. But the idea behind the Grover algorithm is rotation the solution vector in the phase space, so it has no exponential speedup.

community wiki

It is a long-open program to iron out the precise requirements needed to achieve tremendous speedups (e.g., exponential speedups) with quantum algorithms.

If we limit ourselves to decision problems or problems that can be recast as such (like, the factoring problem), a rough and ready answer is that quantum algorithms might afford an exponential speedup when the problems have a certain global structure that interference can exploit. I'd refer you to Aaronson's summary here.

Recently the same program has moved over to non-decision based problems, such as search or sampling problems, that still achieve exponential speedups with quantum computers. This is manifest in the results of Yamakawa and Zhandry (for search problems) and the other results on random circuits (for sampling problems).

For Yamakawa-Zhandry, it's not quite clear to me why there should be a speedup apart from some handwaving about multiplication in the primal domain being equivalent to convolution in the Fourier domain. For sampling problems, the advantage likely has to do with summing a bunch of positive and negative amplitudes together.