Bernstein–Vazirani
Bernstein–Vazirani recovers a hidden n-bit string s from an oracle computing f(x) = s·x mod 2 in a single query; any classical algorithm provably needs n queries. The separation is real but linear, not exponential — its value today is as a hardware benchmark and the clearest showcase of phase kickback turning one query into n bits of answer.
| Task | Best classical | Quantum |
|---|---|---|
| Recover the n-bit hidden string | n queries (provably optimal) | 1 query |
What problem does it solve?
An oracle hides an n-bit string s. On input x it returns one bit: the parity of the bits of x selected by s — in code, popcount(s & x) % 2. Your job is to recover s in as few calls as possible.
Developer framing: an API returns a checksum over an unknown subset of your input bits, and you want the mask.
The classical approach
Probe with one-hot inputs: querying x = 0…010…0 (a 1 in position i) returns exactly s_i. That takes n queries, and no classical strategy beats it — each query returns a single bit, and s contains n bits of information. The lower bound is information-theoretic and airtight.
So the classical cost is already cheap: linear, trivially parallel. Keep that in mind when weighing what the quantum version buys.
How does one quantum query recover all n bits?
Same skeleton as Deutsch–Jozsa: ancilla in |−⟩, Hadamards on the inputs, one oracle call, Hadamards again. The oracle XORs s·x into the ancilla, so each superposed branch |x⟩ picks up the sign (−1)^(s·x) — phase kickback again.
Here is the punchline: that exact sign pattern across all 2^n basis states is what you get by applying Hadamards to the state |s⟩. The final Hadamard layer just runs that transform in reverse, so the register lands on |s⟩ deterministically. No statistics, no repetition — read the string off one measurement.
A quantum query is a stronger resource than a classical one: it evaluates the function once on a superposition, and interference converts the resulting phase pattern back into bits. That is the honest description — nothing was computed "in parallel universes".
What it does not prove
Three honest caveats.
- Linear, not exponential. The saving is
nqueries down to 1. Useful as a demonstration; not the kind of separation that changes what is computable in practice. - The oracle is self-fulfilling. The CX pattern in the oracle is the string
s— the answer is compiled into the circuit. This is a statement about query counts, not about extracting unknown information from the world. - The strong versions are different beasts. A recursive variant of this problem gives a superpolynomial separation, but that is a different construction and does not run on today's hardware at meaningful sizes.
What does this look like on real hardware?
Bernstein–Vazirani is a favourite hardware benchmark: one ancilla, up to n CX gates, shallow depth, and a single correct answer to check against. Runs at 5–15 input qubits are routine on current devices, with success probability decaying as n grows.
It also exposes topology honestly. Every CX targets the same ancilla, so on sparse-connectivity chips the transpiler must insert SWAP chains to ferry qubits next to it — connectivity costs made visible. All-to-all machines (trapped ions) handle the fan-in natively. Compare the same circuit across architectures on the hardware comparison page.