Bernstein-Vazirani Algorithm

With a single oracle query, recover a hidden n-bit string s from a black-box function f(x)=s·x — where any classical deterministic query algorithm needs n queries in the worst case; even a randomized algorithm with high success probability still needs Ω(n) queries.

The problem it solves

Someone has fixed a hidden bit-string s and handed you an oracle that computes the mod-2 inner product of s with your input x:

f(x) = s·x = (s0x0 ⊕ s1x1 ⊕ … ⊕ sn−1xn−1)

Your job is to determine s. Classically, each query returns just one parity bit, so you are forced to probe one position at a time: use x = 100…0 to read s₀, x = 010…0 to read s₁, and so on. For a classical deterministic algorithm, getting all n bits takes n queries.

From O(n) to O(1): however long s is, the quantum algorithm asks just once.

Intuition — reading every bit in one question

The classical limitation is that each input "flattens" the entire hidden string into a single parity bit, discarding the detail. Bernstein–Vazirani instead feeds all 2ⁿ inputs through the oracle in a uniform superposition at once, letting the oracle write every bit of s simultaneously into the phase structure of the state; a layer of Hadamards then "decodes" those phases back to the computational basis, so that s appears directly as the measurement result.

Why it works — the Hadamard sandwich and phase kickback

As in Deutsch, first prepare the auxiliary qubit in |−⟩. Then the oracle |x⟩|y⟩ → |x⟩|y⊕f(x)⟩ reduces to a pure phase acting on the data register:

|x⟩ → (−1)s·x |x⟩

Applying the oracle to the uniform superposition (1/√2n) Σx |x⟩ tags every basis state |x⟩ with the phase (−1)s·x. The key identity is that under an n-qubit Hadamard,

H⊗n (1/√2n) Σx (−1)s·x |x⟩ = |s⟩

In other words, a uniform superposition phased by (−1)s·x, run through a Hadamard transform, undergoes constructive interference toward |s⟩ and destructive interference that erases everything else. So the closing Hadamard sandwich turns the phase-encoded hidden string exactly back into the computational basis state |s⟩, and one measurement reads out all n bits.

The mechanism

What it shows — and what it doesn't

• A deterministic, exponential query advantage. The n→1 speedup is deterministic and holds every run — but the advantage is in query complexity, not the speed of general computation.
• It is a close cousin of Deutsch–Jozsa. The same Hadamard-sandwich-plus-kickback skeleton is used here to read out an entire string at once, rather than to decide a single global bit.
• The oracle must genuinely encode s. It is the oracle's internal structure (which positions are controlled) that carries the answer; the algorithm only extracts it efficiently — it cannot guess from nothing.
• It is a stepping stone to deeper algorithms. The same interference-based decoding idea is pushed to far more powerful forms in the period-finding of Simon's and Shor's algorithms.

The algorithm, step by step

1. Prepare the auxiliary qubit in |−⟩ (x then h).
2. Apply h to the n data qubits, making a uniform superposition of all inputs.
3. Call the oracle; via phase kickback, each basis state acquires the phase (−1)s·x.
4. Apply h to the data register again; interference converges onto |s⟩.
5. Measure the data register and read off s directly.

Seeing it in code

Read it against the theory above: x(aux); h(aux) prepares the auxiliary in |−⟩; the first h(q) makes the n-qubit uniform superposition; the for loop is the oracle — it places an x.ctrl(q[i], aux) only on the positions where secret[i] == 1, writing the inner product s·x into the phase by kickback; the closing h(q) completes the decoding, and mz(q) hands back the hidden string. In the example secret = [1,0,1,1], so the counts peak at "1011".

If a backend displays bit strings with a different endianness, the output string may appear reversed; it still corresponds to the same hidden string. This page interprets outputs in q[0], q[1], … order.

import qalgora

@qalgora.kernel
def bv(secret: list[int]):
    n = len(secret)
    q = qalgora.qvector(n)
    aux = qalgora.qubit()
    x(aux); h(aux)
    h(q)
    for i in range(n):           # oracle encodes the secret string
        if secret[i] == 1:
            x.ctrl(q[i], aux)
    h(q)
    mz(q)

print(qalgora.sample(bv, [1, 0, 1, 1]))   # peaks at "1011"

References

• E. Bernstein and U. Vazirani, "Quantum complexity theory," SIAM J. Comput. 26(5), 1411-1473 (1997). doi:10.1137/S0097539796300921