Bernstein–Vazirani algorithm
The Bernstein–Vazirani algorithm, which solves the Bernstein–Vazirani problem is a quantum algorithm invented by Ethan Bernstein and Umesh Vazirani in 1992. It is a restricted version of the Deutsch–Jozsa algorithm where instead of distinguishing between two different classes of functions, it tries to learn a string encoded in a function. The Bernstein–Vazirani algorithm was designed to prove an oracle separation between complexity classes BQP and BPP. Problem statement. Given an oracle that implements a function formula_1 in which formula_2 is promised to be the dot product between formula_3 and a secret string formula_4  modulo 2, formula_5, find formula_6. Algorithm. Classically, the most efficient method to find the secret string is by evaluating the function formula_7 times with the input values formula_8 for all formula_9: In contrast to the classical solution which needs at least formula_7 queries of the function to find formula_6, only one query is needed using quantum computing. The quantum algorithm is as follows: Apply a Hadamard transform to the formula_7 qubit state formula_14 to get Next, apply the oracle formula_16 which transforms formula_17. This can be simulated through the standard oracle that transforms formula_18 by applying this oracle to formula_19 . (formula_20 denotes addition mod two.) This transforms the superposition into Another Hadamard transform is applied to each qubit which makes it so that for qubits where formula_22, its state is converted from formula_23 to formula_24 and for qubits where formula_25, its state is converted from formula_26 to formula_27. To obtain formula_6, a measurement in the standard basis (formula_29) is performed on the qubits. Graphically, the algorithm may be represented by the following diagram, where formula_30 denotes the Hadamard transform on formula_7 qubits: The reason that the last state is formula_33 is because, for a particular formula_34, Since formula_36 is only  true when formula_37, this means that the only non-zero amplitude is on formula_33. So, measuring the output of the circuit in the computational basis yields the secret string formula_6.