From Circuits to Algorithms

I am among those who think that science has great beauty.

Marie Curie

In the last chapter, we became comfortable putting together gates to create circuits for simple algorithms. We’re now ready to look at more advanced quantum algorithms and consider how and when to use them.

Our target in this chapter is Peter Shor’s 1995 algorithm for factoring large integers, which is almost exponentially faster than classical methods. To get there, we need more tools, such as the Quantum Fourier Transform, phase kickback, eigenvalue and phase estimation, and function order and period finding. These are essential techniques in their own right but are necessary in combination for quantum factoring.

We also return to the idea of complexity that we first saw for classical algorithms in section 2.8. This allows us to understand what “almost exponentially faster” means.

This chapter contains more mathematics and equations...