The BernsteinVazirani algorithm builds upon DeutschJozsa by proving that a quantum computer can solve a problem that is slightly more complex than the simple DeutschJozsa problem and can solve it in a smaller number of steps than a classical computer.
Like DeutschJozsa, it assumes the existence of a function from an ndigit 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 bitwise product between the ndigit input number x and a fixed binary number ndigit 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 BernsteinVazirani algorithm on 5 qubits. The quantum Oracle is a socalled 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 zbasis. The measurement result is the binary representation of the unknown number 's'.
