A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The Bernstein-Vazirani algorithm finds a hidden n-bit string s given an oracle for f(x) = s dot x (mod 2), where dot denotes the bitwise inner product. Classically, n queries are required (one for each standard basis vector). The quantum algorithm recovers s exactly in a single query using the same Hadamard-oracle-Hadamard structure as Deutsch-Jozsa. It demonstrates a linear-to-constant quantum speedup and illustrates the power of phase kickback for extracting global properties from a function oracle.
The Bernstein-Vazirani problem is a natural extension of Deutsch-Jozsa that further illustrates how quantum algorithms extract information from oracles. You are given a black-box function f(x) = s dot x (mod 2), where s is an unknown n-bit string and dot is the bitwise inner product: s dot x = s_1*x_1 + s_2*x_2 + ... + s_n*x_n (mod 2). Your goal is to find s using as few oracle queries as possible.
Classically, each query returns a single bit of information. Querying f(e_i) — where e_i is the i-th standard basis vector with a 1 in position i and 0s elsewhere — returns s dot e_i = s_i, the i-th bit of s. So n queries suffice and are clearly necessary: each query reveals at most one linear constraint on s, and you need n independent constraints to determine n unknowns. No clever classical strategy can do better.
The quantum algorithm uses the same circuit as Deutsch-Jozsa. Initialize n input qubits to |0> and one ancilla to |1>, apply Hadamard to all, query the oracle, apply Hadamard to the input register, and measure. The oracle acts as |x>|-> -> (-1)^(f(x))|x>|-> = (-1)s dot x|x>|->. After the first Hadamard, the input is (1/sqrt(2n)) sum_x |x>. After the oracle, it becomes (1/sqrt(2n)) sum_x (-1)s dot x |x>. Applying Hadamard again performs the Fourier transform over Z_2n, and because the phase pattern (-1)s dot x is exactly a character of this group, the transform localizes it to the single basis state |s>. The measurement outcome is s with probability 1.
The Bernstein-Vazirani algorithm achieves a linear speedup (n queries classically vs. 1 quantumly) rather than the exponential speedup of Deutsch-Jozsa, but it demonstrates a cleaner and more practical pattern. The algorithm reveals how the Hadamard transform acts as a Fourier transform that "decodes" phase information into basis states. This Fourier-transform-based extraction of hidden structure — here a hidden linear function — is the same principle that powers the quantum Fourier transform and ultimately Shor's algorithm for factoring. Bernstein-Vazirani is the simplest case of the "hidden subgroup problem" framework that unifies many quantum algorithms.