TopicIntermediateEstablished concept

Quantum Oracle

Quantum Oracle

An oracle is a unitary operator that computes a function $f$ reversibly, either in bit form $|x\rangle|y\rangle\mapsto|x\rangle|y\oplus f(x)\rangle$ or in phase form $|x\rangle\mapsto(-1)^{f(x)}|x\rangle$; algorithm complexity is measured by the number of calls to it.

In the query model, the function $f$ is given as a black box, and the complexity of an algorithm is measured by the number of times it is called, regardless of the cost of building it internally. The quantum oracleQuantum Oracle: An oracle is a unitary operator that computes a function f reversibly, either in bit form x⟩y⟩⟩y⊕ f(x)⟩ or in phase form x⟩(-1)^f(x)x⟩; algorithm complexity is measured… is the unitary version of this box. The bit form: $O_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle$, which is reversible because applying it twice gives the identity. The phase form: $O_f^{\pm}|x\rangle=(-1)^{f(x)}|x\rangle$, obtained from the bit form by putting the ancilla qubitQubit: The qubit is the unit of quantum information: a two-level system whose state is a unit vector α0⟩+β1⟩ in ℂ^2. in $|-\rangle$ via phase kickbackPhase Kickback: Phase kickback is a phenomenon in which an eigenvalue phase moves from the target qubit to the control qubit of a controlled gate; it is a key mechanism in Deutsch–Jozsa….

In this model strict separations between quantum and classical can be proved: Deutsch–Jozsa solves its problem with one call against $2^{n-1}+1$ calls for a deterministic classical algorithm in the worst case; Simon gives an exponential separation even against randomised algorithms; and Grover needs $O(\sqrt N)$ against $\Theta(N)$. But these separations are specific to the query model and do not automatically translate into a speed-up in actual time, because building the oracle for a real function can be costly, and because the oracle in teaching circuits is often built with prior knowledge of the answer.

In circuits, the oracle is built from reversible classical gates (X, CNOT and Toffoli), and complex functions may need ancilla qubits that must be "uncomputed" at the end so that they do not stay entangled with the register.

q0q1q2HHHHXHUf
Deutsch–Jozsa circuit: Hadamard, oracle Uf, Hadamard, measurement

Mathematical formulation

$$O_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle,\qquad O_f^{\pm}|x\rangle=(-1)^{f(x)}|x\rangle$$

Worked example

The Bernstein–Vazirani oracle for $f(x)=s\cdot x \bmod 2$ with $s=101$: it is enough to place a CNOT from each qubit $i$ with $s_i=1$ to the ancilla qubit, i.e. from $q_0$ and $q_2$. For the input $x=111$: $f=1\cdot1+0\cdot1+1\cdot1=2\equiv0$, so the ancilla does not change. Note that building the oracle used $s$ itself; this is common in teaching demonstrations.

Try it yourself: Deutsch–Jozsa Algorithm

Loading the simulator…

The full experiment page

Test your understanding

The quiz needs JavaScript.

Related topics

References

  1. Michael A. Nielsen; Isaac L. Chuang (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press doi:10.1017/CBO9780511976667The standard reference for quantum computing; the Crossref record gives 2012 for the Cambridge Core online edition.
  2. John Watrous / IBM Quantum (2025). Fundamentals of Quantum Algorithms (course). IBM Quantum Learning quantum.cloud.ibm.com