Bernstein-Vazirani Algorithm

Bernstein-Vazirani Algorithm

The Bernstein-Vazirani algorithm is a classic demonstration of quantum advantage for query (oracle) problems. Given black-box access to a function f(a) = a . s + b (mod 2), where s is a hidden bit string and b a hidden bias bit, the task is to determine the hidden string s. Any classical algorithm must query the oracle once per bit, requiring n queries to recover an n-bit string, because each classical query reveals at most one bit of information. The quantum algorithm recovers the entire string s in a single oracle query, regardless of its length. This Cirq example implements the non-recursive Bernstein-Vazirani circuit: it prepares the input register in a uniform superposition with Hadamard gates, applies the oracle (which imprints the hidden string as a relative phase), interferes the amplitudes with a second layer of Hadamards, and measures to read off s directly. The script constructs a random hidden string and bias, builds the corresponding oracle, simulates the circuit, and confirms that the measured output matches the planted string. It is a clean, minimal illustration of how quantum interference can extract global information about a function that classical querying can only learn one bit at a time.

Run it

pip install -r requirements.txt
python bernstein_vazirani.py

Source and license

Imported from examples/bernstein_vazirani.py in quantumlib/Cirq at v1.6.1, under the Apache License 2.0. Original authors: The Cirq Developers. The upstream LICENSE is included alongside this example.