The Bernstein-Vazirani Algorithm

Imagine a black box that knows a secret $n$-bit string $s = s_{n-1} \dots s_1 s_0$. You can query it: hand it any $n$-bit string $x$ and it returns the inner product $f(x) = s \cdot x = (s_{n-1} x_{n-1} + \dots + s_0 x_0) \bmod 2$. One bit out. Your job is to figure out all $n$ bits of $s$.

Classically, the strategy is obvious: send $x = 10\dots0$, $x = 010\dots0$, and so on — each query peels off one bit of $s$. After $n$ queries you know $s$ exactly. And it is provably necessary: any deterministic or randomized algorithm needs at least $n$ queries, because each query yields at most one bit of information.

A quantum computer does it in one query. This is the Bernstein-Vazirani algorithm, published by Ethan Bernstein and Umesh Vazirani in 1993 and the companion paper in 1997. It was one of the earliest demonstrations that quantum computers can solve natural problems exponentially faster than classical ones — not just asymptotically faster in an abstract setting, but with a provably exact separation: 1 versus $n$.

The trick is superposition. A quantum computer does not ask "what is $f(10\dots0)$?" and then "what is $f(010\dots0)$?" — it asks all $n$ questions simultaneously in a single coherent query, and interference does the rest.

Pick a secret bit-string (or use the random one). The oracle computes $f(x) = s \cdot x \bmod 2$. Try querying it classically — you will need one bit at a time. Then press Run quantum query to see the Hadamard trick recover all bits in one shot.

<!-- {{c_main_layout}} -->
<div class="bv-wrap">
  <div class="secret-row">
    <span class="label">{{lbl_secret}}</span>
    <div id="secret-bits" class="bit-row"></div>
    <button id="btn-random" type="button" class="ghost sm">{{btn_random}}</button>
  </div>
  <hr class="divider"/>
  <div class="panel">
    <div class="panel-head">{{lbl_classical}}</div>
    <p class="panel-desc">{{desc_classical}}</p>
    <div id="classical-queries" class="query-log"></div>
    <div class="panel-actions">
      <button id="btn-classical-step" type="button">{{btn_query_next}}</button>
      <button id="btn-classical-reset" type="button" class="ghost sm">{{btn_reset}}</button>
    </div>
    <div class="result-row" id="classical-result"></div>
  </div>
  <hr class="divider"/>
  <div class="panel">
    <div class="panel-head">{{lbl_quantum}}</div>
    <p class="panel-desc">{{desc_quantum}}</p>
    <div id="quantum-visual" class="hadamard-vis"></div>
    <div class="panel-actions">
      <button id="btn-quantum" type="button">{{btn_quantum_run}}</button>
      <button id="btn-quantum-reset" type="button" class="ghost sm">{{btn_reset}}</button>
    </div>
    <div class="result-row" id="quantum-result"></div>
  </div>
</div>

/* {{c_base_styles}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px 4px; }
.bv-wrap { max-width: 520px; margin: 0 auto; }
.secret-row { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .3rem; }
.label { font-size: .85rem; font-weight: 700; color: #444; white-space: nowrap; }
.bit-row { display: flex; gap: 4px; flex-wrap: wrap; }
/* {{c_bit_styles}} */
.bit { width: 34px; height: 34px; display: flex; align-items: center; justify-content: center;
       font: 700 16px ui-monospace, monospace; border-radius: 6px; cursor: pointer; user-select: none;
       border: 2px solid #adb1b8; background: #e4e7eb; transition: all .15s; }
.bit.on { background: #1d3557; border-color: #1d3557; color: #fff; }
.bit.off { background: #e4e7eb; color: #555; }
.divider { border: none; border-top: 1px solid #dde3ea; margin: .8rem 0; }
.panel { margin-bottom: .4rem; }
.panel-head { font-size: .9rem; font-weight: 700; color: #1d3557; margin-bottom: .2rem; }
.panel-desc { font-size: .82rem; color: #555; margin: 0 0 .4rem; line-height: 1.45; }
/* {{c_query_log_styles}} */
.query-log { font: 13px/1.55 ui-monospace, monospace; min-height: 1.6em; color: #333;
             background: #f4f6f8; border-radius: 6px; padding: .35rem .55rem; margin-bottom: .4rem; }
.q-row { display: flex; gap: .5rem; align-items: baseline; }
.q-x { color: #1d3557; }
.q-eq { color: #888; }
.q-val { color: #0a7d33; font-weight: 700; }
.panel-actions { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .3rem; }
.result-row { font-size: .9rem; font-weight: 600; min-height: 1.4em; }
.result-row.ok { color: #0a7d33; }
.result-row.progress { color: #555; }
/* {{c_hadamard_vis_styles}} */
.hadamard-vis { font: 13px/1.6 ui-monospace, monospace; background: #f4f6f8;
                border-radius: 6px; padding: .35rem .55rem; margin-bottom: .4rem; min-height: 2.5em; }
.h-step { color: #666; }
.h-step .hi { color: #1d3557; font-weight: 700; }
.h-step .hval { color: #0a7d33; font-weight: 700; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button.sm { font-size: 12px; padding: .3rem .6rem; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Notice the asymmetry. Each classical query learns exactly one bit of $s$ — and you need all $n$. The quantum query puts $x$ into uniform superposition over all $2^n$ inputs simultaneously, applies the oracle coherently, and a final Hadamard layer reads out $s$ all at once. The oracle is called once, no matter how large $n$ is.

The algorithm is three steps, each essential:

1. Prepare a uniform superposition. Apply a Hadamard gate $H$ to each of the $n$ input qubits (all starting in $|0\rangle$) and one ancilla qubit (starting in $|{-}\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$). The $n$ qubits now simultaneously represent every string $x \in \{0,1\}^n$ with equal amplitude.

2. Query the oracle. The oracle maps $|x\rangle|y\rangle \mapsto |x\rangle|y \oplus f(x)\rangle$. Because the ancilla is in state $|{-}\rangle$, the phase kickback trick applies: the net effect is $|x\rangle \mapsto (-1)^{f(x)}|x\rangle = (-1)^{s \cdot x}|x\rangle$. The oracle runs once; its output is encoded in the phases of every amplitude simultaneously.

3. Read out $s$ by a second Hadamard layer. The state after the oracle is $\frac{1}{\sqrt{2^n}}\sum_{x} (-1)^{s \cdot x}|x\rangle$. Applying $H^{\otimes n}$ transforms this to $|s\rangle$ — exactly the secret string, with probability 1. Measure and you have $s$.

Why does this work? The Hadamard transform is its own inverse on phase-encoded strings. Encoding $s$ into phases by the inner product, then transforming back, is precisely Fourier analysis over $(\mathbb{Z}/2\mathbb{Z})^n$. The phases interfere constructively at $x = s$ and destructively everywhere else.

The separation is exact and unconditional. Classically, $n$ queries are necessary (each query is one bit of information; you need $n$ bits). Quantum mechanically, 1 query is sufficient. This is a query complexity result: it counts oracle calls, not elementary gates. The circuit itself uses $O(n)$ gates, so the overall complexity is efficient. This places the problem in BQP (quantum polynomial time) with a 1-query algorithm, while the classical lower bound says no classical algorithm — deterministic or randomized — can do better than $n$ queries.

Bernstein-Vazirani also has a recursive variant (recursive BV): apply the trick in layers to create a problem that separates BQP from BPP (classical randomized poly-time) by a super-polynomial factor, foreshadowing Shor's algorithm which separates them exponentially for factoring.

The algorithm is simple, but the ideas behind it reappear throughout quantum computing and beyond:

• Blueprint for quantum algorithm design. Phase kickback + Hadamard readout is the core template for Deutsch-Jozsa, Simon's algorithm, and ultimately Shor's period-finding. Understanding BV is the cleanest entry point to why Hadamard-based algorithms work.
• Oracle separations and complexity theory. BV gives the cleanest unconditional proof that quantum query complexity can beat classical query complexity by a linear factor. Relativized separations of this kind are a primary tool for understanding the BQP vs. P/BPP landscape.
• Learning Parity with Noise (LPN). The noiseless version of the BV oracle is exactly the parity learning problem. Its noisy extension — LPN — is a central hardness assumption in post-quantum cryptography. The speed with which quantum algorithms can attack noiseless parity is why LPN needs noise to remain hard.
• Quantum machine learning. BV is a textbook example of quantum-enhanced linear algebra: you evaluate a linear function over all inputs at once. This intuition motivates quantum approaches to gradient estimation and Fourier-based learning.
• Teaching tool. Because the speedup is exact (not asymptotic) and the proof is fully self-contained at the undergraduate level, BV is the first algorithm taught in virtually every quantum computing course.

The Bernstein-Vazirani algorithm carries a clean and powerful message: quantum superposition is not just a metaphor — it is a computational resource that changes what is possible. Learning a secret $n$-bit string takes exactly $n$ classical queries and exactly 1 quantum query, and no cleverness on the classical side can close that gap.

The mechanism — prepare uniform superposition, query with phase kickback, decode with Hadamard — is the same skeleton that underlies Shor's algorithm, the greatest quantum speedup known. Bernstein-Vazirani is where that skeleton first appears in its purest form: no approximations, no probability to amplify, just a single shot at the full secret.

If you want to understand why physicists believe quantum computers are genuinely more powerful than classical ones, this is the right place to start.