Deutsch's algorithm

Deutsch discovered a problem which the quantum computer could solve faster than a traditional computer, although not exponentially faster. The problem that Deutsch's algorithm solves is not an important problem in Computer Science. It is a contrived problem to see how quantum computers can be used. It is presented here with that purpose.

The problem

Suppose there is a function f that maps {0, 1}into {0, 1}. We wish to know whether the function is one to one or not. Note that there are only four possible functions mapping {0, 1} into {0, 1}. Both f(0) and f(1) can map to either 0 or 1.

The problem could be solved by evaluating f(0) XOR f(1). If the function is one to one, then f(0) XOR f(1) will be equal to 1, and it will be equal to 0 otherwise. This solution to the problem evaluates the function twice in order to determine whether it is one to one or not.

Deutsch's algorithm

The function f has a domain and range of two values. These two values correspond to the possible values of a qubit. Note that in the description of the algorithm and the example below, 00 is shorthand for (0, 0) and means that both qubits have value 0, and likewise for 01, 10, and 11.

1. Prepare two qubits, one in state 0 and the other in state 1. The value of the two qubit register is (0, 1) after step 1.
2. Let H be the Hadamard transformation that operates on the basis vectors as follows:
   
   We send the output from step 1 through the H gate. After step 2, the value of the quantum register is
   
3. Let G be a quantum gate that operates on a pair of qubits (i, j) by
   G(i, j) = (i, j + f(i)). The output from step 2 is send through the gate G. The output will depend on the function f.
4. The output from step 3 is sent through the H gate again.
5. The output from 4 will be a two qubit register. If all four possible function values are tested, it is revealed that the final output (from step 4) will be either (0, 0), (0, 1), (1, 0), or (1, 1) with probability 1. Which value is the output depends on f. The two qubits are entangled in the end, so only one of their values can be measured. This prevents us from known exactly which f is being used. However, the first qubit in the pair will always be 1 if the function is one to one. We measure the value of the first qubit to determine whether the function is one to one.

Note that the function was only evaluated once during the algorithm. The quantum algorithm only evaluates the function once while the classical algorithm evaluates the function twice. This could make significant difference if the function f is very complicated and takes a great deal of time to compute.

Example

We will show how the algorithm operates with a particular function f. Suppose f(0) = 0 and f(1) = 1.

1. The output from step 1 has already been given above.
2. The output from step 2 has already been given above.
3. The output from step 3 will be
   . This output is generated by applying G to each of the individual components of the output from step 2.
4. The output from step 4 will be
   .
5. The final value of the quantum register is (1, 1). We measure the first qubit to be equal to 1, so we know that the function is a one to one function.