Questions: Bernstein-Vazirani Algorithm

Question 1

In the Bernstein-Vazirani algorithm, what is the output state of the input register after the Hadamard-oracle-Hadamard sequence, before measurement?

• A. |0...0>
• B. |s> where s is the hidden string
• C. An equal superposition of all n-bit strings
• D. |s_perp> — the bitwise complement of s

Answer: (B)

The final state is exactly |s>. After the first Hadamard, the input register is in a uniform superposition. The oracle applies phase (-1)^(s dot x) to each |x>. The final Hadamard transform converts this phase pattern into the basis state |s> with probability 1. This works because the Hadamard transform is its own inverse and the function f(x) = s dot x (mod 2) produces exactly the phase pattern that the Hadamard transform 'decodes' to |s>.

Question 2

The Bernstein-Vazirani algorithm uses the same circuit structure as Deutsch-Jozsa: Hadamard, oracle, Hadamard.

• T. True
• F. False

Answer: True

Both algorithms use the identical circuit skeleton: prepare |0>^n|1>, apply H to all qubits, query the oracle (which applies phase kickback via the ancilla in |->), apply H to the input register, and measure. The difference is in the oracle and what the measurement reveals. In Deutsch-Jozsa, you check if the output is |0...0>. In Bernstein-Vazirani, the output directly encodes the hidden string s.

Question 3

Why does a classical algorithm need exactly n queries to find s, while the quantum algorithm needs only one?

Model answer: Classically, each query f(x) returns one bit — the inner product s dot x mod 2. To recover all n bits of s, you need n linearly independent queries (the standard basis vectors e_1,...,e_n work, since f(e_i) = s_i). The quantum algorithm queries f on a superposition of all 2^n inputs simultaneously, and phase kickback encodes all n bits of s into the quantum state's phase pattern. The final Hadamard transform converts this global phase information into the computational basis state |s>, recovering all n bits at once.

This highlights a genuine quantum advantage: a single quantum query can extract n bits of information about a function through interference, while a single classical query yields only one bit. The mathematical reason is that the Hadamard transform is the discrete Fourier transform over Z_2^n, and the function f(x) = s dot x is a character of this group. The Fourier transform localizes the character to a single point — exactly the hidden string s.