Bernstein–Vazirani Algorithm

Overview

Bernstein–Vazirani (BV) is a “hidden string” algorithm.

You are given oracle access to a function

$$f_s(x) = s\cdot x \;\;\text{(mod 2)},$$

where:

• $x\in\{0,1\}^n$ is your query,
• $s\in\{0,1\}^n$ is a fixed hidden bitstring,
• $s\cdot x$ means the bitwise dot product mod 2 (XOR of the ANDs).

Goal: recover $s$.

Why it’s interesting:

• Classically, you typically need $n$ queries to learn all bits of $s$.
• Quantumly, BV finds $s$ with one oracle query, using phase kickback and interference.

Intuition

In the oracle model, the function output is one bit. So it seems like you only learn one bit per query.

BV bypasses that “one-bit bottleneck” by using phase kickback:

• the oracle imprints a structured phase pattern $(-1)^{f_s(x)}$ across a superposition of all $x$.
• a final layer of Hadamards converts that phase pattern into the computational basis state $|s\rangle$.

So the algorithm extracts the entire hidden string in a single query because the oracle’s phase pattern is globally structured.

Algorithm Structure

High-level steps:

1. Prepare $n$ input qubits in $|0\rangle^{\otimes n}$ and a target qubit in $|1\rangle$.
2. Apply H to all qubits to create a uniform superposition on the input and $| - \rangle$ on the target.
3. Query the oracle once.
4. Apply H to the input register.
5. Measure the input register; the result is $s$.

Formal Description

Oracle

Use the standard reversible oracle:

$$U_{f_s}|x\rangle|y\rangle = |x\rangle|y\oplus f_s(x)\rangle.$$

As in Deutsch–Jozsa, preparing the target as $| - \rangle$ turns the XOR into a phase:

$$|x\rangle| - \rangle \mapsto (-1)^{f_s(x)}|x\rangle| - \rangle.$$

So after the oracle, the input register is

$$\frac{1}{\sqrt{2^n}}\sum_x (-1)^{s\cdot x}|x\rangle.$$

Why the final Hadamards reveal $s$

Hadamards transform phase patterns into basis states. In BV, the particular phase pattern $(-1)^{s\cdot x}$ is exactly the one that maps to $|s\rangle$ after $H^{\otimes n}$.

Conceptual takeaway:

• the hidden string is not stored in probabilities yet;
• it is stored in the phase relationship across all $x$;
• the final mixing step turns that phase into a sharp measurement outcome.

Worked Example

Let $n=3$ and hidden string $s=101$. So

$$f_s(x_1x_2x_3) = x_1 \oplus x_3.$$

After the oracle (with phase kickback), each basis state $|x\rangle$ gets a sign of $(-1)^{x_1\oplus x_3}$:

• if $x_1\oplus x_3=0$, the sign is +1
• if $x_1\oplus x_3=1$, the sign is −1

This sign pattern is globally consistent with the hidden string. After applying $H^{\otimes 3}$, the input register collapses to the basis state $|101\rangle$. Measuring yields 101 with certainty in the ideal model.

Turtle Tip

Common Pitfalls

Quick Check

What’s Next

BV shows how phase can encode a hidden linear structure. Next we study Simon’s algorithm, which is an early example of period-finding: the oracle hides a secret XOR-period $s$, and measurement reveals constraints that let you reconstruct it.