Bernstein-Vazirani algorithm

In plain terms

Here is the problem. An oracle computes the parity of your input against a secret string: one bit out per query. Classically each query buys you one bit of the secret, so n bits cost n queries, and no cleverness helps.

Bernstein and Vazirani ask once. Prepare the uniform superposition, let the oracle write its parities into phases, undo the superposition. The interference is total: the register reads the secret string itself, with certainty, every time.

No probability, no repetition, no post-processing. One query, one answer.

In CSD

An algorithm witness in the Hadamard-oracle family, and the corpus proves the strong version: the full circuit's output amplitude is the Kronecker delta at the secret string -- outcome a with probability one (bv_certain), every other outcome zero (bv_zero). Unlike the reduced Simon analysis this is the complete phase-oracle sandwich, no measurement reduction.

Standing disclaimer as ever: the algorithms consume the unitary pillar; they do not support foundations.

Mathematically

The circuit is H^n then the phase oracle |x> to (-1)^{<a,x>} |x> then H^n, on |0^n>. The output amplitude at y is (1/2^n) sum over x of (-1)^{<y+a, x>}, and the character sum collapses to 2^n [y = a] -- the delta.

The content is one orthogonality of characters over F_2^n; the algorithm is the observation that a single physical query evaluates all the parities in superposition.

The name

Ethan Bernstein and Umesh Vazirani published it inside their 1993 STOC paper on quantum complexity theory -- the paper that defined BQP and made quantum computation a complexity class rather than a curiosity. Vazirani, at Berkeley, went on to shape much of the field's theory; Bernstein was his doctoral student.