The Bernstein-Vazirani algorithm builds upon Deutsch-Jozsa by proving that a quantum computer can solve a problem that is slightly more complex than the simple Deutsch-Jozsa problem and can solve it in a smaller number of steps than a classical computer.

Like Deutsch-Jozsa, it assumes the existence of a function from an n-digit binary number to a single digit binary number (0 or 1). We will refer to this function as an Oracle, since the function is in principle unknown. What we do know is that the Oracle returns the bit-wise product between the n-digit input number x and a fixed binary number n-digit number, which will call 's':

f(x) = x * s

We are required to find the number 's'. Classically this problem can be solved by invoking the oracle n times on binary numbers 10000..0, 01000..0, 00100..0 etc. This way during each step we find out one bit of the binary representation of the unknown number 's'. Using a quantum computer, we can solve this problem with one invocation of the Oracle on a register of n qubits. It is true that we also need to make n measurements as well but these are not expensive operations while invoking the Oracle might as well be.

In our example, we implement the Bernstein-Vazirani algorithm on 5 qubits. The quantum Oracle is a so-called Phase Oracle, meaning it maps an input state |x⟩ to the state: (-1)^(s*x) |x⟩. The sixth qubit is an additional scratch qubit that is needed in order for the Boolean Oracle to perform its magic (perform phase kickback).

After we apply the algorithm, we measure the 5 input qubits in the z-basis. The measurement result is the binary representation of the unknown number 's'.