Ominous Oracles

Classical oracle

The Oracle is simply a black-box function used to abstract some parts of an algorithm. Computer scientists use oracles to abstract some complex logic and implementation details and to focus on the computability or time/space complexities of the algorithm being analyzed. Formally we can represent an Oracle as a function. The function would take an $n-$ dimensional input $x$ and produce an $m-$ dimensional output $y$.

$$f(x) = y$$

An example of this could be a function that takes as input five numbers and returns their sum. Consequently, our input $x$ becomes 5-D, whereas output $y$ is just 1-D.

Quantum oracle

The first thing you might notice from the classical oracle example is that the operation is irreversible. The input and output dimensions do not match. We can’t pinpoint the input only by looking at the output. We’ve discussed earlier that we need unitary operations to maintain reversibility. Essentially, a quantum oracle is a reversible black-box function that we can use for the same uses as classical oracles are used to study classical algorithms. The same input and output dimensions allow us to use quantum oracles in the context of quantum computing and qubits. We can define a quantum oracle as a unitary operator $O$ applying the required black-box function on a system of qubits.

$$O|x\rangle = |f(x)\rangle$$ ...