Bernstein–Vazirani Algorithm

The Bernstein–Vazirani problem supplies a Boolean function promised to have the anchored linear form $f_s(x)=s\cdot x$ and asks for the entire unknown word $s\in\{0,1\}^n$. Given a complete coherent XOR oracle, the modern quantum circuit recovers $s$ exactly with one query. Matched classical value queries require $n$: querying the standard basis reads the $n$ bits, and no exact or ordinary bounded-error algorithm can use fewer in the worst case.

This is a factor-$n$ query separation in the hidden-word length, not an exponential separation in $n$, a runtime theorem, or a practical application. Bernstein and Vazirani introduced the construction within a broader complexity-theoretic argument in 1993; the familiar one-XOR-query network is the 1998 reconstruction by Cleve, Ekert, Macchiavello, and Mosca. Oracle construction and every nonquery implementation cost remain outside the one-query statement.

Required background. Quantum Oracles supplies the complete coherent interface and its construction boundary. Phase Kickback supplies the general eigenstate-to-phase transduction theorem and the target-return condition instantiated below.

Helpful background. The Quantum Algorithms and Complexity guide supplies the common claim record; Algorithmic Primitives supplies the access–phase–interference–readout vocabulary; Query Complexity fixes the query and error conventions; and the Deutsch–Jozsa Algorithm gives the neighboring decision problem built from the same transform skeleton.

The Hidden Linear Function Promise

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.

The Ten-Field Bernstein–Vazirani Claim Record

The common record makes the theorem auditable before its derivation. An excluded cost is recorded as unspecified, not as zero.

1. Problem family and size. The family is $\mathrm{BV}_n$ for $n\ge1$, with a hidden $n$-bit word and a truth table of size $N=2^n$.
2. Promise and instance. The supplied function is exactly $f_s(x)=s\cdot x$ with zero intercept. The promise is on the selected oracle, and $s$ is the unknown instance parameter.
3. Access and encoding. One quantum query is the complete $(n+1)$-qubit XOR action $O_s|x,b\rangle=|x,b\mathbin\oplus(s\cdot x)\rangle$. A matched classical query returns the bit $f_s(x)$ at one chosen address.
4. Output and use. The output is the entire word $s$. It labels the promised function but is neither a dump of its $N$ values nor a certificate that an off-promise oracle is linear.
5. Success and error. The ideal quantum decoder succeeds with probability one. For $0\le\varepsilon<1/2$, its fixed-cap cost is one query, whereas the optimal classical cost is $n$.
6. Algorithmic idea. A minus-state answer qubit converts the linear Boolean value into the character $(-1)^{s\cdot x}$, and a final Hadamard transform maps that character to its label.
7. Executable procedure. Prepare $|0^n\rangle|1\rangle$, apply $H^{\otimes(n+1)}$, call $O_s$ once, apply $H^{\otimes n}$ to the data register, and measure that register to obtain $s$.
8. Resource ledger. With $|1\rangle$ supplied, count one abstract oracle call, $n+1$ visible logical qubits plus hidden workspace, $2n+1$ Hadamards, $n$ measured data qubits, and one ideal run. Oracle realization and physical costs are unspecified.
9. Classical comparator. Standard-basis queries attain $n$ calls, while rank and transcript arguments give $D=R_0=R_{1/3}=n$ under matched value access.
10. Evidence and limits. The state identity and query curves are exact black-box theorems, supported below by finite exhaustive checks. They imply no constant-time implementation, exponential advantage in $n$, useful application, or separation of BQP from BPP.

The remaining sections derive each entry and then reprice the distinct affine-intercept variant.

The Complete Linear XOR Oracle

Let $X$ be the $n$-qubit address register and $B$ the one-qubit answer register, with tensor order $X\otimes B$. The licensed query acts on every computational-basis state as

$$O_s|x,b\rangle =|x,b\mathbin\oplus(s\cdot x)\rangle, \qquad x\in\{0,1\}^n, \quad b\in\{0,1\}.$$

This is a permutation unitary and satisfies $O_s^\dagger=O_s$. Defining only the action on $|x,0\rangle$ would leave the coherent interface incomplete: the algorithm deliberately queries the answer register in a superposition. Self-inversion is a property of the declared map, not a license for free oracle synthesis, controlled access, hidden workspace, or other strengthened capabilities.

For

$$|{-}\rangle=\frac{|0\rangle-|1\rangle}{\sqrt2},$$

the complete action gives the specialized kickback identity

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

The answer qubit returns exactly and factors from the data register. The oracle has written a relative-phase character, not a readable list of function values. A direct phase oracle would be a different declared interface; here its action is obtained from one call to the complete XOR oracle.

Classical Basis Queries and Linear Equations

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. A zero-error randomized algorithm cannot repair this indistinguishability with random coins under the same fixed cap, so

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

The Modern One-Query Decoder

Begin with $|0^n\rangle_X|1\rangle_B$. The first Hadamard layer prepares a uniform address state and a minus-state answer qubit. One oracle call imprints the hidden linear character, and a final data Hadamard layer decodes its label:

$$\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}$$

Only the $n$ data qubits are measured. The schedule contains one abstract call to $O_s$, not one call per basis component in the superposition. Supplying the answer register as $|1\rangle$ gives $n+1$ Hadamards before the query and $n$ after it; starting instead from $|0^{n+1}\rangle$ also requires one $X$ on the answer qubit.

This circuit is an instance of the reusable access–phase–interference–readout pattern, but its deterministic output depends on the special character promise. A generic Boolean phase pattern does not decode to one basis word.

Character Orthogonality and Exact Correctness

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.

Randomized Queries and Full-Word Recovery

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_0=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.

The Affine Intercept Convention

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 unused 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_0(\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.

Resources, Separability, and Implementation Boundaries

The abstract circuit has the following ledger:

Resource	Ideal modern decoder
Boolean XOR-oracle calls	$1$
visible logical qubits	$n+1$
hidden oracle workspace	unspecified
Hadamard gates	$2n+1$ if $
additional preparation from $	0^{n+1}\rangle$
measured data qubits	$n$
ideal repetitions	$1$
oracle gates, width, depth, and cleanup	unspecified
fault-tolerant compilation and physical spacetime	unspecified
data acquisition, routing, calibration, noise, and time	unspecified

The two Hadamard layers are parallel within their registers, but total depth includes preparation, oracle implementation, interference, and readout. Circuit Model owns the larger circuit accounting framework, while Single-Qubit Gates owns the Hadamard convention used here.

The ideal post-query data state is separable:

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

Thus entanglement is not required in the displayed boundary states. That fact does not establish that every oracle decomposition or physical realization remains unentangled, nor does it show that entanglement is irrelevant to quantum speedups generally.

A transparent affine oracle can be synthesized as

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

It uses $\operatorname{wt}(s)$ CNOTs plus one answer-wire $X$ when $c=1$, and its wiring openly exposes the word. Such a compiled demonstration can test preparation, control, kickback, interference, and readout; it does not discover a secret hidden in an opaque practical data source.

Keep the accounting categories distinct:

abstract XOR-oracle queries
oracle construction gates, width, depth, and garbage cleanup
data and target preparation
nonquery logical gates and parallel depth
logical qubits and hidden workspace
output bits, measurements, repetitions, and classical decoding
fault-tolerant compilation and physical spacetime
data acquisition, routing, calibration, noise, and wall-clock time

One coherent query returns the promised $n$-bit label, not all $N$ truth-table entries. The output already contains $n$ classical bits, and the transparent realization can require $\Theta(n)$ gates. Classical Information Review owns comparisons that also price representation, memory, construction, output utility, and total cost.

Two Worked Claim Audits

Exhaustive four-bit character-decode audit

Set $n=4$, $N=16$, $s=1011$, and use the affine diagnostic $c=1$. In address order 0000, 0001, …, 1111, the truth-table word is 1001100101100110. Its unnormalized Walsh vector, ordered by $y=0000,0001,\ldots,1111$, is

$$(0,0,0,0,0,0,0,0,0,0,0,-16,0,0,0,0).$$

The final data state is $-|1011\rangle$; the sign is global and leaves the measurement deterministic.

1. Problem family and size. The audit fixes four address bits, sixteen addresses, sixteen anchored linear functions, and thirty-two affine parameter pairs.
2. Promise and instance. The displayed instance is $f_{1011,1}(x)=1011\cdot x\mathbin\oplus1$, with the stated lexicographic address order and a separately declared nonzero intercept.
3. Access and encoding. The register order is four data qubits followed by one answer qubit, and one licensed call is the complete five-qubit XOR action for the selected function.
4. Output and use. The measured output is 1011; the audit records the full ideal spectrum to verify the decoder but does not report the intercept or dump the table through measurement.
5. Success and error. Exhaustive integer arithmetic gives unit norm and probability one on the correct word for all sixteen linear instances and all thirty-two affine instances, with zero decoding failures.
6. Algorithmic idea. The integer Walsh transform converts each promised affine character into one nonzero coefficient at its word label; the intercept determines only that coefficient’s sign.
7. Executable procedure. Enumerate every $s\in\{0,1\}^4$ and both intercepts, construct each sixteen-bit table, compute all sixteen signed character sums, assert norm $16^2$, and assert a unique coefficient $(-1)^c16$ at $y=s$.
8. Resource ledger. The ideal instance uses one abstract query, five visible qubits plus hidden workspace, nine Hadamards, four measured data qubits, and one run; oracle construction remains unspecified.
9. Classical comparator. The displayed affine family would require five worst-case value queries for exact or error-below-one-half recovery, while the primary anchored family requires four.
10. Evidence and limits. This is exhaustive, integer-valued simulation with no shots or floating-point tolerance. It verifies the promised finite family and exact state calculation, not oracle opacity, device performance, or asymptotic total cost.

A compact reproduction is:

const n = 4;
const N = 1 << n;
const parity = (z) => {
  let p = 0;
  while (z) { p ^= z & 1; z >>= 1; }
  return p;
};

let linearInstances = 0;
let affineInstances = 0;
let failures = 0;
let displayedTable;
let displayedWalsh;

for (let s = 0; s < N; s++) {
  for (let c = 0; c <= 1; c++) {
    const f = (x) => parity(x & s) ^ c;
    const table = Array.from({ length: N }, (_, x) => f(x)).join('');
    const W = Array.from({ length: N }, (_, y) =>
      Array.from({ length: N }, (_, x) =>
        (f(x) ^ parity(x & y)) ? -1 : 1)
        .reduce((a, b) => a + b, 0));

    affineInstances++;
    if (c === 0) linearInstances++;
    if (W.reduce((a, v) => a + v * v, 0) !== N * N) failures++;
    if (W.some((v, y) => v !== (y === s ? (c ? -N : N) : 0))) failures++;
    if (s === 0b1011 && c === 1) {
      displayedTable = table;
      displayedWalsh = W;
    }
  }
}

if (linearInstances !== 16 || affineInstances !== 32 || failures !== 0) {
  throw Error('exhaustive audit failed');
}
if (displayedTable !== '1001100101100110') throw Error('table');
if (displayedWalsh.join(',') !== '0,0,0,0,0,0,0,0,0,0,0,-16,0,0,0,0') {
  throw Error('spectrum');
}
console.log({ linearInstances, affineInstances, failures, displayedTable, displayedWalsh });

Four-bit matched-query minimax audit

For $n=4$, the optimal classical success rows are

family	$q=0$	$q=1$	$q=2$	$q=3$	$q=4$	$q=5$
anchored linear	$1/16$	$1/8$	$1/4$	$1/2$	$1$	N/A
unknown affine intercept	$1/16$	$1/16$	$1/8$	$1/4$	$1/2$	$1$

One quantum query succeeds with probability one on either family. Three classical queries in the linear problem and four in the affine problem have optimal success only $1/2$.

1. Problem family and size. The primary audit is $\mathrm{BV}_4$ with sixteen hidden words; the separately priced affine variant has thirty-two parameter pairs but still asks only for the four-bit word.
2. Promise and instance. The first row fixes zero intercept, whereas the second permits either intercept. Every success entry is worst case over the corresponding promised family.
3. Access and encoding. Quantum access is one complete coherent five-qubit XOR call; classical access returns one function bit per selected four-bit address under the same value encoding.
4. Output and use. Both comparisons require the exact four-bit word. The affine task does not ask for its nuisance intercept.
5. Success and error. The quantum success is one. The classical rows are respectively $2^{q-4}$ for $0\le q\le4$ and $1/16$ at $q=0$, then $2^{q-5}$ for $1\le q\le5$.
6. Algorithmic idea. Character orthogonality identifies all four word bits in one coherent phase pattern; a classical transcript conveys at most one independent answer bit per query, with the affine intercept consuming the first.
7. Executable procedure. The quantum schedule uses the two Hadamard layers and one oracle call. The attaining classical schedules query independent basis words, preceded by the zero word in the affine case, and uniformly guess every unresolved bit.
8. Resource ledger. The four-bit circuit has five visible qubits plus hidden workspace, one abstract query, nine Hadamards, four data measurements, and one ideal repetition. Hidden oracle construction is unspecified, not zero.
9. Classical comparator. For the primary problem $Q_E=1$ while $D=R_0=R_{1/3}=4$. The separately qualified affine values are one quantum query and $D=R_0=R_{1/3}=5$ classical queries.
10. Evidence and limits. The two rows follow from exact rank, leaf-count, and attaining-schedule arguments. Their finite values do not turn one oracle call into one gate, establish hiddenness of compiled wiring, or measure physical runtime.

The audit makes the convention sensitivity visible: changing only whether the intercept is known changes every positive-query classical success value by a factor of two, but it changes the quantum state only by a global sign.

Historical Formulations and Canonical Ownership

The historical record has three distinct stages. Bernstein and Vazirani’s 1993 STOC paper introduced the construction within quantum complexity theory and recursive Fourier sampling; its compute–phase–uncompute presentation invoked the function operation twice. Their 1997 SIAM Journal on Computing article expanded that complexity-theoretic argument and its oracle separation. Cleve, Ekert, Macchiavello, and Mosca then presented the familiar one-XOR-query network in 1998 and explicitly treated $f_{s,c}(x)=s\cdot x\mathbin\oplus c$. The displayed one-query circuit should not be attributed verbatim to the 1993 construction.

The elementary one-level problem on this page establishes only the factor-$n$ query result. Recursive Fourier sampling and its superpolynomial relativized separation remain with the primary papers, while Quantum Complexity Classes owns the interpretation of uniform families, relativization, and class separations. The result does not prove BQP $\ne$ BPP.

The ownership seams are equally specific. Quantum Oracles owns interface theory and hidden construction assumptions; Phase Kickback owns the general transduction theorem; Algorithmic Primitives owns reusable transform language; and Query Complexity owns the general measures, Yao principle, and lower-bound toolkit. This page owns their specialization to hidden linear-word recovery. Deutsch–Jozsa Algorithm instead owns constant-versus-balanced decision over a much larger promised Boolean family.

The Hadamard transform used here is Fourier analysis over $(\mathbb Z_2)^n$. The Quantum Fourier Transform owns the cyclic transform $F_{2^n}$ and should not be substituted for this tensor-product Hadamard. Simon’s Algorithm owns another hidden-structure promise, repeated orthogonal-subspace samples, and verified binary-rank recovery; it is not a dependency of this result.

Small NMR and optical demonstrations in the references implement prepared oracle instances and test physical control. Claims, Hype, and Evidence Standards supplies the language for separating such demonstrations, exact black-box theorems, simulations, and end-to-end advantage claims.

Common Bernstein–Vazirani Failures

Widening the promise. The decoder is exact for $f_s(x)=s\cdot x$ and, up to a global sign, for the separately declared affine variant. It does not certify that an arbitrary Boolean function is linear or find a nearest linear function from one sample.

Specifying only half an oracle. A rule on $|x,0\rangle$ does not determine coherent behavior on the answer superposition. The theorem uses the complete XOR map on every $|x,b\rangle$.

Hiding the intercept convention. Anchored linear value queries cost $n$ classically; an unknown affine intercept raises that cost to $n+1$. The quantum global phase does not make the two classical problems identical.

Treating superposition as bulk readout. The query imprints one promised character and the measurement returns its $n$-bit label. It does not reveal an arbitrary $N$-entry truth table.

Calling the advantage exponential. The comparison is one versus $n$ queries, linear in $n$. Writing $n=\log_2N$ makes the same gap logarithmic in truth-table size, not exponential.

Calling one query one gate or constant time. Oracle synthesis, nonquery gates, workspace, output, routing, correction, noise, and wall-clock time remain separate. The abstract query count cannot set them to zero.

Calling transparent wiring a hidden-data search. A CNOT implementation encodes $s$ visibly in its controls. It demonstrates the circuit mechanism, not opaque discovery from a practical database.

Requiring entanglement universally. The ideal character state factors across qubits. This instance neither needs entangled boundary states nor supports a general conclusion about entanglement and quantum advantage.

Overstating history or complexity. The familiar one-query network is the 1998 reconstruction, and the elementary result is not the original recursive separation. Neither formulation proves an unrelativized separation between BQP and BPP.

Exercises

1. 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 separately priced variant.

2. 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 licensed, 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.

3. 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.

4. 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.

5. 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$.

6. 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.

7. Reprice the affine variant

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.

8. Complete a ten-field implementation audit

Audit the $n=4$ circuit, reproduce the character vector and both minimax rows, price hidden construction as unspecified, and repair the claim “Bernstein–Vazirani gives an exponential constant-time speedup.”

Solution

1. Problem family and size. The primary task is $\mathrm{BV}_4$, with four-bit words and sixteen truth-table addresses; the affine audit separately includes both intercepts.
2. Promise and instance. Use $s=1011$, fix lexicographic address order, and set $c=1$ only for the declared affine diagnostic. The primary comparison retains $c=0$.
3. Access and encoding. One quantum query is the complete five-qubit XOR unitary. One classical query returns one value at a chosen four-bit address; neither unit cost includes oracle synthesis.
4. Output and use. The required output is 1011. It identifies the promised word but does not report $c$, list sixteen values, or verify linearity.
5. Success and error. One quantum call returns the word with probability one. The primary and affine classical success rows are the exact sequences displayed immediately below.
6. Algorithmic idea. Kickback encodes the promised function as a product-group character, and character orthogonality maps the phase label to one computational-basis word.
7. Executable procedure. Prepare $|0000\rangle|1\rangle$, apply five Hadamards, make one complete XOR call, apply four data Hadamards, measure four data qubits, and compare the result with 1011.
8. Resource ledger. Count one abstract query, five visible qubits plus hidden workspace, nine Hadamards, four measurements, and one ideal run. Oracle gates, depth, cleanup, routing, error correction, and time are unspecified.
9. Classical comparator. The anchored family has $Q_E=1$ versus $D=R_0=R_{1/3}=4$; the separately declared affine family retains one quantum query but has classical value $5$.
10. Evidence and limits. The affine truth word is 1001100101100110, and its unnormalized Walsh vector is displayed below. Exhaustive integer checks cover sixteen linear and thirty-two affine instances with zero failures. This verifies an ideal finite promise calculation, not hidden oracle construction or physical advantage.

The two classical rows are

$$\begin{aligned} q=0,\ldots,4:\quad &\frac1{16},\ \frac18,\ \frac14,\ \frac12,\ 1,\\ q=0,\ldots,5:\quad &\frac1{16},\ \frac1{16},\ \frac18,\ \frac14,\ \frac12,\ 1. \end{aligned}$$

For $s=1011$ and $c=1$, the character audit gives

$$(0,0,0,0,0,0,0,0,0,0,0,-16,0,0,0,0).$$

A defensible repair is: “Given unit-cost coherent XOR access to the promised anchored family $f_s(x)=s\cdot x$, the modern circuit recovers the $n$-bit word exactly with one quantum query, whereas matched classical value-query algorithms require $n$ queries for worst-case error below one half. Oracle construction and all nonquery costs are excluded.”

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.
• J. Du, M. Shi, X. Zhou, Y. Fan, B. Ye, R. Han, and J. Wu, “Implementation of a Quantum Algorithm to Solve the Bernstein–Vazirani Parity Problem without Entanglement on an Ensemble Quantum Computer,” Physical Review A 64, 042306 (2001), doi:10.1103/PhysRevA.64.042306.
• P. Londero, C. Dorrer, M. Anderson, S. Wallentowitz, K. Banaszek, and I. A. Walmsley, “Efficient Optical Implementation of the Bernstein–Vazirani Algorithm,” Physical Review A 69, 010302(R) (2004), doi:10.1103/PhysRevA.69.010302.
• D. A. Meyer, “Sophisticated Quantum Search without Entanglement,” Physical Review Letters 85, 2014–2017 (2000), doi:10.1103/PhysRevLett.85.2014.
• A. Montanaro, “Quantum Algorithms: An Overview,” npj Quantum Information 2, 15023 (2016), doi:10.1038/npjqi.2015.23.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press (2010), doi:10.1017/CBO9780511976667.
• B. M. Terhal and J. A. Smolin, “Single Quantum Querying of a Database,” Physical Review A 58, 1822–1826 (1998), doi:10.1103/PhysRevA.58.1822.
• A. C.-C. Yao, “Probabilistic Computations: Toward a Unified Measure of Complexity,” in Proceedings of the 18th Annual Symposium on Foundations of Computer Science, 222–227 (1977), doi:10.1109/SFCS.1977.24.