Algorithm Zoo · Search
Bernstein-Vazirani
First described: Bernstein, Vazirani, 1993
The problem
Recover a hidden n-bit string s given oracle access to f(x) = s · x mod 2.
Strengthens Deutsch-Jozsa: recovers s in one query, where classical deterministic needs n queries. Classical randomized still needs Ω(n) — so the separation is also against randomized algorithms in this case.
Best classical
n queries (deterministic or randomized).
Quantum complexity
1 query.
Our verdict
First proof of separation against randomized classical algorithms in the oracle model. Same status as Deutsch-Jozsa — historic, pedagogical, not practical.
When to use it
- Teaching, hardware benchmarks.
When not to use it
- Anything practical.
Classical baseline
n function evaluations on the n standard basis vectors.
Hardware cost
n+1 qubits, one oracle query, depth O(1) (parallel oracle).
Key papers
- Quantum Complexity Theory ↗
Bernstein, Vazirani · 1997 · SIAM J. Computing
Deep-dive tutorials
Last verified: 2026-05-24