The Bernstein-Vazirani algorithm is a quantum algorithm developed by Ethan Bernstein and Umesh Vazirani in 1992. It is used to identify a hidden string and demonstrates a clear computational advantage over the best-known classical methods. Its principles are foundational and appear in more complex algorithms, such as Shor’s algorithm for factoring.

To help explore this algorithm interactively, BVVIZ is a tool that provides a user-friendly playground for running noisy quantum simulations and visualizing the results.

The Problem Definition

The algorithm solves a specific promise problem. It involves a “black-box” function, or oracle, denoted as \(f_s\). This function takes an n-bit binary string, \(x\), as input and returns a single bit as output. The function is guaranteed to compute the bitwise dot product of the input \(x\) with a predetermined, secret n-bit 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 objective is to determine the secret string \(s\) with the minimum number of queries to the function \(f_s\).

Solutions: Classical vs. Quantum

Classical Approach

To solve this problem classically, one must query the oracle multiple times. The most efficient classical strategy, also implemented in BVVIZ for comparison, requires n queries. To find the i-th bit of the secret string \(s_i\), one must input a string \(x\) where only the i-th bit is 1 (e.g., 00100... to find \(s_2\)). This isolates each bit of \(s\) one at a time. Therefore, the time complexity is linear, or \(\mathcal{O}( n )\).

Quantum Approach

The quantum algorithm, in contrast, can determine the secret string \(s\) with absolute certainty in a single query to the oracle. This results in a constant time complexity of \(\mathcal{O}( 1 )\).

image source: Qiskit
The reversible circuit of the Bernstein-Vazirani oracle

image source: Qiskit

The algorithm achieves this through the following steps:

  1. Initialization: Start with n qubits in the \(|0\rangle\) state and one auxiliary qubit in the \(|1\rangle\) state.

  2. Superposition: Apply a Hadamard gate (\(H\)) to all n+1 qubits. This puts the first n qubits into an equal superposition of all possible states and prepares the auxiliary qubit in the \(|-\rangle\) state.

    \[ |\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 \]

  3. Oracle Query: Apply the quantum oracle, \(U_f\). Using phase kickback, the state is transformed based on \(f_s(x) = s \cdot x\). The information about \(s\) is encoded 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 \]

  4. Final Transformation: Apply a Hadamard gate to the first n qubits again. This transformation makes the states interfere in such a way that the final state is precisely 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 \]

  5. Measurement: Measuring the first n qubits in the computational basis yields the secret string \(s\).

The quantum circuit for a secret string ‘101’ as implemented in BVVIZ

The quantum circuit for a secret string ‘101’ as implemented in BVVIZ

Visualizing The Impact of Hardware Noise with BVVIZ

While the theoretical performance of the quantum algorithm is perfect, BVVIZ demonstrates how performance on current Noisy Intermediate-Scale Quantum (NISQ) hardware is degraded by factors like gate errors, qubit decoherence, and readout errors.

The tool gives you full control over the simulated quantum hardware, allowing you to customize the backend system, number of shots, and even the noise model to see these effects firsthand.

BVVIZ visualizes the quantum register mapping, here showing a preconfigured Brooklyn system with sabre layout and stochastic routing.

BVVIZ visualizes the quantum register mapping, here showing a preconfigured Brooklyn system with sabre layout and stochastic routing.

When running the algorithm under noisy conditions, the final measurement may not yield the correct secret string with 100% probability. Instead, multiple runs (shots) produce a distribution of results. The count chart in BVVIZ makes this clear.

A results chart from a BVVIZ experiment with secret string 11001 and 1000 shots.

A results chart from a BVVIZ experiment with secret string 11001 and 1000 shots.

As you increase the noise in the simulation, you will see the probability of measuring incorrect strings rise, diminishing the algorithm’s advantage. This highlights the primary challenge in quantum computing: building fault-tolerant hardware.

BVVIZ provides detailed metrics, showing the impact of a very noisy device on an experiment’s accuracy.

BVVIZ provides detailed metrics, showing the impact of a very noisy device on an experiment’s accuracy.

Conclusion

The Bernstein-Vazirani algorithm is a textbook example of quantum advantage in query complexity. However, its practical implementation is sensitive to hardware noise, a key obstacle that must be overcome for building large-scale quantum computers. Tools like BVVIZ help bridge the gap between theory and practice, offering a clear window into the challenges and potential of today’s quantum technology.

source: bvviz streamlit app

source: bvviz streamlit app

Try It Yourself

I encourage you to experiment with the algorithm yourself.