Shor's algorithm

At the moment we can theoretically build a circuit composed of basic small gates (single cubic and CNOT) for any matrix. (Except for the as yet unproven theorem ABC necessary for the construction of a single-cubic controlled operator.) We can therefore return to the question of for which matrices there is a "small" circuit.

To obtain sufficient motivation for some of the following theoretical passages (especially for the quantum Fourier transform), we will now look at the most important algorithm: Shor's algorithm for factorization.

A note on Fermat's factorization

• Try to decompose some composite number by Fermat's test. E.g. 21. We look for two squares equivalent modulo 21. We can succesively add squares to 21 and see when we get another square. We have 21 + 2² = 5². Hence 21 = (5 + 2) (5-2).
• Order of 2 mod 21 is 6. Thus (2³ + 1) (2³-1) = 9x7 = 63 = 0 mod 21. Nine is not a divisor, but it is a factor of the factorized number. The divisor 3 is thus found by Euclid's algorithm.

Think carefully about what the operator W looks like and how its construction is related to the reversible implementation of a classical algorithm.

• Is it really a permutation of basis elements?
• How big is the circuit for W (what number of elementary gates do we need)? Is it (measured as a function of m and n) polynomial? Quadratic? Or even linear?

You can skip success estimates when reading the lecture notes. Try to imagine an algorithm for factorization of 15. The group of invertible elements modulo 15 has order 8, so all elements have the order of the power of two. For M = 16, therefore, there is an equality in the approximation (*) in this case.