bernstein-vazirani algorithm explained
the bernstein-vazirani algorithm is a quantum algorithm from Bernstein and Vazirani, back in 1992. it pulls out a hidden string in a single query where any classical approach needs one query per bit. it’s a clean little example of quantum speedup, and the same trick shows up inside bigger algorithms like Shor’s.
BVVIZ is a small playground i built for running the algorithm under noisy quantum hardware and seeing what actually comes back.
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
classically, you have to query the oracle once for each bit of \(s\). to learn the i-th bit, feed in a string with only the i-th bit set, like 00100.... that isolates one bit at a time, so the best classical strategy needs \(n\) queries and runs in \(\mathcal{O}(n)\).
quantum approach
the quantum version gets the whole string from a single oracle query, with certainty. that’s \(\mathcal{O}(1)\).
here is how it works.
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\) go into an equal superposition over all possible 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 quantum oracle \(U_f\). phase kickback encodes \(f_s(x) = s \cdot x\) as a relative phase on the input qubits.
\[ |\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 interference lines everything up so the final state is exactly the secret string \(s\).
\[ |\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\).
seeing the noise with BVVIZ
on paper the algorithm is perfect, one query and you’re done. in practice the noise wrecks it, which is pretty much the whole story of quantum hardware right now. BVVIZ just makes that easy to see for yourself.
you can pick the backend, number of shots, and noise model, then watch the success probability drop as the noise goes up.
under noisy conditions the measurement no longer returns the secret string with 100% probability. repeated shots give a distribution, and the count chart shows the wrong answers creeping in.
crank up the noise and the probability of measuring the wrong string rises. that’s the main challenge in quantum computing right now, building hardware that can actually tolerate the errors.
want to play with it? run it in your browser at bernstein-vazirani.streamlit.app, or grab the code at github.com/chutommy/bvviz.
