Chapter 2
Adiabatic Quantum Computing
Search algorithms are among the most important and fundamental algorithms in computer science, the most basic example being that of finding one special item among a list of N items. Classical algorithms are known to solve this problem in time proportional to the problem size, N, which becomes highly untractable when the latter grows large. In 1996, Grover [124] devised a quantum algorithm to solve such search problems with a quadratic speedup, with the obvious caveat that quantum computers did not exist at the time. Soon after, Farhi, Goldstone, Gutmann, and Sipser [98] recast the Grover problem as a satisfiability problem in the context of quantum computation by adiabatic evolution.
Another class of problems that are hard to solve classically is that of combinatorial optimisation problems. The truck dispatching problem, originally proposed by Dantzig and Ramser [78], searches the optimal routing of delivery trucks, and is...
