Bernstein–Vazirani: read a hidden string

Same circuit shape, more useful result: recover an n-bit secret with one query.

You will learn to

Build the oracle for a given secret s.
Explain why the output register reads s exactly.

f_{s} (x) = s \cdot x mod 2, H^{\otimes n} (\frac{1}{2 ^{n}} x \sum (- 1)^{s \cdot x} ∣ x ⟩) = ∣ s ⟩

The oracle is one CNOT from each input bit where s has a 1 onto the target. After the final Hadamards the register is exactly |s⟩, deterministically.

Try it

Secret s = 101

Simulate: every shot reads 101. Change which CNOTs are present to encode another secret and watch the histogram follow.

OPENQASM 3.0;
include "stdgates.inc";
qubit[4] q;
bit[3] c;
x q[3];
h q[0];
h q[1];
h q[2];
h q[3];
barrier q;
cx q[0], q[3];
cx q[2], q[3];
barrier q;
h q[0];
h q[1];
h q[2];
c[0] = measure q[0];
c[1] = measure q[1];
c[2] = measure q[2];

Open in the IDE Open in the Playground

Classically you need n queries (one per bit: query with x = 0…010…0). Quantumly one. Unlike Deutsch–Jozsa the gap holds even against randomised classical algorithms, which is why Bernstein–Vazirani is the first 'real' separation in the oracle model.

Quiz 1 · 10 XP

With secret s = 011 (s0 = 1, s1 = 1, s2 = 0), which CNOTs form the oracle?

Key takeaway

Bernstein–Vazirani turns the Deutsch–Jozsa template into a deterministic n-to-1 query advantage: the Hadamard transform of the kicked-back phases is the secret itself.

Up next: Grover's search

OPENQASM 3.0; include "stdgates.inc"; qubit[4] q; bit[3] c; x q[3]; h q[0]; h q[1]; h q[2]; h q[3]; barrier q; cx q[0], q[3]; cx q[2], q[3]; barrier q; h q[0]; h q[1]; h q[2]; c[0] = measure q[0]; c[1] = measure q[1]; c[2] = measure q[2];