10.3 Oracles

The computational power of quantum interference was discovered by counting how many times certain Boolean functions have to be evaluated in order to find the answer to a given problem. Imagine a “black box” (sometimes also called an oracle) that computes some fixed Boolean function, but whose inner workings are unknown to us. Then imagine that we are in a scenario where we want to learn about some given property of the Boolean function, but we have to “pay” (in energy, time, money, or anything!) for each use (often referred to as a query) of the box. In such a setting, the objective is to minimise number of queries to the oracle while finding out as much information as possible about the function that it computes. For this purpose, we ignore everything that happens inside the black box: in our rules of the game, the Boolean function evaluation counts as just one computational step.