Bernstein-Vazirani algorithm explained
The Bernstein-Vazirani algorithm was introduced by Ethan Bernstein and Umesh Vazirani in 1992. It recovers a hidden n-bit string with a single oracle query, where a classical algorithm needs n queries. It is one of the simplest examples of a quantum speedup in query complexity, and its building blocks (Hadamard transforms, phase kickback, interference) also appear in larger algorithms such as Shor’s.
I built BVVIZ to run the algorithm on simulated noisy hardware and look at what the measurements actually return.
the problem
The algorithm solves a specific promise problem. A black-box oracle \(f_s\) takes an n-bit string \(x\) and returns one bit. It is guaranteed to compute the bitwise dot product of \(x\) with a secret string \(s\), modulo 2.
\[ f_s(\{ x_0, x_1, ..., x_{(n-1)} \}) = x \cdot s \]\[ x \cdot s = (x_0 s_0 \oplus x_1 s_1 \oplus ... \oplus x_{n-1} s_{n-1}) \pmod{2} \]The goal is to find \(s\) with as few oracle queries as possible.
classical vs quantum
classical approach
Each classical query returns a single bit, so finding \(s\) takes at least \(n\) queries. The standard strategy, which BVVIZ also runs for comparison, queries one bit at a time: an input with only the i-th bit set, like 00100..., returns \(s_i\). That is \(n\) queries, or \(\mathcal{O}(n)\).
quantum approach
The quantum algorithm finds \(s\) with a single oracle query, and on ideal hardware it does so with certainty. That is \(\mathcal{O}(1)\) queries.
The steps are:
Start with \(n\) qubits in \(|0\rangle\) and one auxiliary qubit in \(|1\rangle\).
Apply a Hadamard gate to all \(n+1\) qubits. The first \(n\) qubits go into an equal superposition over all \(2^n\) basis states, and the auxiliary qubit ends up in \(| - \rangle\).
\[ |\psi_1\rangle = H^{\otimes n} |0\rangle^{\otimes n} \otimes H|1\rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in \\{0,1\\}^n} |x\rangle \otimes |-\rangle \]Apply the oracle \(U_f\). Because the auxiliary qubit is in \(|-\rangle\), phase kickback writes \(f_s(x) = s \cdot x\) into the relative phase of each \(|x\rangle\).
\[ |\psi_2\rangle = U_f |\psi_1\rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in \\{0,1\\}^n} (-1)^{s \cdot x} |x\rangle \otimes |-\rangle \]Apply Hadamard gates to the first \(n\) qubits again. The phases interfere so that all of the amplitude ends up on \(|s\rangle\).
\[ |\psi_3\rangle = H^{\otimes n} \left( \frac{1}{\sqrt{2^n}} \sum_{x \in \\{0,1\\}^n} (-1)^{s \cdot x} |x\rangle \right) = |s\rangle \]Measure the first \(n\) qubits in the computational basis. The result is \(s\).
simulating hardware noise with BVVIZ
The analysis above assumes ideal gates. On current NISQ hardware, gate errors, decoherence, and readout errors all lower the probability of measuring \(s\). BVVIZ lets you choose the backend, the number of shots, and the noise model, and shows how the results change.
With noise, a single run no longer returns \(s\) with certainty. Repeating the circuit over many shots gives a distribution over output strings, shown in the counts chart.
As the error rates increase, more of the probability mass moves to incorrect strings, and more shots are needed to identify \(s\) reliably.
The app runs in the browser at bernstein-vazirani.streamlit.app, and the code is at github.com/chutommy/bvviz.
