Quantum queries and oracles

What is one query?

A query is one invocation of a specified input-access operation. For a Boolean function, a standard choice is

$$U_f\lvert x,y\rangle=\lvert x,y\oplus f(x)\rangle.$$

Quantum algorithms may apply this operation coherently to a superposition. The oracle contract specifies its behaviour on every basis input, which fixes its action on superpositions by linearity.

Promises change the problem

Deutsch–Jozsa assumes f is either constant or balanced. Without that promise, observing a nonzero output does not classify all possible functions into those two categories.

Grover’s search instead uses a predicate marking acceptable candidates. The cost of evaluating that predicate and the number of marked items affect the useful algorithm and its iteration schedule.

A worked marking example

With two bits and marked item 11, the phase oracle is

$$O_f=\operatorname{diag}(1,1,1,-1).$$

It changes a sign, not a probability, when applied to a uniform state. The later diffusion step makes that phase distinction measurable. The Grover lab performs these steps exactly for small registers.

The practical question

If checking a candidate requires a large reversible computation, one query can represent many gates and ancillas. If accessing data assumes a special memory model, building and operating that access may be substantial. Always state those assumptions beside the headline query count.

Challenge: write the four-by-four diagonal phase oracle for marked item 01. Verify which one amplitude changes sign and explain why measuring immediately would not identify it.

Reference: IBM Quantum — Fundamentals of quantum algorithms.