Lesson 14: The Bernstein–Vazirani Algorithm¶
14.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- State the hidden-string problem and its classical query complexity.
- Derive the Bernstein–Vazirani algorithm and prove it recovers \(a\) deterministically in one query.
- Evaluate the key character sum \(\sum_x(-1)^{(a\oplus y)\cdot x}\) and explain the resulting interference.
- Build the oracle for any hidden string \(a\).
- Explain why this gives \(n\) bits of information from one query without violating Holevo's bound.
14.2 The Problem¶
Setup. An oracle computes
for a fixed but unknown string \(a \in \{0,1\}^n\).
Goal. Determine \(a\).
Classical query complexity¶
Each query returns a single bit. To learn \(n\) unknown bits you need \(n\) bits of output, so at least \(n\) queries are required — and \(n\) suffice, using the standard-basis probes:
This bound is information-theoretic: it holds for deterministic and randomised algorithms. To learn \(n\) bits you must receive \(n\) bits. There is no probabilistic loophole here — unlike Deutsch–Jozsa.
Quantum query complexity¶
A linear \(n \to 1\) separation, and it is against randomised classical algorithms too. This makes Bernstein–Vazirani a cleaner demonstration than Deutsch–Jozsa, even though the speed-up is "only" linear.
14.3 The Algorithm¶
Circuit¶
The circuit is identical to Deutsch–Jozsa. Only the oracle and the interpretation change.
q0 ... q(n-1) : --[H]^n--------.------[H]^n----[M]^n--> a
|
[ U_f ]
|
q_ancilla : --[X]--[H]-----'--------------------
Derivation¶
Step 1.
Step 2 — oracle with phase kick-back.
Notice what this state is. Recall from L07 that
So
The oracle has literally prepared the Hadamard transform of \(|a\rangle\). The string \(a\) is now encoded in the phase pattern of the superposition.
Step 3 — undo the Hadamard. Since \(H^{\otimes n}\) is its own inverse (\(H^2 = I\)):
Step 4 — measure. The register is exactly \(|a\rangle\), so the measurement returns the hidden string \(\mathbf{a}\) with probability 1. \(\blacksquare\)
The interference calculation, done explicitly¶
If the elegance of "\(H^2 = I\)" feels like a trick, here is the direct amplitude computation.
Since \(a\cdot x + x\cdot y = (a\oplus y)\cdot x \pmod 2\), the amplitude of \(|y\rangle\) is
Lemma (character sum). For any \(z\in\{0,1\}^n\):
Proof. The sum factorises over bit positions:
Each factor is \(1 + 1 = 2\) if \(z_j = 0\), and \(1 + (-1) = 0\) if \(z_j = 1\). So the product is \(2^n\) if every \(z_j = 0\), and \(0\) if any \(z_j = 1\). \(\blacksquare\)
Applying the lemma with \(z = a\oplus y\):
Perfect constructive interference at \(y = a\); perfect destructive interference at all other \(2^n - 1\) strings. This is the cleanest interference pattern in the whole course.
14.4 Building the Oracle¶
\(U_{f_a}|x\rangle|y\rangle = |x\rangle|y\oplus(a\cdot x)\rangle\) is implemented by a CNOT from \(q_j\) to the ancilla for every \(j\) with \(a_j = 1\), and nothing else.
Why. Each CNOT XORs \(x_j\) into the ancilla. Stacking them XORs \(\bigoplus_{j: a_j=1} x_j = a\cdot x\).
Cost: at most \(n\) CNOTs, depth \(n\) (or depth \(O(\log n)\) with a CNOT tree, but the ancilla is a shared target so it is naturally sequential).
| Hidden \(a\) (\(n=4\)) | Oracle |
|---|---|
| \(1011\) | CNOTs from \(q_1, q_3, q_4\) |
| \(0000\) | no gates (then \(f\equiv0\)) |
| \(1111\) | CNOTs from all four qubits |
14.5 Holevo's Bound — Why This Is Not a Contradiction¶
Holevo's bound. \(n\) qubits can convey at most \(n\) classical bits of accessible information.
Bernstein–Vazirani extracts \(n\) bits from one query. Is this a violation?
No. Holevo bounds the information carried by transmitted qubits, not by oracle queries. The \(n\)-qubit register is \(n\) qubits, so it can carry \(n\) bits — and it does. The oracle is not a communication channel with a bit budget; it is a unitary applied to \(n\) qubits at once. Classically, one evaluation of \(f\) returns one bit; quantumly, one application of \(U_f\) touches an \(n\)-qubit register.
The right statement: the quantum advantage is not "more information per bit" but "one operation instead of \(n\) operations".
14.6 Solved Problems¶
Problem 1 — Full trace for n = 3, a = 101¶
Run Bernstein–Vazirani with hidden string \(a = 101\).
Solution.
Oracle: CNOTs from \(q_1\) and \(q_3\) to the ancilla (positions where \(a_j = 1\)).
Step 1:
Step 2: \(f(x) = x_1\oplus x_3\). Compute the phases:
| \(x\) | \(x_1\oplus x_3\) | phase |
|---|---|---|
| 000 | 0 | \(+\) |
| 001 | 1 | \(-\) |
| 010 | 0 | \(+\) |
| 011 | 1 | \(-\) |
| 100 | 1 | \(-\) |
| 101 | 0 | \(+\) |
| 110 | 1 | \(-\) |
| 111 | 0 | \(+\) |
Factorise by inspection — the sign depends on \(x_1\oplus x_3\), so:
(check: \(|-\rangle\) on qubits 1 and 3 supplies \((-1)^{x_1}\) and \((-1)^{x_3}\); \(|+\rangle\) on qubit 2 supplies no phase ✓).
Step 3: \(H|-\rangle = |1\rangle\), \(H|+\rangle=|0\rangle\):
Measurement returns \(\mathbf{101} = a\) with probability 1 ✓, in one query. Classically this would need 3 queries.
Problem 2 — Amplitude verification for a wrong guess¶
For \(n=3\), \(a = 110\), compute the amplitude \(A_y\) at \(y = 100\) and confirm it vanishes.
Solution.
The exponent depends only on \(x_2\). Of the 8 strings, 4 have \(x_2 = 0\) (sign \(+1\)) and 4 have \(x_2=1\) (sign \(-1\)):
Now check \(y = a = 110\): \(z = 000\), so every term is \(+1\):
Problem 3 — Query comparison and a practical timing¶
A 256-bit hidden string is to be recovered. Compare classical and quantum query counts. If each oracle call takes 10 µs on both platforms, compare total time.
Solution.
Classical: \(n = 256\) queries.
Quantum: 1 query.
Speed-up factor: 256×.
Caveat worth stating to students. The quantum circuit needs 256 qubits and 512 Hadamards plus up to 256 CNOTs; on NISQ hardware, gate errors would swamp the result long before 256 qubits. With per-gate error \(\epsilon\), the success probability is roughly \((1-\epsilon)^{G}\) where \(G \approx 768\). For \(\epsilon = 10^{-3}\) this is \((0.999)^{768} \approx 0.46\) — a coin flip. Bernstein–Vazirani is a correctness demonstration, not a practically useful speed-up. Its real importance is as the scaffolding for Simon's algorithm and as a standard hardware benchmark.
Problem 4 — Recovering an affine function¶
Now let \(f(x) = a\cdot x \oplus b\) for unknown \(a\in\{0,1\}^n\) and unknown \(b\in\{0,1\}\). Can the algorithm still recover \(a\)? Can it recover \(b\)?
Solution. After the oracle:
The extra \(b\) contributes \((-1)^b\) uniformly to every term — a global phase.
Measurement still returns \(a\) with probability 1 ✓. The constant offset \(b\) is invisible, exactly as in the Deutsch algorithm where constant-0 and constant-1 were indistinguishable.
Recovering \(b\) requires one additional query. Classically, query \(x = 0^n\): then \(f(0^n) = a\cdot 0 \oplus b = b\) directly. So:
Classically the same task needs \(n+1\) queries.
Problem 5 — Bernstein–Vazirani with a noisy oracle¶
Suppose each oracle CNOT fails (acts as identity) independently with probability \(q\). For \(a\) with Hamming weight \(w\), find the probability of recovering \(a\) exactly, and evaluate for \(n=8\), \(w=5\), \(q=0.02\).
Solution. The oracle consists of \(w\) CNOTs, one for each 1-bit of \(a\). If the CNOT for position \(j\) fails, then bit \(j\) of \(a\) is never XORed into the ancilla, and the effective hidden string has \(a_j\) replaced by 0.
Each of the \(w\) CNOTs must succeed, independently:
For \(n=8\), \(w=5\), \(q=0.02\):
Expected number of wrong bits: \(wq = 5\times0.02 = 0.1\).
Design lesson. Errors here are not randomising — they are systematically biased toward zero, because a missing CNOT can only remove a 1 from the recovered string, never add one. So majority voting over repeated runs converges quickly: run the circuit \(R\) times and take the OR (not the majority) of the results, which recovers \(a\) correctly with probability \((1-q^R)^w\). For \(R = 3\): \((1 - 8\times10^{-6})^5 \approx 0.99996\).
Recognising the structure of the noise, not just its magnitude, is the essence of error mitigation (L38).
14.7 Practice Problems¶
- Trace the algorithm for \(n=4\), \(a = 0110\). [Ans: measures \(0110\); oracle = CNOTs from \(q_2,q_3\)]
- Compute \(A_y\) for \(n=2\), \(a=11\), \(y=01\) using the character-sum lemma. [Ans: 0]
- Prove the character-sum lemma for \(n=2\) by writing out all four terms.
- How many classical queries are needed for a 1024-bit hidden string, and how many quantum? [Ans: 1024 and 1]
- Explain why \(\Pr[y]=|A_y|^2\) sums to 1 in this algorithm using the lemma.
- Modify the oracle so that \(f(x) = a\cdot x \oplus 1\) and confirm experimentally (on the web lab) that the answer is unchanged.
- Why does Bernstein–Vazirani beat randomised classical algorithms while Deutsch–Jozsa does not?
14.8 Summary¶
- Problem: learn the hidden string \(a\) from an oracle for \(f_a(x) = a\cdot x\).
- Classical: exactly \(n\) queries — an information-theoretic bound holding for randomised algorithms too.
- Quantum: 1 query, deterministic. This is a genuine (linear) separation against randomised classical computation, unlike Deutsch–Jozsa.
- Mechanism: the oracle prepares \(H^{\otimes n}|a\rangle\); the final \(H^{\otimes n}\) inverts it and returns \(|a\rangle\) exactly.
- Key tool: the character sum \(\sum_x(-1)^{z\cdot x} = 2^n\,\delta_{z,0}\) — perfect constructive interference at \(y=a\), perfect cancellation elsewhere.
- Oracle = one CNOT per 1-bit of \(a\). An affine offset \(b\) appears only as an unobservable global phase.
- Holevo's bound is not violated: \(n\) qubits carry \(n\) bits; the win is one operation instead of \(n\).
Next lesson: L15 — Simon's algorithm (the first exponential separation against randomised classical algorithms).
Practise now: unit2-algorithms-lab.html → Bernstein–Vazirani tab: type any hidden string up
to 8 bits, see the auto-generated oracle, and watch the single spike appear at \(y = a\).