Introduction to Week 3
Now that we have the basic concepts under our belt, we are ready to examine some of the important quantum algorithms in detail.
The two best algorithms for beginners to study are Grover’s algorithm for generalized search, and Shor’s algorithm for factoring large numbers. They serve as good examples for our speedup potential: polynomial for Grover, superpolynomial for Shor. They also illustrate the important techniques for building the entanglement and interference that drive quantum algorithms.
One of a quantum computer’s true strengths is the ability to expose patterns in data, if we build our entanglement. Before we can understand Shor’s algorithm, we first need a little bit of classical background in how certain types of functions exhibit periodic behavior that we can exploit, so we will learn about these topics as a prelude to the quantum parts of the algorithm. Along the way, we will also see one of the oldest known algorithms, Euclid’s (classical) algorithm for finding the greatest common denominator of two large numbers.
We will also take a briefer look at quantum algorithms for machine learning and quantum chemistry, including a second visit with James Whitfield.
Then, in our final week, we will learn more about the machines themselves, how to manage errors, and about the people and companies working to build and deploy quantum computers.
© Keio University