Introduction
In this lesson, we'll discuss the phase estimation problem and how to solve it with a quantum computer. We'll then use this solution to obtain In addition to his integer factorization algorithm, Peter Shor also discovered an efficient quantum algorithm for the different but related problem of computing discrete logarithms. The two algorithms appeared in the same paper, first published as a conference paper in 1994 and then as a journal paper in 1997. — an efficient quantum algorithm for the integer factorization problem. Along the way, we'll encounter the quantum Fourier transform, and we'll see how it can be implemented efficiently by a quantum circuit.
Lesson video
In the following video, John Watrous steps you through the content in this lesson on quantum phase estimation. Alternatively, you can open the YouTube video for this lesson in a separate window.