The Bernstein-Vazirani Algorithm: One Query, Whole Answer

The Bernstein-Vazirani algorithm recovers an n-bit hidden string from a single oracle query, where any classical algorithm requires n. It is among the cleanest provable separations between quantum and classical query complexity, and because the circuit is entirely Clifford it can be run exactly at any width. This article derives why it works, gives the circuit, and reports a certified run.

The problem

An oracle holds a hidden n-bit string s. Given an input x, it returns the inner product of x and s modulo 2, that is, the parity of the bits where x and s are both 1. The task is to determine s.

Classically the query complexity is exactly n. Querying x = 100...0 returns s_1, querying x = 010...0 returns s_2, and so on; each query returns one bit of information about s, and n bits are required, so n queries are necessary and sufficient.

Bernstein and Vazirani showed in 1992 that a quantum algorithm needs one. The separation is exact and provable rather than asymptotic or heuristic.

Phase kickback, which is the actual mechanism

The algorithm is usually described as querying all inputs at once in superposition. That description is misleading, because superposition alone gives nothing. Measuring a uniform superposition returns one random input, exactly as a single classical query would. The mechanism is interference, and it depends on a specific trick worth understanding on its own because it recurs throughout quantum algorithms.

Prepare an ancilla qubit in the state |-> = (|0> - |1>)/sqrt(2). Now consider what a CNOT targeting that ancilla does. Applying X to |-> yields -|->, since X swaps the two components and the minus sign moves to the front. So a controlled-X on the ancilla leaves the ancilla unchanged and multiplies the *control* branch by -1 when the control is |1>.

The effect intended for the target has appeared as a phase on the control. This is phase kickback, and it is how an oracle's answer is written into the input register rather than into the output qubit.

With the input register in a uniform superposition, the oracle therefore maps each basis state |x> to (-1)^(x.s) |x>. Every branch acquires a sign determined by its inner product with the secret. No measurement has occurred and no information has been read yet; the entire secret is now encoded in the sign pattern across 2^n amplitudes.

Why the second Hadamard layer returns the answer

The final step is a Hadamard on every input qubit. The n-qubit Hadamard transform maps a state with amplitude pattern (-1)^(x.s) to the single basis state |s>, exactly and with certainty.

The reason is that the Hadamard transform is its own inverse and maps |s> to the uniform superposition with signs (-1)^(x.s). The oracle has produced precisely that state, so applying the transform again returns |s>. The measurement is deterministic: the algorithm succeeds with probability 1, not with high probability.

This is the general shape of quantum algorithms that achieve genuine speedup. Spread into superposition, arrange for the problem structure to write itself into relative phases, then interfere so that the amplitudes for wrong answers cancel and the amplitude for the right answer adds. Grover's algorithm is the same pattern applied iteratively.

The circuit

The oracle for a given s is a CNOT from each input qubit where s has a 1, targeting the ancilla. The template hides s = 1011.

OPENQASM 2.0;
include "qelib1.inc";
qreg q[5];
creg c[4];
x q[4];
h q[4];                 // ancilla in the |-> state
h q[0]; h q[1]; h q[2]; h q[3];
cx q[0],q[4];           // oracle for s = 1011
cx q[1],q[4];
cx q[3],q[4];
h q[0]; h q[1]; h q[2]; h q[3];
measure q[0] -> c[0];
measure q[1] -> c[1];
measure q[2] -> c[2];
measure q[3] -> c[3];

The four input qubits carry Hadamards on both sides. The fifth is the ancilla, prepared with an X followed by a Hadamard to place it in |->. The emerald CNOTs in the middle are the oracle: one for each 1 in the secret, and their pattern is what the algorithm reads back.

A certified run

The circuit was submitted at 1,000 shots. Every gate is Clifford, so it ran on the exact stabilizer engine.

counts:     {"1011": 1000}
error_info: {"method": "stabilizer (Gottesman-Knill)",
             "truncation_error": 0.0,
             "shot_noise_only": true, "shots": 1000}

What the separation does and does not show

The result should be stated carefully, because it is frequently overclaimed.

The separation is in *query* complexity, counting calls to the oracle. It is exact, provable and unconditional, which is rare.

But the oracle is a black box supplied by the problem, and in any concrete instance someone must build it. If the circuit implementing the oracle is known, the secret can be read off its structure without running anything, since the CNOT pattern is the secret.

Bernstein-Vazirani is therefore a demonstration of mechanism rather than a useful algorithm. Its value is that it isolates phase kickback and interference in the simplest possible setting, and those are the components that do the work in algorithms which are useful.

Deutsch-Jozsa, the sibling result

The Deutsch-Jozsa algorithm uses the identical structure to decide whether a black-box function is constant or balanced in a single query. A classical deterministic algorithm requires 2^(n-1) + 1 queries in the worst case, giving an exponential separation, though a randomised classical algorithm answers correctly with high probability in a constant number of queries, which narrows the practical significance considerably.

Both algorithms were among the first to establish on paper that quantum computers can do things classical ones cannot, and both are built from the same three steps: spread into superposition, let the oracle write phases, interfere and read.

Running it

Select Bernstein-Vazirani in the console and run it. Modify the oracle CNOTs to encode a different secret and confirm the output follows. Add input qubits to lengthen the string and confirm the query count stays at one while the classical requirement grows linearly.

The interference pattern here is the same one Grover's algorithm applies repeatedly rather than once; that construction is in the Grover tutorial. The entanglement these circuits rely on is built in the GHZ walkthrough.