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.

Specify the oracle on every basis input

WORKED DIAGRAM · F24One abstract phase query can contain several gates

For a two-bit oracle marking 11, CZ = H on q1, then CX 0→1, then H on q1. One oracle query in a high-level model can therefore contain multiple native gates. More complex predicates can be much more expensive.

The diagram implements a two-qubit phase flip on 11 using H on the target, CX, then H on the target. This is controlled-Z. Its action is diagonal: it negates the 11 amplitude and leaves the others unchanged. A two-wire phase oracle can therefore be built from elementary gates rather than treated as an unexplained box.

An oracle contract must also specify any target or workspace. A bit oracle XORs a function value into a target. A phase oracle multiplies each input component by a sign. Phase kickback relates these forms under a suitable target preparation. They are not interchangeable without identifying those preparations, ancillas and possible controlled-use requirements.

Worked example: mark the label 11

Start with two qubits in the uniform state, so all four amplitudes are one half. A phase oracle for the predicate “x equals 11” changes the last entry to negative one half. The Z probabilities remain one quarter each. The oracle has marked the item coherently, but it has not yet increased its chance of appearing at readout.

Apply the diffusion operation that reflects amplitudes about their mean. After the sign flip, the mean is one quarter. Each unmarked amplitude maps to twice one quarter minus one half, giving zero. The marked amplitude maps to twice one quarter minus negative one half, giving one. One complete Grover iteration therefore produces 11 with certainty in this special case.

If you want to mark 01 instead, apply X to q0 before and after the controlled-Z. The first X maps 01 to 11 for the phase operation, and the last X restores the original labels. This conjugation changes which basis state receives the sign while preserving every other label. Verify it on all four basis inputs rather than reasoning only from the marked one.

The promise is part of the input

A function can be constant, balanced or neither when it has more than one input bit. Deutsch–Jozsa assumes only the first two possibilities. A zero or nonzero measurement outcome has its advertised interpretation under that promise. If a function violates it, the output distribution still follows quantum mechanics but no longer supports the same classification guarantee.

Grover’s assumptions are different. It needs a coherent predicate and an estimate or method for handling the number of marked items. A wrong iteration schedule can rotate amplitude past the useful region. The algorithm is not an instruction to keep repeating until the histogram looks good, because observing intermediate results changes the experiment and can bias a performance report.

Input access has a cost

Suppose the predicate compares a candidate with a fixed short bitstring. Its reversible circuit can be relatively simple. Suppose instead it validates a large schedule with many constraints or accesses a massive classical database. The oracle may require substantial arithmetic, workspace and data movement. Counting either task as “one query” is useful for an abstract theorem but insufficient for an engineering estimate.

Data loading is especially easy to hide in a block-box description. A coherent lookup interface is a resource that must be supplied, built or assumed. It is not automatically available because the data resides in ordinary memory. An honest application analysis identifies whether the oracle computes a structured function or queries a pre-existing data structure, and charges the relevant preparation and access costs.

Test the phase-oracle consequence

The Grover lab contains a built-in single-item phase predicate. At two input qubits and zero iterations, predict the uniform distribution. Then select one iteration and predict the marked outcome. The lab does not offer an oracle-only stage, so use the diagram and signed-amplitude calculation above to explain the intermediate sign flip before diffusion.

L06 · INTERACTIVE LABRuns on your device

Grover search explorer

A phase oracle marks one item; diffusion reflects amplitudes about their mean. Amplification can overshoot. Oracle construction and hardware costs are excluded.

Experiment controls

Grover iterations1Random seed

Predict the marked item’s success probability at this register size and iteration count. Explain an expected increase or decrease.

Your prediction

Reveal exact resultsRun measurements →Reset

Record a prediction to enable the results.

Results are hidden.

Prepare your experiment using the controls. Record a prediction, then reveal the statevector or run the experiment.

Changing the preparation or circuit starts a new prediction.

MODEL · Ideal pure-state vector, complex double precisionORDER · q0 is the leftmost bit

Take it further

For four items, trace all amplitudes through one iteration. For eight, compare iterations 0–6 and explain the oscillation.

Initial setup · reference state

Exact probability

|00⟩

0.0%

|01⟩

0.0%

|10⟩

0.0%

|11⟩

100.0%

Marked item probability 100.0%

Statevector before readout · ideal simulation

Basis	Amplitude a + bi	Magnitude	Phase (rad)	Probability
|00⟩	0 + 0i	0.000000	undefined	0.0%
|01⟩	0 + 0i	0.000000	undefined	0.0%
|10⟩	0 + 0i	0.000000	undefined	0.0%
|11⟩	1 + 0i	1.000000	0.000000	100.0%

Signs and complex phases are part of the state. Phase is undefined for a zero amplitude. A shared global phase changes no probabilities; relative phases can affect a later operation. Values are rounded to six decimal places.

Prediction to try: Predict the marked item’s success probability at this register size and iteration count. Explain an expected increase or decrease.

Challenge: For four items, trace all amplitudes through one iteration. For eight, compare iterations 0–6 and explain the oscillation.

Open the live experiment studio

Change the marked label and repeat the prediction. The final success probability should be unchanged in the symmetric ideal four-item model, while the location of the nonzero amplitude moves. Changing the number of qubits changes the rotation angle and removes the special exact-one-iteration result. Those comparisons test both the predicate contract and the surrounding algorithm.

Practice: distinguish access from answers

A description says, “A quantum oracle reads all database records at once, so it returns every matching record in one call.” Identify two separate errors and state what a coherent query actually provides.

Check your reasoning

A coherent input-access operation must be implemented or explicitly assumed; ordinary database storage does not provide it for free. Applying that operation to a superposition transforms amplitudes according to the oracle rule, but a measurement does not return every branch’s answer. The algorithm must use further interference and repeated runs to extract its specified output, and reporting many matches has its own output cost.

Check your understanding

PAUSE & THINK

Does a phase oracle alone increase the marked item’s Z probability?

Choose your answer

YesNo; interference is needed afterwardOnly if its amplitude becomes negative

Check my answer

Answer: No; interference is needed afterward. Negating an amplitude preserves its squared magnitude. Grover’s diffusion converts the phase pattern into population changes.

Reference: IBM Quantum — Fundamentals of quantum algorithms.