Bernstein-Vazirani

The Bernstein-Vazirani problem (1992) is a cousin of Deutsch-Jozsa. It uses almost the same circuit but solves a different promise problem — and it’s arguably a cleaner illustration of how quantum interference extracts structure from an oracle in one query.

The problem

You’re given a function $f: \{0,1\}^n \to \{0,1\}$ with the promise that

$f(x) = s \cdot x \mod 2$

for some fixed, hidden string $s \in \{0,1\}^n$. Here $s \cdot x$ is the dot product $\sum_i s_i x_i$ — the bitwise AND followed by a parity check. Your job: find $s$.

Classically, you need $n$ queries: each query $f(e_i)$ (where $e_i$ is the $i$th basis string) returns $s_i$ directly. So you read each bit of $s$ one at a time — a total of $n$ queries.

Quantum: one query.

The algorithm

The circuit is almost identical to Deutsch-Jozsa:

1. Prepare $n$ qubits in $|0\rangle^{\otimes n}$.
2. Apply $H$ to each qubit.
3. Apply the phase oracle: $|x\rangle \mapsto (-1)^{f(x)}|x\rangle = (-1)^{s \cdot x}|x\rangle$.
4. Apply $H$ to each qubit.
5. Measure.

The punchline: after step 5, you measure $|s\rangle$ with certainty. The hidden string is the measurement outcome. One query, guaranteed.

Why it works

The key identity is about the Hadamard transform on all $n$ qubits:

$H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1\}^n} (-1)^{x \cdot y} |y\rangle$

After step 2, we have a uniform superposition. After step 3 (the oracle), the state is:

$\frac{1}{\sqrt{2^n}} \sum_x (-1)^{s \cdot x} |x\rangle = \frac{1}{\sqrt{2^n}} \sum_x (-1)^{s \cdot x} |x\rangle$

Now apply $H^{\otimes n}$:

$H^{\otimes n} \cdot \frac{1}{\sqrt{2^n}} \sum_x (-1)^{s \cdot x} |x\rangle = \frac{1}{2^n} \sum_x (-1)^{s \cdot x} \sum_y (-1)^{x \cdot y} |y\rangle$

$= \frac{1}{2^n} \sum_y \left[\sum_x (-1)^{(s + y) \cdot x}\right] |y\rangle$

The inner sum is $2^n$ if $s + y = 0 \pmod 2$ (i.e., $y = s$), and $0$ otherwise. So the final state is exactly $|s\rangle$. Measure and you read off the hidden string directly.

Why this is beautiful

The same three-step recipe — Hadamard, oracle, Hadamard — reads a hidden string in one query. It feels almost like cheating. Classically, you’d query $f(10\ldots0)$, $f(010\ldots0)$, etc., one bit at a time. Quantumly, the oracle acts on the full superposition at once, the phases it stamps encode the entire bitstring, and the final Hadamard layer transforms those phases into a single definite basis state — the hidden $s$.

The core mechanism behind all of the “Hadamard-oracle-Hadamard” algorithms (Deutsch-Jozsa, Bernstein-Vazirani, Simon’s) is the same:

• Hadamards create a uniform superposition.
• The oracle stamps phases onto the superposition, encoding the information about $f$ as a phase pattern across all basis states.
• Hadamards (or the quantum Fourier transform, for Simon’s) convert the phase pattern into a position pattern — a specific basis state that, when measured, reveals the hidden structure.

This “phase pattern → position pattern” is a recurring theme. Grover’s search, Shor’s algorithm, and the quantum Fourier transform all use variations of it.

What’s next

Simon’s algorithm applies the same recipe to find a hidden period — and crucially, its quantum speedup is exponential even against randomized classical algorithms. That’s a hint that some quantum speedups are genuine, not just artifacts of insisting on zero error.