The Bernstein-Vazirani Algorithm

Suppose a black box computes a secret dot product. Given a bit string $x$ , it returns $f(x) = a \cdot x \bmod 2$ . A classical computer needs $n$ queries to learn all $n$ bits of the hidden string $a$ . It learns one bit at a time. The Bernstein-Vazirani algorithm recovers all of $a$ using a single quantum query. It exploits superposition and phase kickback. This turns an oracle into a direct readout of hidden structure. This is not merely a party trick. It is the cleanest illustration of a recurring theme in quantum algorithm design. Hidden classical information can sometimes be extracted with exponentially fewer queries. This works by encoding it into the phase of a superposition. The phases are then interfered back into readable amplitudes. The same mechanism — Hadamard transform, oracle phase kickback, Hadamard transform again — reappears, in generalized form, in The Deutsch-Jozsa Algorithm. It eventually blossoms into the period-finding ideas behind Simon's Algorithm and Shor's algorithm. The big picture is this: classical query complexity for learning a linear function is $\Theta(n)$ , provably. Each classical query yields at most one bit of information about $a$ in the worst case. Quantum query complexity for the exact same problem collapses to $\Theta(1)$ . Bernstein and Vazirani used this gap in 1997. They gave the first oracle separation between quantum and classical computation that was provable, rather than merely suspected. This generalizes naturally to a recursive version. That version separates quantum $\mathsf{P}$ from the polynomial hierarchy under an oracle. This article gives a complete derivation of the algorithm. It covers the exact state evolution through each Hadamard and oracle application. It includes a correctness proof via the Hadamard eigenvalue identity. It also provides a full complexity analysis and a worked numerical trace showing every amplitude. It closes with the historical context. It ends with the natural path forward toward algorithms that detect hidden periodicities rather than hidden linear strings.

Key takeaways

The problem: given oracle access to $f(x) = a \cdot x \bmod 2$ for secret $a \in \{0,1\}^n$ , find $a$ .
Classically this needs exactly $n$ queries; quantumly it needs exactly $1$ .
The algorithm is Hadamard $^{\otimes n}$ → phase oracle → Hadamard $^{\otimes n}$ → measure.
Correctness follows from the identity $H^{\otimes n}|a\rangle = 2^{-n/2}\sum_x (-1)^{a\cdot x}|x\rangle$ , applied twice.
Phase kickback converts the oracle's action on an ancilla qubit into a global phase on the query register.
It is the direct ancestor of Simon's Algorithm and the template for phase-based hidden-structure algorithms.

The core insight

Encoding a hidden bit string into relative phases via one oracle call, then using a second Hadamard transform to convert those phases into a directly measurable computational-basis state, recovers the string exactly.

The idea

The Bernstein-Vazirani (BV) problem is stated over the field $\mathbb{F}_2$ . Fix a hidden string $a \in \{0,1\}^n$ . An oracle (black box) computes the Boolean function

f(x) = a \cdot x \bmod 2 = \left(\sum_{i=1}^n a_i x_i\right) \bmod 2,

for any $x \in \{0,1\}^n$ that we choose to query. The task is to determine $a$ exactly, using as few queries to $f$ as possible. Classically, the optimal strategy is to query the $n$ standard basis vectors $e_1, e_2, \dots, e_n$ (each having a single $1$ in one position). Since $f(e_i) = a_i$ , each query reveals exactly one bit of $a$ , and $n$ queries are both necessary and sufficient — necessary because any function output is a single classical bit, and an information-theoretic counting argument shows $n$ bits of unknown information require at least $n$ single-bit-output queries in the worst case. Quantumly, we are given the oracle as a unitary rather than a classical subroutine. Two equivalent oracle conventions are used in the literature; we adopt the standard phase oracle obtained via phase kickback applied to the more primitive bit-flip oracle $U_f: |x\rangle|y\rangle \mapsto |x\rangle|y \oplus f(x)\rangle$ . Preparing the ancilla in the state $|-\rangle = \frac{1}{\sqrt2}(|0\rangle - |1\rangle)$ , an eigenstate of the XOR-flip with eigenvalue $-1$ , converts the oracle into

U_f |x\rangle |-\rangle = (-1)^{f(x)} |x\rangle |-\rangle = (-1)^{a\cdot x}|x\rangle|-\rangle.

The ancilla is unchanged and can be discarded; the oracle now acts as a phase on the query register alone. This is exactly the phase-kickback trick used in the Deutsch-Jozsa algorithm, applied here to a richer function class (a linear function rather than a constant/balanced promise). The entire task reduces to: prepare a uniform superposition over all $x$ , let the oracle imprint phases $(-1)^{a\cdot x}$ , and then find a way to read $a$ off directly. The second Hadamard transform performs exactly this readout.

How it works

The circuit uses $n$ query qubits initialized to $|0\rangle^{\otimes n}$ and one ancilla qubit initialized to $|1\rangle$ , which is Hadamard-transformed into $|-\rangle$ .

Step 1 — Initialization. Prepare

|0\rangle^{\otimes n} \otimes |1\rangle.

Step 2 — Hadamard on all qubits. Applying $H^{\otimes n}$ to the query register and $H$ to the ancilla gives

\left(\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n} |x\rangle\right) \otimes |-\rangle.

Step 3 — Query the oracle once. The phase oracle acts as

U_f: |x\rangle|-\rangle \mapsto (-1)^{a\cdot x}|x\rangle|-\rangle,

giving the entangled-looking but actually product state

\frac{1}{\sqrt{2^n}}\sum_{x} (-1)^{a\cdot x}|x\rangle \otimes |-\rangle.

The ancilla decouples completely and is discarded (or measured and ignored).

Step 4 — Hadamard on the query register again. This is the crucial step. Using the identity (proved below)

H^{\otimes n} \left(\frac{1}{\sqrt{2^n}}\sum_x (-1)^{a\cdot x}|x\rangle\right) = |a\rangle,

the query register collapses, after this unitary, to the single computational basis state $|a\rangle$ .

Step 5 — Measure. Measuring the query register in the standard basis yields $a$ with probability $1$ . ``` Algorithm BernsteinVazirani(oracle U_f, n) // U_f implements |x⟩|y⟩ -> |x⟩|y ⊕ (a·x mod 2)⟩ for hidden a ∈ {0,1}^n Input: black-box oracle U_f, size parameter n Output: the hidden string a ∈ {0,1}^n 1. Initialize register R of n qubits to |0...0⟩ 2. Initialize ancilla qubit A to |1⟩ 3. Apply H to A // A is now |-⟩ = (|0⟩ - |1⟩)/√2 4. Apply H to every qubit of R // R is now uniform superposition over all x 5. Apply U_f to (R, A) // phase kickback: R picks up phase (-1)^(a·x) 6. Apply H to every qubit of R again // R collapses (via interference) to |a⟩ 7. Measure R in the standard basis 8. Return the measured bit string as a ``` The single call to `U_f` in step 5 is the only query made. Everything else is local unitary manipulation and a final measurement — no repetition, no amplitude amplification, no error probability to amplify away.

Figure

Circuit diagram: one oracle query sandwiched between two Hadamard layers

Complexity & correctness

Query complexity. The algorithm makes exactly one call to `U_f`. This is optimal: any classical algorithm requires $n$ queries in the worst case, since each classical query to a Boolean function returns one bit, and there are $2^n$ possible values of $a$ , so at least $\log_2(2^n) = n$ bits of information — hence at least $n$ single-bit queries — are information-theoretically required to distinguish all cases (this can also be shown directly by an adversary argument on the standard basis queries). So the separation is $1$ versus $n$ : exponential in query complexity, though the function class itself is extremely simple.

Gate complexity / time complexity. The circuit uses $2n$ single-qubit Hadamard gates plus one call to $U_f$ (whose own gate cost depends on how $f$ is implemented, but is treated as a black box of unit cost in the query model). Total circuit depth is $O(n)$ gates plus one oracle call, and $O(n)$ qubits are used. Classically, computing $a$ via the standard-basis-vector strategy costs $n$ queries and $O(n)$ total classical work, so BV also improves gate-level cost, not just query count, when the oracle's per-call cost is comparable in both models.

Space complexity. $n+1$ qubits: $n$ for the query register, $1$ ancilla. No auxiliary qubits beyond this are needed.

Correctness proof. The entire argument rests on one identity: for $a, x \in \{0,1\}^n$ ,

H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{z \in \{0,1\}^n} (-1)^{x\cdot z} |z\rangle.

Apply this with $x = 0^n$ during step 2, obtaining the uniform superposition $\frac{1}{\sqrt{2^n}}\sum_x |x\rangle$ (since $(-1)^{0\cdot z}=1$ for all $z$ ). This confirms step 2. The oracle then multiplies the amplitude of each $|x\rangle$ by $(-1)^{a\cdot x}$ , giving the state

|\psi\rangle = \frac{1}{\sqrt{2^n}}\sum_x (-1)^{a\cdot x}|x\rangle.

Now apply $H^{\otimes n}$ again. Using linearity and the same Hadamard identity applied to each basis vector $|x\rangle$ inside the sum,

H^{\otimes n}|\psi\rangle = \frac{1}{\sqrt{2^n}}\sum_x (-1)^{a\cdot x} \cdot \frac{1}{\sqrt{2^n}}\sum_z (-1)^{x\cdot z}|z\rangle = \frac{1}{2^n}\sum_z \left(\sum_x (-1)^{(a\oplus z)\cdot x}\right)|z\rangle.

The inner sum over $x$ is a character sum over $\mathbb{F}_2^n$ . It equals $2^n$ if $a \oplus z = 0^n$ (i.e., $z=a$ ), and it equals $0$ otherwise, because summing $(-1)^{w\cdot x}$ over all $x$ for any fixed nonzero $w$ gives exactly as many $+1$ 's as $-1$ 's by a pairing argument (flipping any coordinate $i$ with $w_i = 1$ flips the sign, and such an $i$ exists whenever $w \neq 0$ ). Therefore

H^{\otimes n}|\psi\rangle = \frac{1}{2^n}\cdot 2^n |a\rangle = |a\rangle.

The query register is exactly $|a\rangle$ with probability $1$ — not approximately, not with high probability, but exactly, assuming a perfect (noiseless) oracle and gates. Measuring in the standard basis therefore returns $a$ deterministically. This completes the correctness proof.

Tradeoffs and honesty about scope. The dramatic $1$ -vs- $n$ separation is a query complexity statement relative to a black-box oracle; it says nothing about the hardness of computing $f$ itself, since $f(x) = a\cdot x$ is already trivially easy to compute classically once $a$ is known. The power of BV is a clean demonstration mechanism, not a source of practical algorithmic speedup for a "real-world" hidden linear-function-guessing task, because such a task rarely arises in isolation as an oracle. Its lasting importance is pedagogical and structural: it is the minimal example showing that a single quantum query can outperform any number of classical randomized queries on a well-defined problem, and the phase-interference recipe it introduces generalizes directly to problems, like Simon's problem, that do have significant downstream cryptographic implications.

Worked example

Take $n = 3$ and hidden string $a = 101$ (i.e., $a_1=1, a_2=0, a_3=1$ ), so $f(x_1x_2x_3) = x_1 \oplus x_3$ .

Step 1–2. Query register starts as $|000\rangle$ , Hadamard gives uniform superposition over all $8$ strings, each amplitude $1/\sqrt8$ . Ancilla becomes $|-\rangle$ .

Step 3 (oracle). Each basis state $|x\rangle$ receives phase $(-1)^{a\cdot x} = (-1)^{x_1 \oplus x_3}$ (using the fact that $a\cdot x \bmod 2$ equals $x_1 \oplus x_3$ here). The table below lists every basis state and its phase after the oracle.

$x$	$x_1 \oplus x_3$	phase $(-1)^{a\cdot x}$
000	0	+1
001	1	−1
010	0	+1
011	1	−1
100	1	−1
101	0	+1
110	1	−1
111	0	+1

So after step 3, the state (ignoring the decoupled ancilla and the global $1/\sqrt8$ factor) is

+|000\rangle -|001\rangle +|010\rangle -|011\rangle -|100\rangle +|101\rangle -|110\rangle +|111\rangle.

Step 4 (second Hadamard layer). Rather than expanding all $64$ cross terms, use the proven shortcut: $H^{\otimes 3}$ applied to $\frac{1}{\sqrt8}\sum_x (-1)^{a\cdot x}|x\rangle$ must yield $|a\rangle = |101\rangle$ exactly, by the identity proved above. We can spot-check this by verifying the amplitude of $|101\rangle$ directly:

\text{amp}(|101\rangle) = \frac{1}{8}\sum_x (-1)^{a\cdot x}(-1)^{x\cdot 101} = \frac{1}{8}\sum_x (-1)^{(a\oplus 101)\cdot x} = \frac{1}{8}\sum_x (-1)^{0} = \frac{1}{8}\cdot 8 = 1.

Since $a \oplus 101 = 000$ , every term in the sum is $+1$ , giving amplitude exactly $1$ . Checking any other basis state, say $|011\rangle$ : $a \oplus 011 = 110 \neq 0$ , so the character sum splits evenly between $+1$ and $-1$ and cancels to $0$ .

Step 5 (measure). The query register is $|101\rangle$ with certainty; measurement returns $a = 101$ , matching the hidden string, using only the single oracle call from step 3.

Figure

Amplitude flow for n=3, a=101, across the two Hadamard layers

Common pitfalls & traps

Pitfall	Why it's wrong	Fix
Using the bit-flip oracle $U_f$ directly without the $\lvert-\rangle$ ancilla trick	Without phase kickback, the oracle entangles the ancilla with the query register and the second Hadamard layer no longer isolates $\lvert a\rangle$	Always initialize the ancilla to $\lvert1\rangle$ and Hadamard it to $\lvert-\rangle$ before querying
Forgetting to apply Hadamard to the ancilla	The oracle then just flips a target bit conditioned on $f(x)$ with no phase effect at all	Explicitly apply $H$ to the ancilla in step 3 of the circuit
Measuring the query register before the second Hadamard layer	The state $\sum_x (-1)^{a\cdot x}\lvert x\rangle$ looks uniform in measurement probability — every outcome is equally likely, giving no information about $a$	Apply the second $H^{\otimes n}$ before measuring; the information is in the phase, not the pre-interference measurement statistics
Confusing BV with Deutsch-Jozsa and expecting only a promise-decision answer	BV recovers the entire string $a$ , not a single bit like "constant vs. balanced"	Recognize BV as DJ's linear generalization: same circuit, richer output
Assuming the $1$ -query bound survives with noisy or imperfect gates	The exact cancellation relies on perfect phase interference; realistic noise reduces the success probability below $1$	State the deterministic result as an idealized, noiseless-oracle guarantee, and treat noisy hardware separately
Believing this proves quantum computers are faster for all problems	The separation is specific to this promise/oracle structure; it says nothing about general-purpose speedup	Treat BV as a structural, not universal, separation result

Pioneers & history

Origins · 1 minEthan Bernstein and how this was discovered

Ethan Bernstein

born 1966 · American computer scientist, co-developer of the algorithm with Umesh Vazirani

Umesh Vazirani

born 1957 · Professor of computer science at UC Berkeley, prominent figure in quantum complexity theory

The Bernstein-Vazirani algorithm was introduced as a query-complexity separation result, deliberately designed to be simpler than Simon's algorithm while still demonstrating a strict quantum advantage that could be proven rigorously rather than only conjectured. It built directly on the ideas of phase kickback and superposition query already present in the Deutsch-Jozsa algorithm, but sharpened the separation from a promise-decision problem into a full string-recovery problem with a clean $1$ -vs- $n$ query gap.

Origins · 1 minhow this was discovered

History

1985

— Deutsch introduces the first quantum algorithm exploiting superposition to gain query advantage over deterministic classical query.

1992

— Deutsch and Jozsa generalize this into the promise-based constant-vs-balanced separation, establishing phase kickback as a reusable technique.

1993

— Bernstein and Vazirani publish "Quantum Complexity Theory," introducing the recursive version separating quantum

\mathsf{P}

from the polynomial hierarchy relative to an oracle.

1997

— The journal version formalizes the single-instance linear-string recovery algorithm now taught as the Bernstein-Vazirani algorithm.

1994

— Simon's algorithm appears shortly after, generalizing the phase-interference recipe to periodicity detection over

\mathbb{Z}_2^n

, directly inspiring Shor's factoring algorithm.

Where this matters

The Bernstein-Vazirani algorithm is used almost universally as the entry-level demonstration circuit on real quantum hardware and cloud quantum computing platforms, because it is small, deterministic in the ideal case, and immediately shows a measurable, checkable output that differs from any classical single-query strategy. Students and researchers routinely implement it on superconducting-qubit and trapped-ion cloud backends as a first "hello world" beyond single-qubit demonstrations, using it to calibrate readout fidelity and gate error by comparing the observed output distribution to the ideal deterministic spike at $|a\rangle$ . Pedagogically, it is the standard bridge between the constant/balanced promise of Deutsch-Jozsa and the group-structure hiding of Simon's algorithm, which in turn is the direct conceptual ancestor of the period-finding subroutine inside Shor's algorithm. The phase-kickback-then-interfere pattern it crystallizes — encode structure into relative phase via one oracle call, then use a change of basis (Hadamard, or more generally a quantum Fourier transform) to read that structure back out — is the single most reused architectural motif in query-based quantum algorithms, appearing again in amplitude estimation and in various quantum machine learning feature-map constructions. It also serves as a canonical example in complexity theory courses discussing oracle separations and the limits of what black-box lower bounds can and cannot say about real-world computational hardness.

Ask the tutor: How would the Bernstein-Vazirani circuit change if the hidden function included a constant offset, i.e., $f(x) = a\cdot x \oplus b$ for an unknown bit $b$ ?

Why does the algorithm need exactly one ancilla qubit and not more?

The ancilla's only job is to serve as an eigenstate of the underlying bit-flip oracle so that the oracle's action becomes a global phase rather than a bit flip on a separate register. A single qubit prepared in $|-\rangle = \frac{1}{\sqrt2}(|0\rangle-|1\rangle)$ satisfies $|y\rangle \mapsto |y\oplus 1\rangle$ having eigenvalue $-1$ on this state, which is exactly what's needed since $f(x)$ is a single bit. If $f$ returned multiple output bits, you might need a correspondingly sized ancilla register, but for a Boolean-valued $f(x)=a\cdot x \bmod 2$ , one ancilla qubit suffices and using more would be wasted resources with no effect on correctness.

Is the Bernstein-Vazirani algorithm probabilistic, like Grover's algorithm?

No. Assuming a perfect, noiseless implementation of the oracle and gates, the algorithm is fully deterministic: the final measurement returns the exact hidden string $a$ with probability exactly $1$ , not with high probability. This distinguishes it from Grover's algorithm, whose success probability approaches but does not reach $1$ and which requires $O(\sqrt{2^n})$ queries rather than a fixed single query. The determinism here is a direct consequence of the exact cancellation shown in the correctness proof: the character sum over $\mathbb{F}_2^n$ evaluates to precisely $0$ or $2^n$ , with no intermediate values, so there is no residual measurement uncertainty in the idealized model.

How does this algorithm differ from the Deutsch-Jozsa algorithm if they use the same circuit?

They share an identical circuit template — Hadamard, oracle, Hadamard, measure — but differ in what the oracle promises and what the output means. Deutsch-Jozsa promises $f$ is either constant or balanced and asks a one-bit decision; Bernstein-Vazirani promises $f(x)=a\cdot x \bmod 2$ for some fixed hidden $a$ and asks for the entire string $a$ . In fact, Bernstein-Vazirani can be seen as a generalization: the Deutsch-Jozsa decision is recoverable as a special case, since $f$ is constant if and only if $a = 0^n$ , which the BV circuit would report by returning the all-zero string.

Why can't a classical randomized algorithm beat n queries, even with error allowed?

Even allowing bounded error, information-theoretic arguments (formalized via Yao's minimax principle or direct entropy counting) show that distinguishing among $2^n$ equally likely candidate strings $a$ requires close to $n$ bits of information on average, and each classical query to a Boolean-valued $f$ yields at most one bit. Randomization can sometimes reduce worst-case query counts for other problems, but for this particular linear-recovery task the lower bound remains $\Omega(n)$ even in the randomized bounded-error query model, because the outputs for different candidate $a$ 's are not compressible into fewer than $n$ independent bits of evidence.

Does Bernstein-Vazirani give any real-world cryptographic or computational advantage?

Directly, no — the function $a\cdot x \bmod 2$ is already trivial to evaluate and does not model any hard real-world problem, so the $1$ -vs- $n$ separation is a demonstration of quantum query power rather than a practical speedup for an existing application. Its real-world importance is indirect: the exact same phase-interference technique, generalized to detect a hidden period rather than a hidden linear string, becomes Simon's Algorithm, which in turn inspired the quantum Fourier transform machinery behind Shor's factoring algorithm — a result with direct implications for RSA and Diffie-Hellman cryptography.

What happens if the oracle is not exactly linear — does the algorithm silently give a wrong answer?

Yes, and this is an important caveat: the algorithm's guarantee is conditional on the promise that $f(x) = a\cdot x \bmod 2$ for some fixed $a$ . If $f$ is not of this form, the circuit still runs and still produces some measured output, but that output need not correspond to any meaningful "hidden string," since the derivation of $H^{\otimes n}|\psi\rangle = |a\rangle$ relied entirely on the phase pattern being exactly $(-1)^{a\cdot x}$ . Unlike some algorithms that degrade gracefully, this one has no built-in mechanism to detect or flag a violated promise; verifying the promise, if needed, requires separate classical reasoning about how $f$ was constructed.

How does phase kickback in this algorithm relate to phase kickback used elsewhere, such as in Shor's algorithm?

The underlying mechanism is identical: a target qubit or register is prepared in an eigenstate of the operation the oracle performs, so that applying a controlled version of that operation leaves the eigenstate unchanged but multiplies the control register's corresponding amplitude by the eigenvalue. In Bernstein-Vazirani, the eigenstate is the single qubit $|-\rangle$ and the eigenvalues are $\pm 1$ . In Shor's algorithm's phase estimation step, the eigenstate is an eigenvector of modular multiplication and the eigenvalues are complex roots of unity, requiring a full quantum Fourier transform rather than a simple Hadamard layer to read out. Bernstein-Vazirani is the simplest nontrivial instance of this general phase-kickback-and-readout pattern.