Bernstein–Vazirani Algorithm

Bernstein–Vazirani recovers a hidden bit-string s from a single query to a linear oracle — a full n-bit answer where classical needs n queries.

Queries

1 vs n classical

Oracle

f(x)=s·x mod 2

Mechanism

phase kickback + interference

What it does

With the input in superposition and the oracle encoding s·x as a phase, a final Hadamard layer maps the state directly to |s⟩ — the hidden string appears in the measurement outcome in one shot.

Steps

• Superpose input; ancilla in |−⟩.
• Oracle imprints s·x as phase.
• Hadamard the input register.
• Measure — the result is exactly s.

Where it's used

A crisp demonstration that quantum interference can extract global structure in one query; a building block intuition for learning-from-oracle problems.

In code (Qiskit)

qc = QuantumCircuit(n+1,n)
qc.x(n); qc.h(range(n+1))
# oracle: CX from each i where s_i=1 to ancilla
qc.h(range(n)); qc.measure(range(n),range(n))