Bernstein-Vazirani Algorithm

The Bernstein-Vazirani Algorithm, published by Ethan Bernstein and Umesh Vazirani in 1993, is a variation of the Deutsch-Jozsa algorithm. Instead of distinguishing between constant and balanced functions, it solves the 'hidden bitstring' problem. It demonstrates a linear speedup in terms of queries, but more importantly, it shows how a quantum computer can reconstruct an entire hidden structure in a single step.

Imagine someone has written a secret binary code (like 1011) on a piece of paper and put it in a box. You can test the box by entering a test code. The box will calculate the bitwise dot product of your code and the secret code, and tell you if the number of matching 1s is even (0) or odd (1). Classically, to find a secret code of length $n$, you must test the box at least $n$ times (once for each bit position, e.g., 1000, 0100, 0010, 0001). The Bernstein-Vazirani algorithm allows you to input a quantum superposition of all possible test codes. Through phase kickback, the secret code is written directly into the phases of the qubits, allowing you to read out the entire secret code in a single query.

Let $s \in \{0,1\}^n$ be a hidden bitstring. We are given access to an oracle that evaluates the function $f_s: \{0,1\}^n \to \{0,1\}$ defined by:

$$f_s(x) = x \cdot s = \sum_{i=1}^n x_i s_i \pmod 2$$

Classical Complexity: To determine $s$ with certainty, a classical algorithm must query the oracle at least $n$ times. The optimal classical strategy is to query the unit vectors $e_i$ (strings with a 1 at position $i$ and 0 elsewhere), yielding $f_s(e_i) = s_i$.

Quantum Complexity: The Bernstein-Vazirani algorithm finds $s$ with 100% success probability using exactly 1 query.

Circuit Construction: The circuit is identical to the Deutsch-Jozsa circuit: 1. Initialize: Prepare $n$ qubits in state $|0\rangle^{\otimes n}$ and 1 target qubit in state $|1\rangle$. 2. Superposition: Apply $H^{\otimes n} \otimes H$: $$|\psi_1\rangle = \left( \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle \right) |-\rangle$$ 3. Oracle Query: Apply $U_{f_s}$. By phase kickback: $$|\psi_2\rangle = \left( \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} (-1)^{x \cdot s} |x\rangle \right) |-\rangle$$ 4. Interference: Apply $H^{\otimes n}$ to the control register: $$|\psi_3\rangle = \left( H^{\otimes n} \left( \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} (-1)^{x \cdot s} |x\rangle \right) \right) |-\rangle$$ Let us evaluate the state of the control register. Recall that $H^{\otimes n} |x\rangle = \frac{1}{\sqrt{2^n}} \sum_{y} (-1)^{x \cdot y} |y\rangle$. Substituting this in: $$\text{Control Register} = \frac{1}{2^n} \sum_{y \in \{0,1\}^n} \left( \sum_{x \in \{0,1\}^n} (-1)^{x \cdot s + x \cdot y} \right) |y\rangle = \frac{1}{2^n} \sum_{y \in \{0,1\}^n} \left( \sum_{x \in \{0,1\}^n} (-1)^{x \cdot (s \oplus y)} \right) |y\rangle$$ If $y = s$, then $s \oplus y = 0$. The term $(-1)^{x \cdot 0} = 1$ for all $x$. The inner sum is $2^n$, and the amplitude of $|s\rangle$ is $\frac{2^n}{2^n} = 1$. If $y \neq s$, then $s \oplus y \neq 0$. The term $(-1)^{x \cdot (s \oplus y)}$ is $+1$ for half the values of $x$ and $-1$ for the other half. The inner sum is $0$, and the amplitude of $|y\rangle$ is $0$. Therefore, the state of the control register simplifies exactly to: $$|\psi_3\rangle = |s\rangle |-\rangle$$ 5. Measurement: Measuring the control register yields the hidden bitstring $s$ with probability 1.