9.5 Welcome to Delphi
In ancient Greece, the Oracle at Delphi was a high priestess at the Temple of Apollo who, under the right conditions and during warm weather, issued prophecies. Less elaborate functions were served by other priestesses who would sometimes issue ‘‘yes’’ or ‘‘no’’ answers to questions put to them.
It’s in this second sense that we introduce the notion of oracle for quantum computing. An oracle is a function which we supply with data and it responds with a 1 for yes and a 0 for no. The oracles we use cannot answer arbitrary questions but are instead built to respond to a specific query. For the algorithms that use them, two things are significant:
- The implementation of the oracle must be as fast and efficient as possible.
- We want to call the oracle the fewest number of times as possible to minimize the complexity of the algorithm.
An oracle is often called a black...
