Bernstein–Vazirani Algorithm

The Bernstein–Vazirani algorithm is the cleanest demonstration in all of quantum computing that interference — not brute-force parallelism — is where the power lives. You are handed a black box that computes a hidden linear function $f(x)=a\cdot x\bmod 2$ for some secret $n$ -bit string $a$ , and asked to recover $a$ . Classically the box is stingy: each query returns a single parity bit, so learning an $n$ -bit secret costs $n$ queries, one bit at a time. The quantum algorithm reads the entire string $a$ with a single query. It does so with a circuit already familiar from Deutsch and Deutsch–Jozsa — a layer of Hadamards, one oracle call implemented through phase kickback, and a second layer of Hadamards — and the answer $a$ drops out of the final measurement deterministically, with probability exactly one. The mechanism is worth stating up front because it is so tidy. The first Hadamard layer spreads the register into an equal superposition over all $2^n$ inputs. The oracle stamps each term $|x\rangle$ with the sign $(-1)^{a\cdot x}$ , painting a checkerboard of pluses and minuses across the amplitudes — and that sign pattern is precisely the $a$ -th Walsh function. The second Hadamard layer is the inverse Walsh–Hadamard transform, which recognizes that pattern and focuses every scrap of amplitude onto the one basis state $|a\rangle$ , cancelling everywhere else. Bernstein and Vazirani published this in 1993 alongside a deeper recursive variant and the very definition of the complexity class BQP; the flat version here has become the canonical first lesson in Fourier sampling and a standard benchmark for real quantum hardware.

Key takeaways

The Bernstein–Vazirani problem: given oracle access to $f(x)=a\cdot x\bmod 2$ for an unknown $n$ -bit string $a$ , recover $a$ .
Classically each query yields one bit of $a$ , so $n$ queries are needed; the quantum algorithm recovers all of $a$ in one query.
The circuit is $H^{\otimes n}\,U_f\,H^{\otimes n}$ on $|0\rangle^{\otimes n}$ with an ancilla in $|-\rangle$ — it maps $|0\rangle^{\otimes n}$ deterministically to $|a\rangle$ .
The engine is amplitude encoding of an inner product: the Walsh–Hadamard transform of $(-1)^{a\cdot x}$ is the single basis state $|a\rangle$ , by character orthogonality $\sum_x(-1)^{b\cdot x}=2^n\delta_{b,0}$ .
It is the abelian hidden subgroup problem over $(\mathbb{Z}_2)^n$ and the deterministic core of Deutsch–Jozsa, foreshadowing Simon, the QFT, and Shor.
The $n$ -to- $1$ query gap is exact and deterministic; a randomized classical algorithm solves the flat problem in $O(1)$ , so the true super-polynomial separation is the recursive variant.
Key idea: apply $H^{\otimes n}$ before and after the phase oracle for $f(x)=a\cdot x$ ; the first layer builds an equal superposition, the oracle stamps the phase pattern $(-1)^{a\cdot x}$ , and the second layer is the inverse Walsh–Hadamard transform that maps that pattern exactly onto $|a\rangle$ , so one measurement returns $a$ with certainty.

The core insight

Apply $H^{\otimes n}$ before and after the phase oracle for $f(x)=a\cdot x$ : the first Hadamard layer creates an equal superposition, the oracle stamps each term with $(-1)^{a\cdot x}$ , and the second Hadamard layer is the inverse Walsh–Hadamard transform, which collapses that parity pattern onto the single basis state $|a\rangle$ — so one measurement yields $a$ deterministically.

Where this lives today

Bernstein–Vazirani has outgrown its origins as a proof-of-concept and become a practical instrument. Because its ideal output is a single, known bitstring, it is one of the most popular fixed-output benchmarks for real quantum processors: you program in a known $a$ , run the shallow circuit — one layer of Hadamards, a CNOT-based oracle, another layer of Hadamards — and any spread of the measured distribution away from the delta at $a$ is a direct, interpretable measure of gate and readout error. IBM, Google, IonQ, Rigetti and university groups have all run BV as a scaling test on dozens of qubits, and its low, constant depth makes it a favourite for probing crosstalk and mid-circuit fidelity. Conceptually it is the doorway to Fourier sampling: the Hadamard layer is the quantum Fourier transform over $(\mathbb{Z}_2)^n$ , and recognizing the oracle's phase as a single group character is exactly the move that, scaled up to $\mathbb{Z}_N$ , becomes phase estimation and Shor's algorithm. The same "learn a hidden linear function from one query" motif reappears across quantum learning theory — learning parities, juntas, and Fourier-sparse functions — where quantum examples can be exponentially more sample-efficient than classical labeled data. And as the base case of the abelian hidden subgroup problem, with hidden subgroup $\{x:a\cdot x=0\}$ , it is the first rung on the ladder whose top rungs are discrete logarithm and integer factoring.

The physical picture

Think of the oracle as a rubber stamp for phases. After the first Hadamard layer the register holds an equal sum over every input $x$ , all $2^n$ amplitudes identical. The oracle then multiplies each term $|x\rangle$ by $(-1)^{a\cdot x}$ — a $+1$ where the parity $a\cdot x$ is even, a $-1$ where it is odd. Nothing about the magnitudes changes; only a pattern of signs is laid down. Yet that pattern is the entire fingerprint of the secret $a$ , because it is the $a$ -th Walsh function. The circuit below is the standard three-act structure: Hadamards to spread, one oracle call to stamp, Hadamards to focus.

Figure

The Bernstein–Vazirani circuit for n = 3 query qubits and a hidden string a = 101: the query register starts in the zero state, the ancilla in the one state; H⊗3 builds the equal superposition, the oracle U_f applies the phase (−1)^(a·x) by kickback onto the ancilla in the minus state, and a second H⊗3 focuses all amplitude onto the basis state 101 that a single measurement then reads out

The second Hadamard layer is where the magic happens, and it is pure interference. Measuring right after the oracle would be useless — every amplitude still has the same magnitude $1/\sqrt{2^n}$ , so a measurement returns a uniformly random string that says nothing about $a$ . The information sits entirely in the phases, which a basis measurement cannot see. The final $H^{\otimes n}$ converts phase into population: it sums the $2^n$ signed amplitudes with its own sign pattern, and the two patterns reinforce perfectly for the outcome $z=a$ and cancel exactly for every $z\neq a$ . The bar chart below makes this collapse quantitative for the same $a=101$ shown in the circuit.

Figure

Amplitude collapse for n = 3, a = 101. Left: after the oracle all eight amplitudes have equal magnitude 1/√8 ≈ 0.354, carrying only the sign pattern + − + − − + − + which is the fingerprint of a. Right: after the second H⊗3 the inverse Walsh–Hadamard transform concentrates everything onto the basis state 101 with amplitude 1.000, while all seven other amplitudes are exactly 0 — a single measurement returns 101 with probability one

The core equations

The whole story is set by the promise on $f$ : it is not an arbitrary Boolean function but a linear one, a single inner product with the hidden string. Fixing that promise is what lets one query suffice.

f:\{0,1\}^n\to\{0,1\},\qquad f(x)=a\cdot x=\bigoplus_{i=1}^{n}a_i x_i \qquad (1)

where: $a$ — the unknown $n$ -bit hidden string to recover; $x$ — the $n$ -bit query input; $a\cdot x$ — bitwise inner product modulo 2, the parity of the overlapping 1-bits; $\oplus$ — addition mod 2 (XOR). The reading: $f$ answers a single yes/no question about each input, "is the overlap of $x$ with $a$ odd?", and probing $x=e_i$ returns the single bit $a_i$ . The oracle is supplied in the reversible XOR form standard for all quantum query algorithms, writing the answer into a separate register so the map stays unitary.

U_f\,|x\rangle|y\rangle = |x\rangle\,|y\oplus f(x)\rangle \qquad (2)

where: $|x\rangle$ — the $n$ -qubit query register; $|y\rangle$ — the single-qubit answer register; $\oplus$ — XOR on that answer qubit. The reading: $U_f$ leaves the query register alone and toggles the answer qubit exactly when $f(x)=1$ ; it is its own inverse, $U_f^2=I$ . Preparing the answer register in $|-\rangle$ turns that bit-flip oracle into a phase oracle — the phase-kickback trick that all three of Deutsch, Deutsch–Jozsa and Bernstein–Vazirani run on.

U_f\,|x\rangle|-\rangle = (-1)^{f(x)}\,|x\rangle|-\rangle,\qquad |-\rangle=\tfrac{1}{\sqrt2}\big(|0\rangle-|1\rangle\big) \qquad (3)

where: $|-\rangle$ — the $-1$ eigenstate of the XOR action; $(-1)^{f(x)}$ — the phase kicked back onto each query term. The reading: the ancilla is an eigenvector, so it factors out unchanged and the oracle's effect is a pure sign on the query register — exactly the sign we can later interfere. The tool that both builds the superposition and reads it out is the $n$ -fold Hadamard, whose matrix elements are the characters of the group $(\mathbb{Z}_2)^n$ .

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

where: $H$ — the single-qubit Hadamard, $H|b\rangle=\tfrac{1}{\sqrt2}\sum_c(-1)^{bc}|c\rangle$ ; $z$ — the output label summed over all $n$ -bit strings; $x\cdot z$ — the bitwise inner product in the phase. The reading: setting $x=0$ makes every sign $+1$ and gives the uniform superposition; a general $x$ imprints the parity pattern that is the $x$ -th Walsh function. Chaining the first Hadamard layer and the oracle produces the signed superposition — the state the second figure charts on its left.

|0\rangle^{\otimes n}\xrightarrow{\,H^{\otimes n}\,}\frac{1}{\sqrt{2^n}}\sum_{x}|x\rangle\xrightarrow{\,U_f\,}\frac{1}{\sqrt{2^n}}\sum_{x}(-1)^{a\cdot x}|x\rangle \qquad (5)

where: $\sum_x$ — the sum over all $2^n$ inputs; $(-1)^{a\cdot x}$ — the parity-phase fingerprint of $a$ . The reading: at this stage every amplitude has magnitude $2^{-n/2}$ , so a measurement here is uniformly random and worthless — the answer is hidden in the signs. The second Hadamard layer inverts the transform and returns the hidden string as a single deterministic basis state.

H^{\otimes n}\!\left[\frac{1}{\sqrt{2^n}}\sum_{x}(-1)^{a\cdot x}|x\rangle\right]=|a\rangle \qquad (6)

where: $|a\rangle$ — the computational basis state encoding the hidden string. The reading: because $H^{\otimes n}$ is its own inverse and $(-1)^{a\cdot x}$ is literally the pattern $H^{\otimes n}$ produces from $|a\rangle$ , applying it again undoes the spreading and returns $|a\rangle$ exactly. That collapse rests on one identity — character orthogonality on $(\mathbb{Z}_2)^n$ — which is the true engine of the algorithm.

\sum_{x\in\{0,1\}^n}(-1)^{b\cdot x}=2^n\,\delta_{b,0^n} \qquad (7)

where: $b$ — shorthand for $a\oplus z$ ; $\delta_{b,0^n}$ — 1 if $b$ is the all-zero string, else 0. The reading: for $b\neq 0$ exactly half the inputs give $+1$ and half give $-1$ , so the sum is zero; only $b=0$ (that is, $z=a$ ) survives, with full weight $2^n$ . The payoff is a query-count separation that is as sharp as separations get in the exact model.

q_{\text{quantum}}=1,\qquad q_{\text{classical,\,exact}}=n \qquad (8)

where: $q_{\text{quantum}}$ — oracle queries used by the algorithm; $q_{\text{classical,exact}}$ — deterministic classical queries needed to learn $a$ exactly. The reading: one quantum query replaces $n$ classical ones — a gap that grows without bound as the strings get longer, though (as the warning notes) it is a statement about the exact deterministic model.

Derivation APhase kickback turns the XOR oracle into a sign

The goal is to prove the single identity that makes the whole algorithm run: that the standard reversible oracle $U_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle$ , when its answer qubit is prepared in the state $|-\rangle$ , acts as a pure phase $(-1)^{f(x)}$ on the query register and leaves the ancilla untouched. This is what lets us treat $U_f$ not as something that scribbles an answer into a scratch register but as something that stamps a computable sign onto each branch of a superposition, and it is the exact point where quantum querying diverges from classical querying.

Step 1. Act $U_f$ on a single query term with the ancilla in $|-\rangle$ and push it through by linearity: $U_f|x\rangle\tfrac{1}{\sqrt2}(|0\rangle-|1\rangle)=|x\rangle\tfrac{1}{\sqrt2}(|0\oplus f(x)\rangle-|1\oplus f(x)\rangle)$ . Why: the oracle is linear, so it acts on the $|0\rangle$ and $|1\rangle$ pieces of the ancilla separately, and each simply gets XORed with $f(x)$ .

Step 2. Evaluate the two branches using $0\oplus f=f$ and $1\oplus f=\overline{f}$ (the complement): the state becomes $|x\rangle\tfrac{1}{\sqrt2}(|f(x)\rangle-|\overline{f(x)}\rangle)$ . Why: XOR either leaves the bit alone or flips it, so the ancilla's two kets are always $|f(x)\rangle$ and its complement — the same two labels $0$ and $1$ , possibly swapped.

Step 3. Read off the sign by cases. If $f(x)=0$ the bracket is $\tfrac{1}{\sqrt2}(|0\rangle-|1\rangle)=|-\rangle$ ; if $f(x)=1$ it is $\tfrac{1}{\sqrt2}(|1\rangle-|0\rangle)=-|-\rangle$ . Both are captured by $(-1)^{f(x)}|-\rangle$ , so $U_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle$ . Why: flipping the two labels of $|-\rangle$ is the same as multiplying it by $-1$ , which is exactly how a bit-flip on the ancilla becomes a sign on the whole term — the phase "kicks back" to the query register.

Step 4. Note that the ancilla emerges in $|-\rangle$ unchanged, so it factors out of the entire computation and can be ignored from here on; the query register alone carries $(-1)^{f(x)}$ . Why: because the ancilla is an eigenvector of $U_f$ 's action, it never entangles with the query register, which is precisely what allows the clean single-register analysis of the next derivation.

Go deeper · Derivation B · 2 minOne query yields the hidden string

Derivation BOne query yields the hidden string

The aim is to carry the full $n+1$ -qubit state through the circuit $H^{\otimes n}\,U_f\,H^{\otimes n}$ and prove that it deposits $|a\rangle$ in the query register with certainty, using exactly one oracle call. The one nontrivial ingredient is character orthogonality on $(\mathbb{Z}_2)^n$ , equation (7); everything else is bookkeeping of Hadamard layers and the phase-kickback result just established. Seeing every $z\neq a$ amplitude vanish by exact cancellation, while the $z=a$ amplitude builds to one, is the concrete meaning of "interference does the computation."

Step 1. Initialize the query register in $|0\rangle^{\otimes n}$ and the ancilla in $|1\rangle$ , then Hadamard everything. The ancilla becomes $|-\rangle$ and the query register becomes the equal superposition, giving $\tfrac{1}{\sqrt{2^n}}\sum_x|x\rangle\,|-\rangle$ . Why: starting the ancilla in $|1\rangle$ rather than $|0\rangle$ is what makes $H|1\rangle=|-\rangle$ , arming the phase-kickback eigenstate before the oracle is called.

Step 2. Apply $U_f$ once. By phase kickback the ancilla factors out and each query term picks up $(-1)^{a\cdot x}$ , leaving $\tfrac{1}{\sqrt{2^n}}\sum_x(-1)^{a\cdot x}|x\rangle\,|-\rangle$ . Why: this is the only oracle access in the entire algorithm — a single call stamps the complete fingerprint of $a$ across all $2^n$ amplitudes at once.

Step 3. Apply the second Hadamard layer to the query register, expanding each $H^{\otimes n}|x\rangle=\tfrac{1}{\sqrt{2^n}}\sum_z(-1)^{x\cdot z}|z\rangle$ and collecting the coefficient of each $|z\rangle$ . Combining the two phases with mod-2 arithmetic, $a\cdot x + x\cdot z=(a\oplus z)\cdot x$ , gives $\tfrac{1}{2^n}\sum_z\big[\sum_x(-1)^{(a\oplus z)\cdot x}\big]|z\rangle$ . Why: the two sign patterns — the oracle's $(-1)^{a\cdot x}$ and the Hadamard's $(-1)^{x\cdot z}$ — merge into a single parity $(a\oplus z)\cdot x$ , whose sum over $x$ is exactly the character sum that decides the whole outcome.

Step 4. Evaluate the inner sum by character orthogonality (7): $\sum_x(-1)^{(a\oplus z)\cdot x}=2^n\delta_{z,a}$ , so the bracket is $2^n$ when $z=a$ and $0$ otherwise. The state collapses to $\tfrac{1}{2^n}\cdot 2^n\,|a\rangle=|a\rangle$ . Why: every wrong string $z\neq a$ has its amplitude annihilated by perfect destructive interference, while the right string $z=a$ has all $2^n$ terms add in phase — this is the delta peak in the second figure.

Step 5. Measure the query register in the computational basis. The state is exactly $|a\rangle$ , so the outcome is the bitstring $a$ with $\Pr=1$ . Why: there is no residual amplitude anywhere else, so success is deterministic — no repetition, no error term, one query and done. *The collapse follows from $\sum_x(-1)^{b\cdot x}=2^n\delta_{b,0}$ ; for $n=3$ , $a=101$ the eight signed amplitudes $1/\sqrt{8}$ with signs $+\,-\,+\,-\,-\,+\,-\,+$ Walsh-transform to a single unit amplitude at $|101\rangle$ .*

Go deeper · Derivation C · 2 minWhy classical querying needs n queries

Derivation CWhy classical querying needs n queries

The purpose is to show that no deterministic classical algorithm can identify $a$ with fewer than $n$ oracle queries, so that the quantum single-query result is a genuine $n$ -to- $1$ separation and not an artifact of a weak classical strategy. The argument is linear algebra over the two-element field $\mathbb{F}_2$ : each classical query returns one linear equation in the unknown $a$ , and pinning down an $n$ -dimensional vector requires $n$ independent equations. This is the exact, worst-case, deterministic lower bound; the warning below explains why relaxing to randomized bounded-error querying changes the picture.

Step 1. Observe that a classical query at a chosen point $x_k$ returns the single bit $b_k=f(x_k)=a\cdot x_k$ , which is one linear constraint $a\cdot x_k=b_k$ on the unknown $a\in\mathbb{F}_2^n$ . Why: the promise that $f$ is linear is double-edged — it is what the quantum algorithm exploits, but classically it means each query reveals only one scalar equation, never more.

Step 2. After $q$ queries the algorithm holds the linear system $Xa=b$ , where $X\in\mathbb{F}_2^{q\times n}$ has the queried points $x_k$ as its rows. A unique solution for $a$ exists only if $X$ has full column rank, $\mathrm{rank}(X)=n$ . Why: if the rank were below $n$ the solution set would contain at least two candidate strings consistent with all answers, and the algorithm could not decide between them.

Step 3. Bound the rank by the number of rows, $\mathrm{rank}(X)\le q$ . Combining with the requirement $\mathrm{rank}(X)=n$ forces $q\ge n$ . Why: rank can never exceed the count of equations, so fewer than $n$ queries can never supply the $n$ independent constraints needed to isolate $a$ .

Step 4. Check that $n$ queries also suffice: probing the standard basis vectors $x_k=e_k$ returns $f(e_k)=a\cdot e_k=a_k$ , reading off the bits of $a$ one at a time. So $q=n$ is exactly optimal classically. Why: this constructive matching strategy shows the bound is tight — the classical cost is precisely $n$ , against the quantum cost of $1$ . *The rank argument over $\mathbb{F}_2$ gives the exact/deterministic bound, and the basis-probing strategy shows it is tight at $q=n$ . Note that a randomized classical algorithm sampling random $x$ and running Gaussian elimination recovers $a$ in $O(1)$ expected queries — so this bound is specific to the exact deterministic model.*

Limiting cases

Degenerate inputs and small $n$ sharpen exactly what the algorithm is doing and how it connects to its neighbours.

Case	Result	Meaning
All-zero hidden string	$a=0^n\Rightarrow f(x)=0\ \forall x$	The oracle applies no phase; $H^{\otimes n}H^{\otimes n}=I$ returns $\|0\rangle^{\otimes n}$ , correctly reporting $a=0$ — the "constant-zero" overlap with Deutsch–Jozsa.
Single-bit string $a=e_i$	$f(x)=x_i,\ a\cdot x=x_i$	The algorithm returns $\|e_i\rangle$ ; classically the query $f(e_i)=1$ gives the same one bit, but the quantum recipe handles all $a$ with the same one query.
$n=1$ reduces to Deutsch	$f(x)=a_0x,\ a_0\in\{0,1\}$	Distinguishing $a_0=0$ (constant) from $a_0=1$ (identity/balanced) on one qubit is exactly Deutsch's problem; Bernstein–Vazirani is the $n$ -qubit lift.
Same circuit as Deutsch–Jozsa	read all $n$ bits vs. read one bit	Identical $H^{\otimes n}U_fH^{\otimes n}$ circuit; DJ asks only "is the outcome $0^n$ ?" while BV interprets the full bitstring as $a$ .
Randomized classical model	$q_{\text{cls,bdd-err}}=O(1)$	Sampling random $x$ and solving the resulting linear system recovers $a$ in $O(1)$ expected queries, so the flat gap is exact/deterministic only; the recursive variant restores a super-polynomial bounded-error gap.

Common trapThe speedup is not "evaluating f on all inputs at once"

The tempting story — "the quantum computer tries all $2^n$ inputs in superposition, so of course it is faster" — is wrong and actively misleading. After the oracle the register holds $\tfrac{1}{\sqrt{2^n}}\sum_x(-1)^{a\cdot x}|x\rangle$ , in which every basis state has probability exactly $2^{-n}$ : measuring there gives a uniformly random string and reveals nothing about $a$ . Quantum parallelism alone buys you nothing measurable. The entire advantage is the second Hadamard layer, whose interference converts the invisible phase pattern $(-1)^{a\cdot x}$ into a single peaked amplitude at $|a\rangle$ . A second caution concerns the size of the win: the dramatic $n$ -versus- $1$ query gap is a statement about the exact, deterministic model. In the randomized, bounded-error model a classical algorithm solves the flat problem in $O(1)$ expected queries by random sampling plus Gaussian elimination, so flat Bernstein–Vazirani does not separate bounded-error complexity classes. The genuine super-polynomial separation is the recursive Bernstein–Vazirani (recursive Fourier sampling) problem from the same 1993 paper.

Worked examples

1 · Reading a = 101 in a single query (fully worked)

Take $n=3$ and hidden string $a=101$ . Run the full circuit $H^{\otimes3}U_fH^{\otimes3}$ on $|000\rangle|1\rangle$ and show the measurement returns $101$ deterministically.

Step 1. First Hadamard layer. Starting from $|000\rangle$ , $H^{\otimes3}$ builds the equal superposition $\tfrac{1}{\sqrt8}\sum_{x}|x\rangle$ over all eight strings $x\in\{000,\dots,111\}$ , each amplitude $1/\sqrt8\approx\mathbf{0.354}$ . The ancilla, prepared as $H|1\rangle=|-\rangle$ , is ready for kickback.

Step 2. Oracle query. With $a=101$ the parity is $a\cdot x=x_2\oplus x_0$ (bits at the positions where $a$ is 1). Phase kickback stamps $(-1)^{a\cdot x}$ on each term, giving the sign pattern over $x=000,001,010,011,100,101,110,111$ of $+,-,+,-,-,+,-,+$ . The state is now $\tfrac{1}{\sqrt8}\big(|000\rangle-|001\rangle+|010\rangle-|011\rangle-|100\rangle+|101\rangle-|110\rangle+|111\rangle\big)|-\rangle$ . All magnitudes are still $0.354$ ; only signs distinguish it from the pre-oracle state.

Step 3. Second Hadamard layer. The amplitude of outcome $z$ is $\tfrac{1}{8}\sum_x(-1)^{a\cdot x}(-1)^{x\cdot z}=\tfrac{1}{8}\sum_x(-1)^{(a\oplus z)\cdot x}$ . Test two cases. For $z=101=a$ : $a\oplus z=000$ , so every term is $+1$ and the sum is $8$ , giving amplitude $\tfrac{1}{8}\cdot 8=\mathbf{1}$ . For, say, $z=001$ : $a\oplus z=100\neq0$ , so half the terms are $+1$ and half $-1$ , the sum is $0$ , and the amplitude is $\mathbf{0}$ .

Step 4. Measure. Every $z\neq101$ amplitude vanishes by the same cancellation, so the state is exactly $|101\rangle$ . The measurement returns $101$ with probability $1$ , recovering the full 3-bit secret in one oracle call — where a classical solver would need three (probing $e_1,e_2,e_3$ ).

2 · Query accounting for a 20-bit secret (classical vs. quantum)

A hidden string has $n=20$ bits, e.g. $a=10110011010011101001$ . Compare the deterministic classical query cost with the quantum cost, and state what a measurement yields in each shot.

Step 1. Classical, worst case. Each query returns one parity bit $a\cdot x$ . To pin down a 20-dimensional vector over $\mathbb{F}_2$ you need 20 linearly independent equations; the simplest choice probes the basis vectors $e_1,\dots,e_{20}$ , so that query $k$ returns $f(e_k)=a_k$ directly. Deterministic classical cost: $q=n=20$ queries, one per bit.

Step 2. Quantum. The circuit $H^{\otimes20}U_fH^{\otimes20}$ prepares the equal superposition over all $2^{20}=1{,}048{,}576$ strings, applies the oracle once, and inverts the transform. The output register is exactly $|a\rangle=|10110011010011101001\rangle$ . Quantum cost: $q=1$ query, and the single measurement returns all 20 bits at once, deterministically.

Step 3. The honest caveat. If instead of exact determinism we allow a small error probability, a randomized classical algorithm can pick $\sim20$ random inputs $x$ , collect the parities, and solve the linear system by Gaussian elimination — recovering $a$ with high probability in $O(1)$ rounds of parallel sampling. So the clean $20$ -to- $1$ statement is about the exact deterministic model; the quantum win over even randomized classical querying is the recursive variant, not this flat one.

Physics of the portrait

The algorithm carries two names, but its intellectual center of gravity is the framework it was born inside — the theory of quantum complexity, which asked for the first time not just can a quantum computer do something, but how much faster than a classical one, made rigorous.

Origins · 1 minUmesh Vazirani and how this was discovered

Umesh Vazirani

computational complexity, UC Berkeley · co-author of the 1993 algorithm and co-definer of the class BQP

Umesh Vazirani is one of the founders of quantum computational complexity theory and, through decades at UC Berkeley, an advisor to a large fraction of the field. Trained under Manuel Blum, he first made his name in classical theory — randomized algorithms, expander graphs, and the widely used algorithms textbook he wrote with Dasgupta and Papadimitriou. His decisive contribution to quantum computing came in 1993 with his PhD student Ethan Bernstein: the paper "Quantum Complexity Theory," presented at STOC and expanded in SIAM J. Comput. (1997). That paper did three lasting things. It defined the class BQP — the problems a quantum computer solves efficiently with bounded error — and showed it is robust, giving quantum computing a complexity-theoretic home. It constructed the universal quantum Turing machine rigorously. And it introduced the hidden-linear-string problem solved here, together with its recursive Fourier-sampling variant, exhibiting the first super-polynomial oracle separation between quantum and classical computation. The flat algorithm — a Hadamard sandwich around one oracle call — is a corollary, but its clarity made it the standard classroom gateway to quantum speedups. Vazirani's fingerprints are everywhere downstream: Simon's algorithm, which he helped shepherd, directly inspired Shor's factoring algorithm the following year, so the line from this modest one-query trick to the breaking of RSA runs straight through his group at Berkeley.

History

1985

— Deutsch poses the first quantum–classical query separation on one qubit

1992

— Deutsch and Jozsa extend it to n qubits, distinguishing constant from balanced functions

1993

— Bernstein and Vazirani present the hidden-string algorithm and define the class BQP at STOC

1994

— Simon's period-finding algorithm and then Shor's factoring algorithm build on Fourier sampling

1997

— the full journal version appears in SIAM Journal on Computing, with the recursive separation

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, §1.4.3–1.4.4 (the hidden-string / Deutsch–Jozsa circuit) · Bernstein & Vazirani, "Quantum Complexity Theory," SIAM J. Comput. 26(5):1411–1473 (1997), orig. STOC 1993 · Preskill, Lecture Notes for Physics 219, Ch. 6 (quantum algorithms) · Watrous, The Theory of Quantum Information and lecture notes on query algorithms · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, §13 (abelian HSP) · Mermin, Quantum Computer Science, Ch. 2. The orthogonality relation $\sum_x(-1)^{b\cdot x}=2^n\delta_{b,0}$ is character orthogonality on $(\mathbb{Z}_2)^n$ . Key checkpoints: (i) the phase-kickback identity $U_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle$ from equation (2); (ii) the four-line circuit evolution ending in $|a\rangle$ ; (iii) the worked case $n=3,\ a=101$ , where the signed amplitudes $1/\sqrt{8}$ with signs $+\,-\,+\,-\,-\,+\,-\,+$ Walsh-transform to a unit peak at $|101\rangle$ ; (iv) the classical rank bound $q\ge n$ and the matching basis-probing strategy. The query-complexity claims — one quantum vs. $n$ exact classical, the $O(1)$ randomized-classical solvability of the flat problem, and the super-polynomial separation only in the recursive variant — are from Bernstein & Vazirani (1997). No empirical constants are quoted.

Prerequisites. Quantum Parallelism and the Oracle Model · Deutsch's Algorithm · Deutsch–Jozsa Algorithm. Leads to. Simon's Algorithm · Quantum Fourier Transform · Hidden Subgroup Problem · Shor's Factoring Algorithm.

Ask the tutor: ask me to trace the circuit for any hidden string $a$ you pick, show the character sum cancelling a wrong outcome to zero, or explain how the same Fourier-sampling idea grows into Simon's and Shor's algorithms.

Is Bernstein–Vazirani really an "exponential" speedup?

It depends on how you count and which classical model you compare against. In the exact, deterministic query model the gap is $1$ quantum query versus $n$ classical queries — the quantum cost is independent of the secret's length while the classical cost grows with it. That is a dramatic and unbounded query gap, and it is the honest headline. But it is only linear in $n$ , not exponential in the usual runtime sense, and crucially a randomized classical algorithm cracks the flat problem in $O(1)$ expected queries by sampling and Gaussian elimination. So flat BV does not separate the bounded-error complexity classes BPP and BQP. The genuinely exponential (super-polynomial) separation is the recursive Bernstein–Vazirani problem from the same paper, which resists the randomized shortcut.

Why prepare the ancilla in the minus state rather than zero?

Because the minus state $|-\rangle$ is an eigenvector of the oracle's bit-flip action, and that is what converts the oracle from something that writes an answer into a scratch register into something that stamps a phase on the query register. Concretely, $U_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle$ : the ancilla comes out unchanged and the sign $(-1)^{f(x)}$ appears on the query term. If you instead used $|0\rangle$ , the oracle would entangle the answer qubit with the query register, and the phases the algorithm needs would never appear where the Hadamards can act on them. You get $|-\rangle$ for free by starting the ancilla in $|1\rangle$ and Hadamarding it alongside the query qubits. This "phase kickback" is the shared trick behind Deutsch, Deutsch–Jozsa, and Grover.

Where exactly does the probability-1 certainty come from?

From perfect destructive interference, guaranteed by character orthogonality. After the second Hadamard layer, the amplitude of a candidate outcome $z$ is $\tfrac{1}{2^n}\sum_x(-1)^{(a\oplus z)\cdot x}$ . When $z=a$ the exponent $(a\oplus z)\cdot x$ is zero for every $x$ , so all $2^n$ terms are $+1$ and add up to full weight — amplitude exactly $1$ . When $z\neq a$ the string $a\oplus z$ is nonzero, and for a nonzero string precisely half of the inputs give $+1$ and half give $-1$ , so the terms cancel in exact pairs to zero. There is no leftover amplitude, no small error term, no need to repeat: the ideal circuit returns $a$ on the first and only shot. Any deviation you see on real hardware is noise, not the algorithm.

The circuit is identical to Deutsch–Jozsa — so what is different?

The hardware and the circuit are the same $H^{\otimes n}U_fH^{\otimes n}$ ; what differs is the promise on $f$ and what you do with the measured bits. Deutsch–Jozsa promises $f$ is either constant or balanced and asks a one-bit question — is the outcome the all-zeros string or not? Bernstein–Vazirani makes the stronger promise that $f$ is linear, $f(x)=a\cdot x$ , and then reads the entire measured bitstring as the hidden $a$ . So BV extracts $n$ bits of information where DJ extracts one, and it does so precisely because the linear promise makes the post-Hadamard state a single clean basis state $|a\rangle$ rather than merely " $0^n$ or not." BV is, in effect, the same experiment interrogated more finely.

Can the oracle really be built without knowing a?

Yes — that is the whole point of the black-box model, and it is not a cheat. The oracle is a fixed circuit that someone (or some physical process) has wired up to compute $f(x)=a\cdot x$ for a specific $a$ ; concretely, $U_f$ is just a set of CNOT gates, one from each query qubit where $a_i=1$ into the answer qubit. The person running Bernstein–Vazirani is given this circuit as a sealed box and is not told $a$ — their job is to discover it by querying. The algorithm never inspects the oracle's internals; it only feeds in a superposition and reads the output. This is exactly the setting in which "one query" is a meaningful and fair measure of cost, and it is why BV is a statement about query complexity rather than about circuit construction.

How does this little algorithm connect to Shor's factoring algorithm?

Through Fourier sampling and the hidden subgroup problem. The Hadamard layer in Bernstein–Vazirani is the quantum Fourier transform over the group $(\mathbb{Z}_2)^n$ , and the oracle's phase $(-1)^{a\cdot x}$ is a single character of that group; the algorithm works by sampling that character and reading off which one it is. Replace $(\mathbb{Z}_2)^n$ with the cyclic group $\mathbb{Z}_N$ and the Walsh–Hadamard transform with the full QFT, and the same "prepare a periodic/character state, Fourier-transform, measure" recipe becomes phase estimation and period finding — the engine of Shor's algorithm. Bernstein–Vazirani and its sibling Simon's algorithm are the abelian base cases; Shor is the same idea deployed on the group that encodes modular exponentiation. Learning BV first is why the QFT-based algorithms later feel inevitable rather than magical.