When to use Grover’s algorithm

Before signing a contract to use Grover’s algorithm, you must read the fine print. To run Grover’s algorithm, you need an oracle that marks your search’s target amplitude. Think about the analogy at the start of this chapter. You have 64 boxes, and you wonder which box contains your coffee pot. Along comes an omniscient oracle who knows which box contains the pot. The oracle puts a mark on that box for everyone to see.

The oracle “knows” which item is the target and marks that item. But, in quantum computing, someone or something has to write the oracle’s code. Why can’t we just ask that code-writing agent which item it marked? Why bother doing inversion about the mean? Why trouble yourself by applying the Grover iterate?

For Grover’s algorithm to be useful, a search problem must have certain characteristics. Among them is the requirement that you can code the oracle without knowing...