Bernstein-Vazirani algorithm

The Bernstein-Vazirani algorithm is a quantum algorithm invented by Ethan Bernstein and Umesh Vazirani in 1997. It solves the Bernstein-Vazirani problem, in which a hidden oracle computes the dot product, modulo two, of its input with a secret bit string, and the task is to recover that string. It is a restricted version of the Deutsch-Jozsa algorithm: instead of distinguishing between two different classes of functions, it learns a string encoded in a function. A classical method needs one query to the oracle for each bit of the string, while the quantum algorithm uses Hadamard transforms on the qubits and recovers the whole string with a single query. The algorithm was designed to prove an oracle separation between the complexity classes BQP and BPP, and the problem has to be reshaped into a decision problem with a recursive construction and a second random oracle to give that separation.