October 2022
Intermediate to advanced
442 pages
9h 37m
English
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 [117] 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 ...