Bernstein–Vazirani Algorithm

Same circuit as Ch. 26, one more time — but instead of classifying f into one of two buckets, this version's oracle hides an entire n-bit secret, and the algorithm reads the whole thing out, exactly, from a single query.

The problem

The oracle computes f(x) = s·x mod 2 — the bitwise dot product of x with some hidden n-bit string s, mod 2 — for an s you don't know and need to find. Classically this takes n separate queries: query x=1000...0 to learn s's first bit, x=0100...0 for the second, and so on, one bit revealed per query. The quantum algorithm needs exactly 1.

Why this works: it's Deutsch–Jozsa's math, reused

Run through the identical H–oracle–H derivation from Ch. 26, but now with f(x)=s·x mod 2 instead of a generic balanced/constant function. The final amplitude on basis state y works out to be exactly 1 when y=s, and exactly 0 for every y≠s. There's no new mathematical machinery here at all — Bernstein–Vazirani is a specific, clever choice of oracle slotted into the exact circuit Ch. 26 already built.

What's genuinely new here

Deutsch–Jozsa only ever answers a single yes/no question (constant or balanced); Bernstein–Vazirani extracts n full bits of hidden information in that same one query. This is the first algorithm in the book that demonstrates a quantum computer reading out a complete, exact classical answer — not just a property of one — exponentially faster than any classical strategy. It's also a direct structural preview of Simon's algorithm and the hidden subgroup problem more broadly, the family of problems Shor's algorithm (Ch. 31) ultimately belongs to: "find a hidden algebraic structure using interference from a superposition of queries" is the same recipe, just with progressively richer structure being hidden.