The Bernstein–Vazirani Algorithm

Someone has picked a secret n-bit string s and locked it inside a black box. You are not allowed to look at s directly; all you may do is feed the box a string x and it hands back a single bit — the bitwise dot product f(x) = s\cdot x \bmod 2. How many questions do you need to pin down every bit of s?

Classically the honest answer is n questions — one per bit. The Bernstein–Vazirani algorithm does it in a single query, no matter how long s is. And the astonishing part: the circuit is the exact circuit you already met in the Deutsch–Jozsa algorithm — Hadamards, a phase oracle, Hadamards, measure — but this time the string you read off the meters is the hidden secret, spelled out bit for bit.

The oracle: a hidden dot product

Fix a secret string s = s_1 s_2 \cdots s_n. The oracle computes the parity of the bits of x that s selects:

f(x) = s\cdot x = s_1 x_1 \oplus s_2 x_2 \oplus \cdots \oplus s_n x_n \pmod 2,

where \oplus is XOR (addition mod 2). It is a linear function: it just picks out the positions where s has a 1 and adds those bits of x together, mod two. For example, with s = 101 the middle bit of x is ignored and

s\cdot x = x_1 \oplus x_3.

So f(110) = 1\oplus 0 = 1, f(011) = 0\oplus 1 = 1, and f(111) = 1\oplus 1 = 0. The whole secret lives in which bits get summed — and that is exactly what we want to uncover.

The classical way: read s one bit at a time

A classical solver can extract s with a clever choice of queries. Feed the box the unit string e_i that is 1 in position i and 0 everywhere else. Then

s\cdot e_i = s_i,

because every product s_j (e_i)_j vanishes except the one at j = i. So querying e_1 = 100\ldots0 reveals s_1, e_2 = 010\ldots0 reveals s_2, and so on. Each query yields exactly one bit, and there are n bits, so you cannot beat n queries classically — a single query returns one parity bit and one bit can distinguish at most two possibilities.

The quantum circuit

Take n input qubits in |0\rangle and one ancilla in |1\rangle. Apply Hadamard to all of them, run the oracle once, apply Hadamard to the input register again, and measure it. That is the entire algorithm — step through it below for n = 3 and the hidden string s = 101:

The ancilla, put into |-\rangle by its Hadamard, turns the oracle into a phase oracle by phase kickback: instead of writing f(x) into a wire, it multiplies each branch |x\rangle by (-1)^{f(x)}. Everything interesting now happens in the phases of the input register.

Why the meters spell out s

Start the input register in |0\rangle^{\otimes n}. The first Hadamard layer spreads it into an equal superposition of every string:

H^{\otimes n}|0\rangle^{\otimes n} = \frac{1}{\sqrt{2^n}}\sum_{x} |x\rangle.

Running the phase oracle multiplies each branch by (-1)^{s\cdot x}, leaving

\frac{1}{\sqrt{2^n}}\sum_{x} (-1)^{s\cdot x}\,|x\rangle.

Here is the whole trick in one line. That state is exactly what you get by Hadamarding the basis state |s\rangle, because

H^{\otimes n}|s\rangle = \frac{1}{\sqrt{2^n}}\sum_{x} (-1)^{s\cdot x}\,|x\rangle.

So the oracle has secretly left the register sitting on H^{\otimes n}|s\rangle. Now apply the second Hadamard layer. Since H is its own inverse (H^{\otimes n}H^{\otimes n} = I), it undoes the first one perfectly:

H^{\otimes n}\!\left(\frac{1}{\sqrt{2^n}}\sum_{x} (-1)^{s\cdot x}\,|x\rangle\right) = H^{\otimes n}H^{\otimes n}|s\rangle = |s\rangle.

The register is now on the single basis state |s\rangle — no superposition, no randomness. Measuring gives the bits of s with certainty. Written out the long way, the interference is a sum that cancels everywhere except at z = s:

\frac{1}{2^n}\sum_{z}\Big(\sum_{x} (-1)^{s\cdot x}(-1)^{x\cdot z}\Big)|z\rangle = \frac{1}{2^n}\sum_{z}\Big(\sum_{x} (-1)^{x\cdot(s\oplus z)}\Big)|z\rangle = |s\rangle,

since the inner sum is 2^n when z = s and 0 otherwise. The Hadamard transform of a linear phase is a single basis state — that is the engine of the whole algorithm.

Worked example: n = 3, s = 101

Let us watch the three-qubit register carry the secret through. After the first Hadamards and the oracle, every branch |x\rangle wears the sign (-1)^{s\cdot x} = (-1)^{x_1 \oplus x_3}:

\tfrac{1}{\sqrt 8}\big(|000\rangle - |001\rangle - |010\rangle + |011\rangle + \cdots\big).

Reading the signs: |001\rangle gets -1 (its bits give 0\oplus 1 = 1), |100\rangle gets -1 (1\oplus 0 = 1), and |101\rangle gets +1 (1\oplus 1 = 0). This is precisely H^{\otimes 3}|101\rangle. Apply the second Hadamard layer and everything collapses onto one term:

H^{\otimes 3}\big(H^{\otimes 3}|101\rangle\big) = |101\rangle.

The meters read 1, 0, 1 with probability 1. One query, and the full three-bit secret s = 101 falls out. A classical solver would have spent three separate queries (100, 010, 001) to learn the same thing.

Worked example: a longer secret, still one query

Nothing about the argument cared that n was 3. Take a five-bit secret s = 11010. Classically you would query 10000, 01000, 00100, 00010, 00001 — five separate calls — to read the five bits one by one. Quantumly the register runs the identical H^{\otimes 5}–oracle–H^{\otimes 5} sequence and lands on

H^{\otimes 5}H^{\otimes 5}|11010\rangle = |11010\rangle,

so a single measurement returns 11010 outright. The quantum cost stays at one query while the classical cost grows with n: the algorithm reads the global linear structure of f in one shot, rather than probing it coordinate by coordinate.

Think of the secret s as a chord and each query string x as a tuning fork. A classical solver strikes one fork at a time and listens for whether it rings — n strikes to name every note. The quantum register instead strikes all forks at once and lets them interfere. The oracle writes the secret into the phases as one clean linear pattern, and the final Hadamard layer is a prism that refracts that pattern straight onto a single basis state: the whole chord, named in one listen. That prism — the Hadamard transform of a linear phase landing on exactly |s\rangle — is the entire idea.

The n \to 1 speedup is real and exact — no error probability, no repeated runs — but keep two caveats in view. First, the oracle already encodes s: the algorithm does not conjure the secret from nothing, it efficiently reads out a string that was baked into the box. Second, like Deutsch–Jozsa, this is a query-model result: the win is counted in oracle calls, and it hinges on a very special promise (that f is linear). The lesson is not that quantum computers magically know secrets — it is that interference can read a global linear structure all at once, where a classical machine is forced to probe it one coordinate at a time.