Bernstein–Vazirani: One Query, Whole String
The Bernstein–Vazirani algorithm finds a hidden n-bit string s with exactly one quantum query. The hidden function is f(x) = s·x mod 2. Any normal method needs n queries. A 4-qubit circuit reads the secret 101 straight off the measurement, every time.
What is the hidden-string problem?
Why care? This is the cleanest example of a quantum computer pulling many bits of an answer out of one question. It is also a popular health check for real hardware.
An oracle is a black-box function you can call but not look inside. This one hides an n-bit secret string s. You give it an input x, also n bits long. It gives back one bit: f(x) = s·x mod 2. That is the dot product mod 2. In plain words: multiply the two strings bit by bit, then XOR the results together. (⊕ is XOR: 0⊕0=0, 0⊕1=1, 1⊕1=0.) Call bit i of s by the name s_i. For n = 3, s = s₂s₁s₀. Then f(x) = s₀x₀ ⊕ s₁x₁ ⊕ s₂x₂.
Let us work one. The secret is s = 101, so s₂=1, s₁=0, s₀=1. The query is x = 011, so x₂=0, x₁=1, x₀=1. The bit-by-bit products are s₀x₀ = 1·1 = 1, s₁x₁ = 0·1 = 0, and s₂x₂ = 1·0 = 0. Then 1 ⊕ 0 ⊕ 0 = 1. So f(011) = 1.
Each query gives you exactly one bit. That bit is one parity of the secret. A parity is an odd-or-even summary. It is 1 if the secret bits picked out by x hold an odd number of 1s, and 0 if even. Think of a guessing game where you point at some cards and a friend only says "odd" or "even" for how many of them are red. The task: find all of s in as few queries as you can.
This chapter uses the phase-kickback trick. It is built from scratch in the Deutsch–Jozsa chapter.
- How many queries does a classical program need?
- How do we build the oracle and read the answer?
- One query, secret 101INTERACTIVE
- Why is one query enough?
- Change the secret to 110INTERACTIVE
- What are the honest caveats?
- What does Bernstein–Vazirani look like on real devices?
You’ve read the opening of chapter 4. Pro unlocks the other 7 sections — plus every chapter of every course, with circuits you can run right on the page. That’s $11.99 a month, about the price of a coffee, or $99.99 a year (save 30%). The first chapter of every course, and the whole math course, stay free.