21. Bernstein–Vazirani

21.1Hidden strings

Bernstein and Vazirani (1993) hid a string instead of a predicate: f(x) = a·x ⊕ b = (a₁x₁ ⊕ … ⊕ aₙxₙ) ⊕ b, and the task is to recover the hidden string a. The constant b is folded into the oracle and, as we will see, made irrelevant by the ancilla convention. The result matters historically because it was the first separation against bounded-error classical algorithms — BQP versus BPP in the oracle world — closing the randomized loophole left open by Deutsch–Jozsa. It is also the first algorithm whose output is a string rather than a one-bit verdict.

21.2Oracle construction

Uf: |x⟩|y⟩ ↦ |x⟩|y ⊕ a·x ⊕ b⟩ is buildable from classical reversible gates: for each i with aᵢ = 1, a CNOT from input qubit i into the ancilla computes the parity, plus one X on the ancilla if b = 1. Now run the ancilla in |−⟩. Each CNOT then contributes a phase: CNOT_{i→a}|x⟩|−⟩ = (−1)^{aᵢxᵢ}|x⟩|−⟩ — phase kickback again — so the whole oracle acts as (−1)^{a·x ⊕ b} = (−1)^b·(−1)^{a·x} on the input register. The global factor (−1)^b is unobservable; b has been erased by the ancilla convention, and only the phase pattern of a remains.

21.3Quantum solution

q0 … q(n-1):  |0> ─H─●─H─M     readout = a, with certainty
                 │
q_n:          |1> ─H─Uf──      Uf: |x>|y> ↦ |x>|y ⊕ (a·x ⊕ b)>

The circuit is identical to Deutsch–Jozsa — only the promised structure of f changed. After the oracle the input register holds (1/√2ⁿ)·Σ_x (−1)^{a·x}|x⟩. Applying H^{⊗n} (which maps |x⟩ → (1/√2ⁿ)·Σ_y (−1)^{x·y}|y⟩) gives the amplitude of basis state y: (1/2ⁿ)·Σ_x (−1)^{x·(a⊕y)} — a sum of ±1 over 2ⁿ terms that equals 1 if y = a and 0 otherwise, by the same cancellation as 20.4. Measurement returns a exactly, every run, no shots needed.

21.4Classical comparison

Each classical query returns one linear equation a·x = c in unknown bits a₁…aₙ; n linearly independent queries are needed before a is pinned down — an information-theoretic lower bound, not an artifact of algorithm design. The quantum algorithm extracts all n bits in a single query. The honest explanation is not "it queried all 2ⁿ inputs in parallel": it queried once, but on a superposition, and the oracle's action on all inputs simultaneously is what lets one global measurement reveal the linear functional. This was the first BQP-versus-BPP oracle separation, and it convinced the field that randomized classical lower bounds would not dissolve quantum advantage.

21.5Implementation

import numpy as np
n, a, b = 4, 0b1011, 1
N = 2 ** n
H1 = np.array([[1, 1], [1, -1]]) / np.sqrt(2)
Hn = H1
for _ in range(n - 1):
    Hn = np.kron(Hn, H1)                       # Walsh–Hadamard on n qubits
f = np.array([(bin(x & a).count("1") + b) % 2 for x in range(N)])
psi = np.ones(N, dtype=complex) / np.sqrt(N)   # H on all inputs
psi *= (-1.0) ** f                             # oracle as phase (ancilla |->)
psi = Hn @ psi                                 # final Hadamards
y = int(np.argmax(np.abs(psi)))
print(f"recovered a = {y:04b}   expected a = {a:04b}   exact: {y == a}")

Note the shortcut: with the ancilla tracked analytically as |−⟩, the oracle is the diagonal phase (−1)^{f(x)} — no 2n-dimensional simulation needed. Hn built from kroneckered 2×2 blocks is the Walsh–Hadamard transform, not the FFT; for f(x) = a·x over the bitwise inner product they differ.