Principles of Superconducting Quantum Computers

12 Some Quantum Algorithms

In this final chapter, we present a few selected quantum algorithms that illustrate the promise of quantum computers to provide a computational advantage over classical computers. We use the word “advantage” informally here, simply meaning that there is some problem size at which the quantum computer can give a solution faster than any feasible classical computer.

What do we mean by “faster”? In the next section, we briefly discuss computational complexity and how it applies to quantum computing. Then we present the two most famous quantum algorithms which promise quantum advantage: Grover’s search algorithm (12.2) and Shor’s algorithm for factoring (12.5). In the process, we will introduce several fundamental building blocks, including amplitude amplification (12.2), the Quantum Fourier Transform (12.3), and quantum phase estimation (12.4). Finally, we will discuss a class of hybrid classical-quantum algorithms, known as variational algorithms, that are designed to operate within the realm of noisy, intermediate-scale quantum (NISQ) systems that are likely to be prevalent in the early years of quantum applications.

12.1 Computational Complexity

In classical computing, we analyze algorithms to determine the resources needed to solve a computational problem. A resource typically means time or space, but could be energy, circuit gates, or some other measurable quantity. We are especially interested in the algorithm’s behavior as the problem size increases. ...