Bernstein–Vazirani: One Query, Whole String
The Bernstein–Vazirani algorithm recovers a hidden n-bit string s from a black-box function f(x) = s·x mod 2 in exactly one quantum query, where any classical strategy needs n queries. A 4-qubit circuit reads the secret 101 directly off the measurement, deterministically.
What is the hidden-string problem?
An oracle — a black-box function you can call but not inspect — hides an n-bit secret string s. On input x (also n bits) it returns a single bit: f(x) = s·x mod 2, the dot product mod 2. In plain words: multiply the strings bit by bit, then XOR the results together (⊕ is XOR: 0⊕0=0, 0⊕1=1, 1⊕1=0). Writing bit i of s as s_i (s = s₂s₁s₀ for n = 3), that is f(x) = s₀x₀ ⊕ s₁x₁ ⊕ s₂x₂.
Example with the secret s = 101 (s₂=1, s₁=0, s₀=1) and query x = 011 (x₂=0, x₁=1, x₀=1): the bitwise products are s₀x₀ = 1·1 = 1, s₁x₁ = 0·1 = 0, s₂x₂ = 1·0 = 0, and 1 ⊕ 0 ⊕ 0 = 1. So f(011) = 1. Each query hands you exactly one bit — one parity of the secret (a parity is an even/odd summary: 1 if the secret's bits selected by x contain an odd number of 1s, 0 if even). The task: recover all of s in as few queries as possible. This chapter assumes you have met the phase-kickback trick; it is derived from scratch in the Deutsch–Jozsa chapter.
You’ve read the opening of chapter 4 — 7 more sections follow, with worked examples and circuits you can run on the page. A free account unlocks every chapter of every course (paid plans aren’t live yet — early readers get everything free).