Bernstein–Vazirani Algorithm

The Bernstein–Vazirani algorithm recovers an unknown $n$-bit word $s$ from a function promised to satisfy $f_s(x)=s\cdot x$, with the dot product evaluated modulo two. A quantum query encodes each bit of $s$ as the sign of a single-qubit superposition. Hadamards then turn those signs into the readable word $s$.

One exact quantum query suffices, while matched classical value queries require $n$ for worst-case error below $1/2$. This is a linear query separation in $n$; it excludes the cost of constructing and implementing the oracle. The unknown-offset variant $s\cdot x\oplus c$ has the same quantum decoder but a different classical count, derived below.

Helpful background. Phase kickback explains the minus-state answer register. Quantum oracles defines coherent value access, and query complexity distinguishes queries from gates and fixes the error convention.

The hidden linear function

Fix $n\ge1$, write $N=2^n$, and let the hidden word be

$$s=(s_1,\ldots,s_n)\in\{0,1\}^n.$$

The oracle is selected from the family

$$f_s:\{0,1\}^n\longrightarrow\{0,1\}, \qquad f_s(x)=s\cdot x =\bigoplus_{j=1}^n s_jx_j.$$

The dot is the mod-two inner product, and the required output is the full $n$-bit label $s$. There are exactly $2^n$ legal functions. Indeed, distinct words give distinct functions because $f_s(e_j)=s_j$ on the $j$th standard basis word $e_j$.

The intercept is anchored to zero. Linearity is promised by the instance supplier; the algorithm neither tests that promise nor learns an arbitrary $N$-entry truth table. The address length $n$ and truth-table size $N$ describe different scales, and a comparison stated in one variable must not be silently restated in the other.

One-query recovery of the hidden word

The complete supplied oracle acts on the data register followed by an answer qubit:

$$O_s|x,b\rangle=|x,b\oplus(s\cdot x)\rangle.$$

Preparing the answer in $|{-}\rangle$ gives $O_s|x\rangle|{-}\rangle=(-1)^{s\cdot x}|x\rangle|{-}\rangle$. The target returns unchanged. A rule specified only for target $|0\rangle$ would not suffice to determine this action on a superposition.

The full sequence is

$$\begin{aligned} |0^n\rangle|1\rangle &\xrightarrow{H^{\otimes(n+1)}}\frac1{\sqrt N}\sum_x|x\rangle|{-}\rangle\\ &\xrightarrow{O_s}\frac1{\sqrt N}\sum_x(-1)^{s\cdot x}|x\rangle|{-}\rangle\\ &\xrightarrow{H^{\otimes n}\otimes I}|s\rangle|{-}\rangle. \end{aligned}$$

Measure the data qubits to read $s$. It is the same gate sequence as the Deutsch–Jozsa circuit, but now every output bit is used, rather than just testing whether all are zero.

Reading the signs one qubit at a time

The character state immediately after the oracle factors:

$$\frac1{\sqrt N}\sum_x(-1)^{s\cdot x}|x\rangle =\bigotimes_{j=1}^n\frac{|0\rangle+(-1)^{s_j}|1\rangle}{\sqrt2}.$$

For each $j$, this factor is $|+\rangle$ if $s_j=0$ and $|{-}\rangle$ if $s_j=1$. Since $H|+\rangle=|0\rangle$ and $H|{-}\rangle=|1\rangle$, the final Hadamards read all the signs. This makes the exact decoder especially transparent. Measuring before the Hadamards would instead give uniform random data bits.

The character-sum proof

For $x,y\in\{0,1\}^n$, the data transform obeys

$$H^{\otimes n}|x\rangle =\frac1{\sqrt N}\sum_y(-1)^{x\cdot y}|y\rangle.$$

The amplitude of $|y\rangle$ after the final layer is therefore

$$A_s(y) =\frac1N\sum_{x\in\{0,1\}^n} (-1)^{x\cdot(s\mathbin\oplus y)}.$$

The sum factors coordinate by coordinate:

$$\begin{aligned} A_s(y) &=\prod_{j=1}^n \left[ \frac12\sum_{x_j=0}^1 (-1)^{x_j(s_j\mathbin\oplus y_j)} \right]\\ &=\prod_{j=1}^n\delta_{s_j,y_j} =\delta_{y,s}. \end{aligned}$$

Each one-bit factor is one when $s_j=y_j$ and zero otherwise. Hence the data state is exactly $|s\rangle$, its norm is one, and measurement returns the full hidden word with probability one.

No zero-query exact algorithm can distinguish the legal outputs. Under the never-wrong fixed-cap convention, a zero-query procedure cannot name any particular $s$ without erring on another instance, so it must always declare failure; that violates the allowed inconclusive-probability cap. Consequently, for $0\le\varepsilon<1/2$,

$$Q_E(\mathrm{BV}_n) =Q_0(\mathrm{BV}_n) =Q_\varepsilon(\mathrm{BV}_n) =1.$$

Across the full bounded-error range, a zero-query output distribution is independent of $s$. Its worst-case success is at most $2^{-n}$, attained by a uniform guess. Thus $Q_\varepsilon=0$ exactly when $1-\varepsilon\le2^{-n}$; otherwise the one-query decoder is necessary and sufficient.

The same circuit has a diagnostic meaning off promise. For an arbitrary Boolean $g$,

$$\Pr(Y=y) =\left| \frac1N\sum_x(-1)^{g(x)+x\cdot y} \right|^2.$$

If $g$ differs from $s\cdot x\mathbin\oplus c$ at exactly $d$ truth-table addresses, then the amplitude at $s$ is $(-1)^c(1-2d/N)$ and

$$\Pr(Y=s)=\left(1-\frac{2d}{N}\right)^2.$$

This identity diagnoses one Walsh coefficient. It is not a test of linearity, a nearest-codeword theorem, or a guarantee for an unspecified noisy oracle.

Classical queries and the full-word requirement

Basis queries and the rank lower bound

Classically, query the standard basis words in order:

$$e_1=(1,0,\ldots,0), \quad \ldots,\quad e_n=(0,\ldots,0,1).$$

The returned values are

$$f_s(e_j)=s\cdot e_j=s_j,$$

so $n$ value queries reconstruct the complete word. If the access model permits parallel calls, all $n$ addresses can be queried in one round, but the total remains $n$ queries. Query count and query-round depth are separate resources.

The matching lower bound survives adaptivity. Fix any branch of a deterministic decision tree after $q<n$ queries, and put its queried address rows into a matrix $M\in\mathbb F_2^{q\times n}$. Since $\operatorname{rank}M\le q<n$, there is a nonzero $d\in\ker M$. The two hidden words $s$ and $s\mathbin\oplus d$ give identical answers to every address on the branch:

$$x_i\cdot(s\mathbin\oplus d) =x_i\cdot s \qquad (i=1,\ldots,q).$$

Inductively they therefore cause the adaptive algorithm to choose the same later addresses and reach the same leaf, yet the leaf cannot output both words. Thus $D(\mathrm{BV}_n)\ge n$, and the basis schedule attains equality. Thus

$$D(\mathrm{BV}_n)=n.$$

Allowing a chance of error

The deterministic rank argument establishes exact recovery. A complete bounded-error comparison follows from the number of distinguishable transcripts.

Choose $s$ uniformly from its $2^n$ possibilities and fix a deterministic classical tree with query cap $q$. It has at most $2^q$ answer transcripts and can name at most one hidden word correctly at each leaf. Its average success is therefore at most $2^q/2^n$. By Yao’s minimax principle, no randomized algorithm can have larger worst-case success.

The bound is attainable for every $0\le q\le n$. Query $q$ independent standard-basis directions, record those $q$ bits of $s$, and guess the remaining $n-q$ bits uniformly. Every hidden word is then recovered with probability $2^{-(n-q)}$. Hence the exact minimax curve is

$$S^*_{n,q}=2^{q-n}, \qquad e^*_{n,q}=1-2^{q-n}, \qquad 0\le q\le n.$$

For every $0\le\varepsilon<1/2$, a cap of $n-1$ queries has optimal error $1/2$ and therefore fails the strict requirement. Thus

$$R_\varepsilon(\mathrm{BV}_n)=n, \qquad 0\le\varepsilon<\frac12,$$

while $n-1$ queries suffice at the excluded boundary $\varepsilon=1/2$. In particular,

$$Q_E=1 \quad\text{versus}\quad D=R_{1/3}=n.$$

This is a factor-$n$, or linear, query separation in hidden-word length. Since $n=\log_2N$, it is logarithmic rather than exponential in truth-table size. The theorem says nothing by itself about gate count, total runtime, energy, physical error correction, or a separation of uniform complexity classes.

What changes with an unknown intercept?

Now define a separate family with an unknown intercept,

$$f_{s,c}(x)=s\cdot x\mathbin\oplus c, \qquad c\in\{0,1\},$$

while continuing to ask only for $s$. Kickback adds the common sign $(-1)^c$, so the modern circuit ends in

$$(-1)^c|s\rangle|{-}\rangle.$$

Measurement still returns $s$ exactly after one query. The intercept is an unobservable global sign in this circuit and is not part of the reported output.

The matched classical problem has changed. Querying $0^n$ reveals $c$, after which $n$ standard-basis queries reveal $s$, for an upper bound of $n+1$. Equivalently, $q$ value equations contain at most $q-1$ independent differences that eliminate the common nuisance intercept.

With no query, exact recovery is plainly impossible. For a deterministic lower bound with $1\le q<n+1$, augment each queried address row to $(x_i,1)\in\mathbb F_2^{n+1}$. The resulting matrix has a nonzero kernel vector $(d,\delta)$. Its word component must satisfy $d\ne0$, because every augmented query row has inner product one with $(0,1)$, so $(0,1)$ is not in the kernel. The parameter pairs $(s,c)$ and $(s\mathbin\oplus d,c\mathbin\oplus\delta)$ then follow the same adaptive transcript but require different word outputs. Therefore exact recovery needs $n+1$ calls.

The full randomized curve exposes the extra query. With no answers, uniformly guessing $s$ succeeds with probability $2^{-n}$. For $q\ge1$, pad every early-stopping branch of a deterministic capped tree with arbitrary queries; this preserves its output and success while giving a nonempty transcript at every leaf. The resulting tree has at most $2^q$ leaves, and at a fixed transcript a proposed word determines at most one consistent intercept, hence at most one parameter pair $(s,c)$. Under the uniform distribution on the $2^{n+1}$ pairs, average success is at most $2^{q-n-1}$. Querying $0^n$, learning $q-1$ independent bits of $s$, and guessing the rest attains that bound. Thus

$$S^{*,\mathrm{aff}}_{n,0}=2^{-n},$$

and

$$S^{*,\mathrm{aff}}_{n,q}=2^{q-n-1}, \qquad 1\le q\le n+1.$$

Consequently,

$$D(\mathrm{BV}^{\mathrm{aff}}_n) =R_\varepsilon(\mathrm{BV}^{\mathrm{aff}}_n) =n+1, \qquad 0\le\varepsilon<\frac12.$$

The primary anchored problem has classical cost $n$; this affine variant has cost $n+1$ under the complete value-query convention. Combining the affine promise with the anchored classical bound would compare different tasks.

Four-bit worked example

Take $s=1011$ and $c=1$. In lexicographic address order 0000 through 1111, the affine truth table is 1001100101100110. The post-query data state is

$$-|{-}\rangle|+\rangle|{-}\rangle|{-}\rangle,$$

so the final Hadamards give $-|1011\rangle$. The common minus sign changes no outcome probability. Equivalently, its unnormalized Walsh coefficients vanish except for $W(1011)=-16$.

For comparison, the optimal classical success probabilities are:

Query cap	Known zero intercept	Unknown intercept
$0$	$1/16$	$1/16$
$1$	$1/8$	$1/16$
$2$	$1/4$	$1/8$
$3$	$1/2$	$1/4$
$4$	$1$	$1/2$
$5$	$1$	$1$

At cap five, the known-intercept procedure can simply stop after four calls. One quantum query succeeds with probability one in either column. Changing whether $c$ is known changes the classical information obtainable from an answer; it does not change the required output word.

Implementation and separability

The ideal circuit uses $n+1$ visible qubits and $2n+1$ Hadamards if the answer starts in $|1\rangle$. An all-zero initialization adds one $X$. Any oracle workspace, oracle gates and output-reading cost must be included in an implementation. Parallel Hadamard layers do not make the entire calculation constant-time.

The displayed data and answer states are products throughout the algorithm’s gate-layer boundaries. This example therefore does not require entangled boundary states. A particular oracle decomposition may create intermediate entanglement; the result makes no general claim about entanglement in quantum computing.

A transparent realization of an affine oracle is

$$X_B^c\prod_{j:s_j=1}\operatorname{CNOT}_{X_j\to B}.$$

It uses $\operatorname{wt}(s)$ CNOTs and, when $c=1$, one target $X$. With this minus-state target, every CNOT acts as a local sign change on its control at the gate boundaries. The wiring itself displays the bits of $s$, so a prepared demonstration tests the coherent decoder rather than discovering a secret inaccessible to the circuit designer.

Bernstein and Vazirani introduced the construction in their 1993 complexity work, expanded in 1997. Cleve and collaborators’ 1997 preprint, published in 1998, gives the familiar one-XOR-query refinement. Their broader recursive Fourier-sampling setting must be distinguished from the elementary one-versus-$n$ problem here. See quantum complexity classes for the role of oracle separations.

Finally, the transform here is Fourier analysis over $(\mathbb Z_2)^n$, namely $H^{\otimes n}$. It is not the cyclic transform $F_{2^n}$ from the quantum Fourier transform page. The groups have different characters even though their Hilbert spaces have the same dimension.

Exercises

Count the linear and affine families

Count the anchored linear functions and the affine parameter pairs. Prove that their parameters are unique, and explain which family defines the primary problem.

Solution

Each $s\in\{0,1\}^n$ defines one anchored function $f_s(x)=s\cdot x$. If $f_s=f_t$, evaluating on every $e_j$ gives $s_j=t_j$, so $s=t$. There are therefore $2^n$ distinct anchored functions.

For the affine family, $f_{s,c}(0^n)=c$ determines the intercept, and then

$$f_{s,c}(e_j)\mathbin\oplus f_{s,c}(0^n)=s_j$$

determines every word bit. Thus all $2^{n+1}$ pairs $(s,c)$ define distinct functions. The primary Bernstein–Vazirani problem uses only the $2^n$ functions with $c=0$; the unknown-intercept family is a separate query problem.

Recover the word with basis queries

Give the classical basis-query schedule, prove that it recovers $s$, and distinguish total query count from parallel query rounds.

Solution

For $j=1,\ldots,n$, query $e_j$. The answer is

$$f_s(e_j)=\bigoplus_{k=1}^n s_k(e_j)_k=s_j.$$

Writing the returned bits in coordinate order therefore gives $s$ after exactly $n$ queries. In a sequential model this takes $n$ query rounds. If independent simultaneous oracle calls are available, the addresses can be submitted in one round, but the algorithm still consumes $n$ calls and $n$ returned bits. Parallel depth does not change total query complexity.

Verify Boolean phase kickback

Apply the complete XOR oracle to $|{-}\rangle$, prove target return and factorization for a data superposition, and determine the effect of an affine intercept.

Solution

For one basis address,

$$\begin{aligned} O_s|x\rangle|{-}\rangle &=\frac{|x,s\cdot x\rangle-|x,1\oplus s\cdot x\rangle}{\sqrt2}\\ &=(-1)^{s\cdot x}|x\rangle|{-}\rangle. \end{aligned}$$

Linearity gives

$$O_s\left(\sum_x\alpha_x|x\rangle\right)|{-}\rangle =\left(\sum_x\alpha_x(-1)^{s\cdot x}|x\rangle\right)|{-}\rangle.$$

The same answer state factors from every term. Replacing the function by $s\cdot x\oplus c$ multiplies the entire data factor by $(-1)^c$, so the target still returns and the intercept becomes one unobservable global sign.

Prove character orthogonality

Derive the coordinate product for $A_s(y)$, prove normalization and exact decoding, and connect the qubitwise factorization to Tensor Products as the general product-space construction.

Solution

Substituting the Hadamard matrix elements gives

$$A_s(y)=\frac1N\sum_x(-1)^{x\cdot(s\oplus y)}.$$

Because both the sum and exponent separate by coordinate,

$$\begin{aligned} A_s(y) &=\prod_{j=1}^n \frac12\sum_{x_j=0}^1(-1)^{x_j(s_j\oplus y_j)}\\ &=\prod_{j=1}^n\delta_{s_j,y_j} =\delta_{s,y}. \end{aligned}$$

Hence $\sum_y|A_s(y)|^2=1$ and $\Pr(Y=s)=1$. The same calculation at the state level is

$$\frac1{\sqrt N}\sum_x(-1)^{s\cdot x}|x\rangle =\bigotimes_{j=1}^n \frac{|0\rangle+(-1)^{s_j}|1\rangle}{\sqrt2}.$$

The tensor product constructs the joint space and distributes the coordinate factors; it does not assert that arbitrary multipartite states factor this way.

Prove the deterministic lower bound

Use rank and a nonzero nullspace word to construct indistinguishable secrets after every adaptive transcript of length $q<n$.

Solution

Fix the addresses $x_1,\ldots,x_q$ selected along one actual decision-tree branch and form the matrix $M$ with these rows. Since $\operatorname{rank}M\le q<n$, choose $d\ne0$ with $Md=0$.

For every query already made,

$$x_i\cdot(s\oplus d) =x_i\cdot s\oplus x_i\cdot d =x_i\cdot s.$$

The equal answers force the deterministic algorithm to choose the same next address on both secrets, so induction preserves the common branch. The leaf then sees one transcript for the two distinct required outputs $s$ and $s\oplus d$ and must fail on at least one. No exact deterministic tree of depth below $n$ exists; combined with basis queries, $D=n$.

Derive the randomized minimax curve

Prove matching upper and lower bounds for $S^*_{n,q}$, reproduce the $n=4$ sequence, and obtain $R_\varepsilon=n$ for $\varepsilon<1/2$.

Solution

Under uniform $s$, a deterministic depth-$q$ tree has at most $2^q$ leaves. Each leaf announces one word and can be correct for at most that one member of the $2^n$-word family, so its average success is at most $2^{q-n}$. Yao’s principle transfers this bound to the worst-case success of randomized algorithms.

Querying $q$ independent basis directions and guessing the remaining bits uniformly attains success $2^{-(n-q)}$ on every $s$. Therefore

$$S^*_{n,q}=2^{q-n}, \qquad e^*_{n,q}=1-2^{q-n}.$$

For $n=4$ and $q=0,1,2,3,4$, the successes are

$$\frac1{16},\quad\frac18,\quad\frac14,\quad\frac12,\quad1.$$

Every cap below four has error at least $1/2$, whereas four queries give zero error. Hence $R_\varepsilon(\mathrm{BV}_4)=4$ for $\varepsilon<1/2$, and the same argument gives $R_\varepsilon(\mathrm{BV}_n)=n$ generally.

Account for an unknown intercept

Derive the $n+1$ classical schedule and exact affine success curve. Explain why the quantum output is unchanged and why the anchored $n$-query equality no longer applies.

Solution

Query $0^n$ to obtain $c$, then query every $e_j$ and compute

$$s_j=f_{s,c}(e_j)\oplus c.$$

This uses $n+1$ calls. With no query, uniform guessing of $s$ succeeds with probability $2^{-n}$. For $q\ge1$, pad early-stopping branches with arbitrary queries so every leaf has a nonempty transcript. There are then at most $2^q$ leaves, and a fixed transcript plus proposed word determines at most one intercept, so it can be correct for at most one parameter pair. The upper bound $2^{q-n-1}$ is attained by learning $c$, then $q-1$ word bits, and guessing the rest. Thus

$$S^{*,\mathrm{aff}}_{n,0}=2^{-n}, \qquad S^{*,\mathrm{aff}}_{n,q}=2^{q-n-1} \quad(1\le q\le n+1).$$

The quantum character acquires only $(-1)^c$ and still decodes to $s$ in one query. The classical oracle returns ordinary values, so it must eliminate the unknown intercept; the anchored equality $D=n$ is therefore inapplicable.

Flip one truth-table value

For $n=4$, change one value of $f_s(x)=s\cdot x$ at address $x_0$. Calculate the probability of decoding $s$ and the probability of each other word. Explain why repeated sampling still does not by itself certify linearity.

Solution

Changing one sign changes every Walsh amplitude by a term of magnitude $2/16$. More explicitly,

$$A_g(y)=\delta_{y,s}-\frac18(-1)^{x_0\cdot(s\oplus y)}.$$

Thus $A_g(s)=7/8$ and every other amplitude has magnitude $1/8$. The correct-word probability is $49/64$, with probability $1/64$ on each of the other fifteen words; the probabilities sum to one. This is a fixed coherent Boolean-function change, not an independent random bit flip on each invocation. Observing $s$ repeatedly can be likely for both this imperfect function and the exact linear one. A statistical test needs a specified alternative, number of trials and tolerated error.

References

• E. Bernstein and U. Vazirani, “Quantum Complexity Theory,” in Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 11–20 (1993), doi:10.1145/167088.167097.
• E. Bernstein and U. Vazirani, “Quantum Complexity Theory,” SIAM Journal on Computing 26, 1411–1473 (1997), doi:10.1137/S0097539796300921.
• R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, “Quantum Algorithms Revisited,” Proceedings of the Royal Society A 454, 339–354 (1998), doi:10.1098/rspa.1998.0164.
• D. A. Meyer, “Sophisticated Quantum Search without Entanglement,” Physical Review Letters 85, 2014–2017 (2000), doi:10.1103/PhysRevLett.85.2014.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press (2010), doi:10.1017/CBO9780511976667.