The Bernstein-Vazirani Algorithm: One Query, Whole Answer

Here is a puzzle a quantum computer solves in one move. A black box hides a secret bitstring. You are allowed to ask it questions, and each answer depends on the secret. How many questions do you need to recover the whole secret? Classically, one per bit. With the Bernstein-Vazirani algorithm, exactly one, no matter how long the string. It is a clean, provable quantum advantage, and a one-click template in the ZKSF console.

The problem: guess the hidden string

The black box, or oracle, hides a secret bitstring s. Ask it about an input and it replies with the bitwise agreement between your input and s, folded down to a single bit. A classical computer learns one bit of s per query: ask about 1000...0 to read the first bit, 0100...0 for the second, and so on. For an n-bit secret it needs n queries. Bernstein-Vazirani needs one, because it does not ask about the bits one at a time. It queries every input at once, in superposition, and reads the whole string off the interference pattern.

The circuit: interfere, then read

The recipe is short. Put the input register into superposition with Hadamards so it holds every possible query at once. Prepare a single ancilla qubit in a state that turns the oracle's answer into a phase. Call the oracle, which here is a set of CNOTs from exactly the qubits where the secret bit is 1. A second layer of Hadamards then converts those phases back into a plain bitstring, and it is the secret. Our 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];

In the diagram the four input qubits get Hadamards on both sides. The fifth qubit is the ancilla, set up with an X and a Hadamard. The emerald CNOTs in the middle are the oracle: there is one for each 1 in the secret, and their pattern is what the algorithm reads back out.

Running it live: the whole string, in one shot

We ran the circuit on ZKSF at 1,000 shots. Every gate is Clifford, so it ran on the exact stabilizer engine. The result:

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

Every shot returned 1011, the hidden string, read from a single query to the oracle. A classical computer would have needed four separate queries to learn those four bits. The run carries a public ZCC-v0.1 certificate.

A close cousin: Deutsch-Jozsa

Bernstein-Vazirani is one of a pair. Its sibling, the Deutsch-Jozsa algorithm, uses the same interference trick to decide in one query whether a black-box function is constant or balanced, a question that can take a classical computer exponentially many tries in the worst case. Both were among the first algorithms to prove, on paper, that quantum computers can do things classical ones cannot, and both are built from exactly the pattern above: spread into superposition, let the oracle stamp phases, interfere, and read.

Try it yourself

Choose Bernstein-Vazirani in the console and run it. Then change the oracle CNOTs to encode a different secret, add input qubits to make the string longer, and confirm the algorithm still reads it in a single shot. For another one-query wonder, see Grover's search, and for the entanglement these algorithms lean on, the GHZ walkthrough.