The Deutsch Algorithm

In 1985, David Deutsch introduced one of the first quantum algorithms to show an advantage over classical computing algorithms. Many others, including Deutsch himself, subsequently modified the algorithm to make it more efficient and understandable.

Deutsch’s algorithm asks a specific question about mathematical functions for which the independent variable (the input) is a binary digit, that is, $0$ or $1$, and the dependent variable (the output) is $0$ or $1$. Since there are only two possible input values and two possible output values, we have four possible functions. Customarily, these are labeled $f_0$, $f_1$, $f_2$, and $f_3$. Of course, you could use any four names you would like. We don’t need to worry about the details of how the functions turn the inputs into the outputs. All we need to do is specify the output for each of the two possible inputs $0$ and $1$. The following table displays the results.

The functions are divided into two classes: (1) constant functions and (2) balanced functions. Constant means that the output is the same no matter what the input is. The other two give $0$ for $50$% of the inputs and $1$ for the other $50$% and are called balanced functions. For a one-qubit system, all non-constant functions are balanced, as shown in the table below. For a two-qubit system, we might have a function that gives $f(00) = 0$ and $f(01) = f(10) = f(11) = 1$. That function is non-constant, but not balanced. We will restrict ourselves to constant and balanced functions.