What can one query reveal?
A quantum algorithm does not obtain every value of a function by measuring a superposition. It can, however, arrange phases from a reversible oracle so that a later interference pattern answers a particular global question. Deutsch–Jozsa is a clean example: with one oracle call it distinguishes two promised kinds of Boolean functions exactly. The promise and the query model are essential to the conclusion.
Definition 2.1.1
(Constant and balanced functions)
Let , , and . A constant function has the same value at every input. A balanced function takes each value on exactly inputs. The task is to decide which case holds, with the guarantee that the input function is one or the other. No correct answer is specified for a function outside this promise.
Definition 2.1.2
(Reversible oracle and query)
The standard reversible oracle acts on an input register and one target qubit by
For every fixed , this either keeps or flips the target, so it permutes the computational basis and is unitary. A query counts one use of ; the physical cost of constructing that oracle is not included in the query count. The promise does not say that an arbitrary has a small circuit.
A phase from a reversible query
Let and . Since ,
The target returns to the same state, while the input branch receives a phase. This phase kickback follows by linearity from the reversible oracle; it is not a measurement of on all inputs.
Prepare , apply to every qubit, call once, and apply to the first register. Using the binary dot product and the identity
the final state is
Measure the first register and output “constant” exactly when the outcome is .
Common mistake
(Using instead of as the target)
With target the oracle produces , which records in the target instead of a phase. After the final Hadamards the amplitude of in the first register is , a vector with squared length , where count the inputs with value . For a balanced function this is , so is measured half of the time and the decision rule fails. The target must be prepared in , that is, as followed by .
Theorem 2.1.3
(Exact decision under the promise)
The algorithm uses one oracle query and is correct with probability one for every constant or balanced .
Proof
(Amplitude at the all-zero outcome)
At , the amplitude is . If is constant, or , so the measurement gives with probability one. If is balanced, the positive and negative terms cancel, giving , so is never measured. The output rule is therefore correct in both promised cases.
Proof X-ray
What the interference actually computes
The first Hadamards prepare equal amplitudes; the oracle changes their signs according to ; the last Hadamards add signed contributions at each output. At all extra dot-product signs are one, so its amplitude is the average of . Only this aggregate is needed for the promised decision. The circuit does not reveal the complete truth table in one measurement.
Worked example 2.1.4
(A balanced and a constant function for two bits)
For and , exactly two of the four inputs have value one. The final first register is , so the output is certainly “balanced.” For the constant-one function, the final first register is ; the minus sign is global and the output is certainly “constant.”
Worked example 2.1.5
(A balanced function that is a character)
Let and . It equals one at exactly two of four inputs, so it is balanced. The amplitude factors over the two bits:
and the first factor is if and otherwise, the second is if and otherwise. Hence and every other amplitude vanishes. The measurement returns , so the output is “balanced,” as it must be. This function is the hidden-string function with .
Common mistake
(A negative amplitude is still the constant case)
For the constant-one function, . Some readers take the sign to mean that the function is “not constant.” Measurement probabilities depend on , so is measured with certainty; the minus sign is a global phase and has no effect on the outcome.
What the promise changes
Counterexample mode
Outside the promise, the output is not a complete classification
For , let be one only at . It is neither constant nor balanced. Here , so the measurement returns with probability and a nonzero string with probability . Either algorithmic answer would misclassify this function if the only allowed labels were “constant” and “balanced.” The exact guarantee applies to the promised inputs; it does not assert that every Boolean function belongs to one of the two cases.
For arbitrary , the probability of is . It measures the squared imbalance between the two output values. A zero probability implies balance, but a single nonzero measurement outcome outside the promise does not by itself prove exact balance.
The explorer below computes every first-register amplitude exactly for a truth table you edit, so you can see that the amplitude of is the average sign of and what changes outside the promise.
Classical query comparisons
Proposition 2.1.6
(Deterministic exact query complexity)
Under the promise, every deterministic classical algorithm that is always correct makes at least queries on some input function, and distinct queries suffice.
Proof
(An adversary answers zero)
Answer zero to the first distinct queries. The answers are consistent both with the constant-zero function and with a balanced function completed by assigning ones to unqueried inputs. Repeating a query gives no new information. Thus the algorithm cannot safely stop after at most queries on that transcript. Querying distinct inputs suffices: if both values appear, the function is balanced; if all agree, a balanced function is impossible.
This is an exact deterministic comparison, not an exponential separation from bounded-error randomized classical algorithms. For example, sample distinct inputs uniformly without replacement and declare “balanced” if both values appear; otherwise declare “constant.” Constants are always correct. On a balanced function the probability of error is
with when . Each factor in is at most when nonzero. Thus a fixed error tolerance needs only a constant number of randomized classical queries when enough inputs are available. The one-query quantum algorithm has an exact advantage in this oracle model; that fact alone does not establish an exponential bounded-error runtime separation for a concrete computational problem.
Worked example 2.1.7
(Randomized test on eight inputs)
Let , so , and sample distinct inputs. For the error probability on a balanced function is , below the bound . For it is . For we have , so the error probability is : five distinct inputs cannot all take the same value on a balanced function. This is the edge case where the randomized test becomes exact, at the cost of queries as in the deterministic bound.
A related hidden-string problem
Suppose instead that for an unknown . This is a different promise, including .
Proposition 2.1.8
(One-query recovery of a hidden string)
For , the same phase-query circuit measures with certainty after one query. Every deterministic classical algorithm that always finds needs at least bit-valued queries in the worst case, even when queries are adaptive.
Proof
(Amplitudes factor over coordinates)
The same phase-query circuit has amplitude
The last equality follows because the sum factors by coordinates: if any bit of is one, summing over that input bit cancels the terms. Thus one measurement returns the entire string with certainty. For the classical bound, a depth- decision tree has at most answer transcripts, but the algorithm must distinguish possible strings, so .
This is the Bernstein–Vazirani algorithm. The comparison counts oracle queries rather than the cost of implementing the oracle.
Concept lensAlgebraic
The amplitudes as a Walsh–Hadamard transform
Write . Then is the Walsh–Hadamard transform of the normalized sign vector , a unitary change of basis from the points to the characters . In this description the cases above are one statement. is the average of , so a constant puts all weight at and a balanced puts none there; a character puts all weight at . Since the transform is unitary, for every : weight removed from is necessarily placed elsewhere.
Practice with solutions
Quick check
(For , write the phase-oracle action on and when , . What is the final first-register measurement?)
Solution · Answer
The two branches acquire phases and . The first register is after the query and becomes after ; it is measured as .
Quick check
(For , let equal one only at . Calculate the probability of measuring and explain why the promised decision theorem does not apply.)
Solution · Answer
Three phase signs are positive and one negative, so and the probability is . The function is neither constant nor balanced.
Quick check
(A deterministic classical algorithm sees zero on four distinct inputs when . Can it already distinguish a constant function from a balanced one with certainty under the promise?)
Solution · Answer
No. With , the four zeros can be extended to the constant-zero function or to a balanced function by assigning ones to all four unseen inputs.
Quick check
(For and hidden string , what does the hidden-string algorithm measure? Why do all other amplitudes vanish?)
Solution · Answer
It measures with certainty. For , at least one bit of is one, and the two values of the corresponding input bit cancel in the phase sum.