The Bernstein-Vazirani Algorithm

Imagine a game. Someone thinks of an n-bit string s — say s = 10110101 for n = 8 — and keeps it secret. They then hand you a black box. You can feed the black box any n-bit string x you like, and the box will return a single bit: the bitwise-AND of x with s, summed modulo 2.

So if you feed in x = 10000000, the box returns s_1 \cdot 1 + s_2 \cdot 0 + \ldots = s_1 — the first bit of the hidden string. Feed in x = 01000000, get s_2. Feed in x = 00100000, get s_3. After n = 8 queries, one per standard basis vector e_i, you have reconstructed s in full.

Classical: n queries to learn n bits. This feels inescapable — how could you possibly learn n independent bits from fewer than n one-bit answers? Each query returns one bit of information; you need n bits. Information theory seems to rule out anything better.

A quantum computer with access to the same oracle solves the puzzle in one query. One. The output register, after a single oracle call and a final round of Hadamards, is precisely |s\rangle — all n bits at once, read off directly from a computational-basis measurement. This is the Bernstein-Vazirani algorithm, published in 1993 as part of a broader paper on quantum Turing machines and complexity theory that also introduced the first non-relativised evidence for quantum advantage.

The speedup is only linear (1 versus n) — much smaller than Simon's exponential speedup or Shor's factoring speedup — so Bernstein-Vazirani is not, on its own, a world-changing algorithm. What it is, pedagogically, is the cleanest possible demonstration of the mechanism at the heart of every oracle-based quantum algorithm: phase kickback encodes a function into phases, and the Hadamard transform decodes those phases into a directly readable string. The Deutsch-Jozsa algorithm squeezes one bit out of the phase pattern (constant vs balanced); Bernstein-Vazirani squeezes all n.

The problem, stated carefully

You are given a function f: \{0,1\}^n \to \{0,1\} with the promise that there exists a hidden string s \in \{0,1\}^n such that, for every input x,

This kind of function is called a parity function or a linear Boolean function: the output is the parity (XOR) of the bits of x selected by the mask s. Your job is to learn s.

Why this family is special: linear Boolean functions are exactly the functions that can be written as s \cdot x \bmod 2 for some s. There are exactly 2^n of them — one per choice of s — and they form a very restrictive subset of the 2^{2^n} functions from \{0,1\}^n to \{0,1\}. The promise that f is linear is what makes both the classical n-query algorithm and the quantum 1-query algorithm possible; without the promise, no algorithm could hope to identify f in a number of queries polynomial in n.

Note that the Deutsch-Jozsa promise (constant or balanced) is compatible with many different functions; Bernstein-Vazirani's promise pins down f to one of exactly 2^n specific functions, each labelled by its own s. Learning s is equivalent to identifying the function completely.

The classical baseline — n queries, one per bit

Before the quantum algorithm, confirm the classical bound.

Claim. Any deterministic classical algorithm that learns s with certainty must query f at least n times.

Proof sketch. Think of each query as asking a linear equation over \mathbb{F}_2 (the field of two elements \{0,1\} with arithmetic mod 2). A query on input x returns the value of the linear form s \cdot x at x — equivalently, the value of one linear functional evaluated at the unknown vector s. To determine the unknown vector s \in \mathbb{F}_2^n uniquely, you need n linearly independent equations. Each query gives you at most one such equation. Therefore, you need at least n queries.

The matching upper bound is also n: query f at the n standard basis vectors e_1 = 10\ldots 0, e_2 = 010\ldots 0, ..., e_n = 0\ldots 01. You get f(e_i) = s \cdot e_i = s_i directly. After n such queries, you have learnt every bit of s.

Why randomisation doesn't help much: even a randomised classical algorithm needs \Omega(n) queries to succeed with constant probability. Intuitively, each query returns at most one bit of information, and s contains n bits; no amount of randomness can squeeze more than one bit out of a single query. This is a genuine information-theoretic lower bound. The linear quantum-vs-classical separation of 1 vs n is therefore real against both deterministic and randomised classical models, unlike Deutsch-Jozsa's separation which collapses against randomised classical.

The algorithm — same four lines as Deutsch-Jozsa

The quantum algorithm uses n input qubits and one target qubit. The oracle is the standard reversible encoding:

where x \in \{0,1\}^n, y \in \{0,1\}, and \oplus is XOR. This is exactly the oracle shape we used in Deutsch-Jozsa — Bernstein-Vazirani uses it with a different promise on f.

The algorithm:

1. Initialise the input register to |0\rangle^{\otimes n} and the target to |1\rangle.
2. Hadamard every qubit: apply H^{\otimes n} to the input and H to the target.
3. Query the oracle once: apply U_f.
4. Hadamard the input register again: apply H^{\otimes n}. (Leave the target alone.)
5. Measure the input register in the computational basis.

Decision rule. The measurement outcome is s. That is the answer, directly, no post-processing needed.

The circuit is identical to Deutsch-Jozsa; only the promise on f and the interpretation of the outcome have changed. This is the first sign that the Hadamard–oracle–Hadamard sandwich is a genuinely general-purpose template, not a trick tailored to one problem.

Why it works — the walk-through

Track the state through each step.

After step 1 — initialisation. The state is |0\rangle^{\otimes n}|1\rangle.

After step 2 — Hadamards everywhere. Hadamard on |0\rangle^{\otimes n} gives the equal superposition over all 2^n input strings:

and Hadamard on |1\rangle gives |-\rangle. Joint state:

After step 3 — oracle query. Phase kickback (see the phase-kickback chapter) tells you that U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle. Since f(x) = s \cdot x, the factor is (-1)^{s \cdot x}:

Why this is the crucial step: the hidden string s is now written, in its entirety, into the phase pattern of the input register. Every basis state |x\rangle carries a sign \pm 1 that depends on the parity of s \cdot x. If a measurement at this stage would reveal anything, you could just measure now — but it won't, because every |x\rangle has the same probability 1/2^n. The sign information is present but invisible to a direct measurement. The final Hadamard is what makes it visible.

After step 4 — Hadamards on the input register. The key identity is the n-qubit Hadamard transform:

This formula is proved in the Hadamard chapter: it is just the tensor product of the single-qubit identity H|a\rangle = (|0\rangle + (-1)^a|1\rangle)/\sqrt{2} expanded over all n qubits. Apply it to every term in the phase-encoded sum:

Combine the two inner products using the distributive property of \bmod 2 arithmetic: s \cdot x + x \cdot y = (s+y) \cdot x \pmod 2. Substitute:

Why splitting the exponents this way is the clean move: you want to group by y because y is what you will measure. Writing the combined exponent as (s+y) \cdot x turns the double sum over x,y into a sum whose inner structure depends cleanly on a single combined variable s+y \in \{0,1\}^n.

Now evaluate the inner sum \sum_{x} (-1)^{(s+y) \cdot x}. This is a well-known orthogonality identity for the group \mathbb{F}_2^n: for any fixed v \in \mathbb{F}_2^n,

Why this identity holds: if v = 0^n, then v \cdot x = 0 for every x and every term is (+1), summing to 2^n. If v \ne 0^n, then v has at least one 1-bit, say in position i. Pair up each x with its flipped-at-position-i partner x': they contribute (-1)^{v \cdot x} and (-1)^{v \cdot x'} = (-1)^{v \cdot x + v_i} = -(-1)^{v \cdot x}, cancelling. Every x has a unique partner in this pairing, so the whole sum cancels to 0.

Apply this to v = s + y: the sum is 2^n if s + y = 0^n (equivalently y = s, since we are working mod 2), and 0 otherwise. Therefore:

The input register is now exactly |s\rangle, with probability 1.

Step 5 — measurement. Measure in the computational basis. The outcome is s, with certainty. Read off the n bits, and you have the hidden string.

The worked examples

Common confusions

• "Bernstein-Vazirani is just Deutsch-Jozsa." Structurally, yes — the circuit is identical. But the problem is different. Deutsch-Jozsa has a two-valued promise (constant or balanced) and returns one bit of information. Bernstein-Vazirani has a 2^n-valued promise (one of 2^n parity functions) and returns n bits of information. The interpretation of the measurement outcome is entirely different: Deutsch-Jozsa asks "was the outcome |0^n\rangle?", Bernstein-Vazirani asks "what was the outcome?" The two algorithms reuse the same template for different purposes.

• "You can read the hidden string from a 1-query measurement, so it violates information theory." It does not. Each run of the algorithm gives you n bits of classical output — exactly n bits. The subtlety is that the oracle query is not a classical query: U_f acts on a superposition over all 2^n inputs and entangles the output with n different function values in parallel. The Hadamard then converts the resulting n-bit phase pattern into n bits of measurement outcome. No information-theoretic law is violated; you just have to count queries to the quantum oracle, not to the classical function.

• "Randomised classical can do better than n queries." It cannot, in the worst case. Even with randomness and a constant error probability, the expected number of queries is \Omega(n). A careful lower-bound argument shows that each classical query (deterministic or randomised) contributes at most O(1) bits of information about the n-bit string s; learning n bits requires \Omega(n) queries. The linear quantum separation is therefore real against randomised classical too.

• "The outcome can sometimes be wrong." On an idealised quantum computer, no — the outcome is s with probability exactly 1. On real hardware (NISQ devices with gate-error rates around 10^{-3}), errors accumulate across the \sim 2n Hadamard gates and the oracle's internal gate count; the outcome is close to s with high probability but not certain. Running the circuit a few times and taking the majority (or the most common outcome) is a practical fix. With fault-tolerant error correction, the idealised certainty is restored.

• "Bernstein-Vazirani needs the promise to be literally true." Yes. If f is not of the form s \cdot x — for example, if f is a nonlinear Boolean function — the algorithm will still return some outcome, but that outcome is not guaranteed to be any meaningful string. The promise is a hypothesis on the input; the guarantee that "outcome = s" depends on it.

• "Bernstein-Vazirani is useful for breaking cryptography." Not directly — no real-world cryptographic system hides a secret string in a parity oracle. What Bernstein-Vazirani does contribute is a conceptual milestone: it demonstrated, in 1993, that quantum algorithms can extract structural information (the full hidden string) in a single query where classical algorithms need many. This was part of the theoretical scaffolding that led to Simon's algorithm (1994, exponential speedup for a harder hidden-structure problem) and Shor's algorithm (1994, exponential speedup for factoring — which does break RSA).

Going deeper

The Hadamard-transform identity, derived cleanly

The identity that decodes the phase pattern into |s\rangle is a special case of the Fourier transform over the group \mathbb{F}_2^n = (\mathbb{Z}/2\mathbb{Z})^n — the group of n-bit strings under XOR. Here is the derivation from scratch.

Claim. For any a \in \{0,1\}^n,

Proof. Apply H^{\otimes n} term by term using H^{\otimes n}|x\rangle = (1/\sqrt{2^n})\sum_y (-1)^{x \cdot y}|y\rangle:

The inner sum is 2^n if a + y = 0^n (i.e. y = a) and 0 otherwise, by the orthogonality-of-characters identity proved in the walk-through above. So the only surviving term has y = a with coefficient \tfrac{1}{2^n} \cdot 2^n = 1, giving |a\rangle. \blacksquare

The Hadamard transform is therefore a self-inverse (it is its own inverse) linear map on \mathbb{F}_2^n's complex vector space that takes the "character" (-1)^{a \cdot x} to the basis state |a\rangle, for every a. This is exactly the Fourier transform over the abelian group \mathbb{F}_2^n. Bernstein-Vazirani is, structurally, a Fourier-sampling algorithm: the oracle plants a character into the state, and the Fourier transform converts that character into the basis state that labels it.

The Fourier-transform perspective — why this generalises

The identity H^{\otimes n}[\sum_x (-1)^{a \cdot x}|x\rangle] = \sqrt{2^n}|a\rangle is the \mathbb{F}_2^n instance of a much more general fact. For any finite abelian group G:

• The characters of G are homomorphisms \chi: G \to \mathbb{C}^* (the multiplicative group of nonzero complex numbers). They form a group isomorphic to G.
• The quantum Fourier transform \mathrm{QFT}_G acts on the Hilbert space \mathbb{C}^{|G|} and takes |g\rangle to \tfrac{1}{\sqrt{|G|}}\sum_\chi \chi(g) |\chi\rangle.
• Its inverse takes a character-sum superposition \tfrac{1}{\sqrt{|G|}}\sum_g \chi(g)|g\rangle to the basis state |\chi\rangle.

For G = \mathbb{F}_2^n, the characters are \chi_a(x) = (-1)^{a \cdot x}, and the QFT equals H^{\otimes n}. For G = \mathbb{Z}/N\mathbb{Z} (integers mod N), the characters are \chi_k(x) = e^{2\pi i k x / N} and the QFT is the standard discrete Fourier transform, which is exactly the transform Shor's algorithm uses.

Bernstein-Vazirani, Deutsch-Jozsa, Simon, and Shor are all instances of the same template: plant a character into the state using an oracle; use the QFT to extract the character's label as a basis state. The Hilbert space, the group, and the character family change, but the mechanism is unified. This framing is called the hidden-subgroup problem (HSP), which you can read about in its own article.

Recursive Bernstein-Vazirani and the polynomial-hierarchy connection

In their 1993 paper, Bernstein and Vazirani went further than just the linear algorithm. They defined a recursive version of the problem — Recursive Fourier Sampling — where the oracle f is itself computed by solving a nested Bernstein-Vazirani problem with its own hidden string, and so on, to any depth k. The quantum algorithm solves depth-k Recursive Fourier Sampling in O(n) queries per level (total O(n \cdot k)), while any classical algorithm requires n^{\Omega(k)} queries. For k = \Theta(\log n), this is a superpolynomial (quasi-polynomial vs polynomial) separation, not just linear.

This was historically important: it was the first example of an oracle on which quantum algorithms achieve a superpolynomial speedup over classical randomised algorithms. The flat (non-recursive) Bernstein-Vazirani gives only a linear speedup; the recursive version is what established quantum computing's superpolynomial potential before Shor's algorithm. Shor's algorithm, which came a year later, delivered a superpolynomial speedup for an actually-useful problem (factoring).

Query complexity lower bounds — the classical side in detail

The formal lower bound that classical algorithms (deterministic or randomised, zero-error or bounded-error) need \Omega(n) queries to solve Bernstein-Vazirani uses an information-theoretic argument.

Setup. The hidden s is uniformly random over \{0,1\}^n — n bits of information. A classical algorithm observes query outcomes b_1 = s \cdot x_1, b_2 = s \cdot x_2, \ldots, b_q = s \cdot x_q, each a single bit. By Shannon's source-coding theorem, to determine s with probability at least 2/3, the total information content of the observations must be \Omega(n) bits. Each query contributes at most 1 bit, so q = \Omega(n).

This argument is tight: it shows both deterministic and randomised classical algorithms are stuck at \Theta(n) queries. The quantum 1-query algorithm beats this by a factor of n because one quantum query accesses the function on a superposition over all 2^n inputs simultaneously, and then Hadamard interference compresses the resulting phase pattern into n bits of measurable output — with correlations that a classical single-input-single-output query cannot produce.

Indian context — Umesh Vazirani and the Berkeley school

Umesh Vazirani is one of the two namesakes of this algorithm. Born in India and educated at the Bombay International School before moving abroad, he did his undergraduate studies at MIT, completed his PhD at Berkeley in 1986, and is now the Roger A. Strauch Professor of Electrical Engineering and Computer Science at UC Berkeley, where he has been on the faculty since 1987. Vazirani is widely regarded as one of the founders of quantum computing theory: the 1993 paper introducing Bernstein-Vazirani also laid the foundations of quantum complexity theory (defining the complexity class BQP — Bounded-error Quantum Polynomial time — and proving its basic relationships to classical complexity classes). His PhD student Ethan Bernstein is his co-author on the original paper. Vazirani later co-authored influential work with his PhD student Andris Ambainis on the quantum adversary method, and his Berkeley group has trained many of the field's leading researchers.

Vazirani's brother, Vijay Vazirani, is himself a celebrated computer scientist at UC Irvine (approximation algorithms, market equilibria). The Vazirani brothers' contributions to theoretical CS, both classical and quantum, are a small but concrete demonstration that Indian-origin computer scientists have been present and influential at the foundations of every major development in the field — a fact that a 15-year-old in India starting to study quantum computing should be aware of. Vazirani co-taught, with Berkeley colleague Ryan O'Donnell, one of the most popular online quantum-computing courses (edX, 2014 and later), which has introduced the Bernstein-Vazirani algorithm to hundreds of thousands of students worldwide.

Where this leads next

• Simon's algorithm — the next step up: an exponential speedup (quantum polynomial vs classical \Omega(2^{n/2})) for a harder hidden-structure problem. Directly inspired Shor.
• Hidden subgroup problem — the unifying framework. Bernstein-Vazirani is HSP over \mathbb{F}_2^n with a specific subgroup structure.
• Shor's algorithm — the most famous quantum algorithm. Uses the same Fourier-sampling template over \mathbb{Z}/N\mathbb{Z} instead of \mathbb{F}_2^n.
• Deutsch-Jozsa algorithm — the predecessor: same circuit, different promise, single-bit output.
• Phase Kickback — the core mechanism by which the oracle writes f(x) into phases.
• Grover's algorithm — a different oracle-based algorithm with a quadratic speedup for unstructured search.

References

1. Bernstein and Vazirani, Quantum complexity theory (1993) — the original paper introducing the algorithm and the class BQP. SIAM J. Comput. 26, 1411 (published version; preprint version widely distributed from 1993).
2. Wikipedia, Bernstein-Vazirani algorithm — the standard encyclopaedic treatment with a worked small-n example.
3. John Preskill, Lecture Notes on Quantum Computation, Ch. 6 (quantum algorithms) — theory.caltech.edu/~preskill/ph229.
4. Nielsen and Chuang, Quantum Computation and Quantum Information, §6.1.2 — Cambridge University Press.
5. Cleve, Ekert, Macchiavello, Mosca, Quantum algorithms revisited (1998) — unified treatment of Deutsch-Jozsa, Bernstein-Vazirani, Simon, and Shor as Fourier-sampling algorithms. arXiv:quant-ph/9708016.
6. Qiskit Textbook, Bernstein-Vazirani algorithm — runnable Python implementation with hardware demonstration.