The Deutsch-Jozsa algorithm was the first example of a quantum algorithm that, in principle at least, solves a problem faster than the best classical algorithm.

The Deutsch-Jozsa problem 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 unknown. The function can be anything, except that we are guaranteed that it is either balanced or constant. A constant function returns always 0 or always 1 regardless of input. A balanced function will return 0 for half of the inputs and 1 for the other half. We are asked to determine whether the Oracle is constant or balanced.

If the function is balanced, a classical algorithm may give an answer in two steps in the most favorable case, assuming it makes two queries and one answer is 0 while the other is 1. In the worst case, 2^(n-1)  + 1 queries may be required to determine the type of Oracle, assuming the first 2^(n-1) queries return all the same result.

Using a quantum computer, we can answer this question by invoking the Oracle just once on the register of n qubits. In all fairness, when evaluating the potential speedup, we may want to take into account the n measurements performed at the end but measuring qubits is not an expensive operation while invoking the Oracle might as well be.

In our example, we implement Deutsch-Jozsa algorithm on 5 qubits. The sixth qubit is where the Oracle will output its result and is prepared in state |1⟩ followed by a Hadamard which should be an indication that the algorithm is secretly using the phase kick-back trick to find the right answer. You can convince yourself of that by performing the calculation by hand on a piece of paper. The Oracle we use is a so called Boolean Oracle meaning it transform an input state |x⟩⊗|y⟩ to: |x⟩⊗|y + f(x)⟩ where the '+' sign indicates addition modulo 2, |x⟩ is a n-qubit state and |y⟩ is a single qubit state. After we apply the algorithm, we measure the 5 input qubits. When the Oracle is constant, and only then, measurements will return 0 for each qubit.