Bernstein–Vazirani: find the hidden string in one go

The algorithm that reads a bit string hidden inside a function in a single query instead of the n queries needed classically. See step by step how the oracle is built.

The problem

The function has the form f(x) = s·x (mod 2): the parity of the sum of the bitwise products of a hidden bit string s and the input. The goal is to find s. Classically you query inputs with a single 1 bit each time and learn the bits of s one by one; n bits need n queries.

Building the oracle

f(x) = s·x is built with one CNOT from each input qubit where s has a 1 to the helper qubit. In the playground s = 101: there is a CNOT from q0 and from q2 to q3, none from q1.

The circuit has the same skeleton as Deutsch–Jozsa: H on the inputs, X and H on the helper, the oracle, then H again. Phase kickback writes the phase (−1)^(s·x) onto the inputs, and the final H gates turn this phase pattern directly into s.

What did we learn?

All n bits, with certainty, in a single query. The speed-up is linear rather than exponential (1 versus n), but it is one of the cleanest examples of quantum parallelism and interference working together, and one of the first algorithms tried on real hardware.

Try it yourself

Remove the CNOT from q2 to q3: the hidden string becomes 001 and the inputs (q2 q1 q0) read 001 in one go; the result is 1001.

Open the circuit in your browser

The circuit playground is in Turkish. Button guide: “1000 kez ölç” = measure 1000 times, “Durum vektörünü göster” = show the state vector, “Bu devrenin Qiskit kodu” = this circuit’s Qiskit code, “Geri al” = undo, “Temizle” = clear. Click a gate in the circuit to remove it.

Key points

The f(x) = s·x (mod 2) oracle is built with one CNOT for each bit of s that is 1.
Phase kickback and the final H gates turn the phase pattern directly into s.
Classically n queries are needed; quantum needs one.

Test yourself

If the hidden string is s = 110, from which qubits are CNOTs drawn to the helper qubit?

q0 and q1
q1 and q2
Only q0

Show the answer

q1 and q2. In s = 110 the q2 and q1 bits are 1 and the q0 bit is 0, so CNOTs are drawn from q1 and q2.

← Deutsch–Jozsa: a certain answer in one query · Grover in depth: oracle and diffusion →