Quantum Algorithms

This chapter traces the history of quantum algorithms with a focus on the milestones, Peter Shor's algorithm and Grover's algorithm for unstructured search. The first quantum algorithm is Deutsch's algorithm. The interesting fact about this algorithm is that not only it is the smallest algorithm, involving only two quantum bits (qubits) but also carries the main ingredients of later quantum algorithms, and is a nice toy model for understanding why and how quantum algorithms work. To understand this algorithm, the chapter clarifies the notion of a quantum black-box function. Developments in quantum algorithm design after Shor's and Grover's algorithms can be loosely grouped into three categories: algorithms that generalize Shor's algorithm, algorithms that perform some version of unstructured search and a few algorithms that do not fit into either of these categories. The chapter concludes with the recent developments of quantum algorithms.