Bernstein-Vazirani Algorithm

Overview

The Bernstein-Vazirani algorithm finds a hidden n-bit string s using a single quantum query. The hidden string defines a function f of x equal to the dot product of s and x modulo 2, which is the parity of the bits of x selected by s. A classical computer needs n queries to learn s, one for each bit, while a quantum computer finds all n bits at once.

It is a simple algorithm, closely related to Deutsch-Jozsa, and it is one of the best teaching examples of how interference extracts global information. Beyond teaching, its recursive form gave the first evidence of a super-polynomial separation between quantum and classical bounded-error computation.

The problem it solves

Given a 'black box' function that computes the dot product of the input with a hidden secret string, determine the secret string.

History and background

Ethan Bernstein and Umesh Vazirani introduced the algorithm in their paper Quantum Complexity Theory, presented at the ACM Symposium on Theory of Computing in 1993 and published in the SIAM Journal on Computing in 1997. The paper had two parts: the linear-speedup parity problem used here, and a recursive version, recursive Fourier sampling, which requires super-polynomially many classical queries.

Because the circuit is short and its answer can be checked, Bernstein-Vazirani became a standard test for quantum hardware. It has been run on NMR devices, trapped ions, and superconducting qubits, and researchers have used it to compare noise levels, since success requires every qubit's gates to be accurate.

How it works

Prepares all inputs in superposition, queries the function once, and uses interference so that measuring the resulting state directly reveals the hidden string in a single shot.

The Hadamard transform converts between two views of a function on bit strings. In the computational view, the function is evaluated at each input. In the Hadamard view, the function is represented by its Fourier coefficients. For a parity function, the Fourier transform is extremely simple: all the weight is concentrated on a single string, the hidden s.

The algorithm creates an equal superposition of all inputs, queries the oracle in a way that writes the function values into the phases, and applies Hadamard gates. The phases form a pattern that is precisely the Fourier transform of the parity function, so the Hadamard layer converts the phase pattern into the basis state s, and a measurement reveals it.

A classical algorithm cannot do this because each query returns a single bit, so it must query n times to pin down n unknown bits. The quantum oracle is queried once on a superposition, and the output encodes all n bits in the interference pattern.

Step by step

1. Prepare n input qubits in the zero state and one ancilla qubit in the state 1.
2. Apply Hadamard gates to every qubit, which creates a superposition of all inputs and puts the ancilla in the minus state.
3. Apply the oracle that maps x and y to x and y XOR s dot x, which in the presence of the ancilla puts a phase of minus 1 to the s dot x on each input x.
4. Apply Hadamard gates to the n input qubits.
5. Measure the n input qubits. The result is the hidden string s with probability 1.

A worked example

Let n = 3 and the hidden string be s = 101, so f of x is x1 XOR x3. Classically, you would query f at 100, 010, and 001 and read off the bits of s from the three answers: 1, 0, and 1. That requires three queries.

On a quantum computer, the circuit prepares the superposition, applies the oracle once, and applies the final Hadamards. The state after the oracle has phase minus 1 on inputs 001, 011, 100, 110, because f is 1 there, and the final Hadamard transform turns this phase pattern into the single state 101. Measuring gives 101 with certainty after a single query.

Complexity and resources

What hardware it needs

• A few qubits and a very short circuit, so it runs on any current device for small n.
• The oracle is a set of CNOT gates from the input qubits where s has a 1 to the ancilla, so its cost is low.

Applications

• A first example of a quantum advantage in the query model with a clear, verifiable answer.
• A hardware benchmark that checks correct operation of many qubits and gates.
• The starting point for recursive Fourier sampling, which separates BQP from classical bounded-error computation relative to an oracle.

Limitations and caveats

• The advantage is only linear in the query model, and the problem is artificial.
• The oracle's cost is not counted, and for a hidden string known in advance, the oracle already contains the answer.
• Noise makes large instances fail on current hardware.

Common misconceptions

• It does not give an exponential speedup. The classical algorithm needs only n queries, which is already efficient.
• It does not extract information without measurement. The speedup comes from interference in the query, and the result is read out by measuring.

How it compares

• Deutsch-Jozsa uses the same circuit but decides whether a function is constant or balanced.
• Simon's algorithm needs repeated runs and classical post-processing, and offers an exponential gap.
• Grover's algorithm is probabilistic and iterative, while Bernstein-Vazirani is exact with one query.

Real-world impact

Mainly an educational stepping-stone algorithm, often taught right after Deutsch-Jozsa, used to build intuition for how quantum parallelism extracts global information about a function efficiently.

Why it matters

The algorithm demonstrates, in the simplest possible setting, that interference lets a quantum computer extract a whole string of information from a single oracle call. It is the cleanest entry point to the Fourier-sampling idea that powers Simon's and Shor's algorithms.

Its recursive version, recursive Fourier sampling, was the first evidence that quantum computers could beat classical probabilistic machines by more than a polynomial factor, which helped establish the case for quantum computing as a new computational model.

Frequently asked questions

Keep learning

• Related algorithm: Deutsch-Jozsa Algorithm
• Related algorithm: Simon's Algorithm
• Related algorithm: Quantum Fourier Transform (QFT)

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database