5.2.1 Deutsch’s algorithm

It is late on Sunday evening. Alice and Bob have just finished their homework assignments for the quantum computing class and are about to watch a 3D movie. When they turn on their holographic television set, they discover that the movie screening has been postponed due to unexpected dramatic news coverage coming from the International Transgalactic Station. There has been a terrible accident and a module containing two crew members, Hila and Iman, has separated from the main mothership. The last message received from the module was that Iman has been injured and is heavily bleeding – he is in need of an urgent blood transfer. What makes the situation complicated is that Hila and Iman are somewhat in shock and forgot their own blood type – they can only remember that they each had blood type A or B. The news presenter is appealing to the general public for help with suggesting a way for Hila and Iman to determine if they have the same blood type, because if that was the case Hila could transfer her blood to Iman to save his life. This is because the medical kit in Hila and Iman’s module includes a lympho-transcoder that is able to convert either of the two blood types to the opposite one. Hence, even if it turns out that their blood types are mismatching, Hila can convert her’s to the opposite one using the lympho-transcoder.

Upon hearing these news, Alice and Bob immediately abandon their plan to watch a movie and start to ponder what could be done to help Hila and Iman. The news coverage continues with some additional information. Luckily, it turns out that the module involved in the accident contains a database chip that stores Hila and Iman’s blood type. We can model this by a function $f\colon\{0,1\}\to\{0,1\}$, where

What needs to be determined is whether $f(0)=f(1)$ or not!

The solution seems at hand: Hila and Iman simply need to query the database twice to read out their respective blood types, $f(0)$ and $f(1)$, and then compare the two values to see if they are the same. Unfortunately, the accident has partly fried the control logic of the database chip and the news presenter reports that after the first query the database chip will likely burn out completely.

Our two protagonists are at an impasse. Clearly, any classical algorithm needs to evaluate $f$ twice in order to determine whether $f(0)=f(1)$. Indeed, if you know only the value of $f(0)$ then whether $f(0)=f(1)$ still depends on the value of $f(1)$ and, unless you also compute $f(1)$, you would not be able to tell whether $f(0)=f(1)$. Similarly, if you know only $f(1)$ then you cannot compare it with $f(0)$ unless you also know what the value of $f(0)$ is. No matter what strategy you use, you need to know both $f(0)$ and $f(1)$ in order to determine whether $f(0)=f(1)$. Is there really no way around this?

After flipping through some manuals, Bob discovers that the database chip can be switched into quantum mode. When enabled, the database chip no longer evaluates the function classically but instead implements the sign oracle $O_{f}$. Could this somehow be used to solve the problem? Alice thinks about it for a second and suddenly realizes that this is precisely what Deutsch’s algorithm is for! Alice and Bob quickly go over some calculations to confirm that it works and sit down to write an intergalactic e-mail with instructions to Hila and Iman on how they can solve the problem. Their instructions are as follows:

1. 1.
   ​

   Prepare a qubit in state $\left|+\right\rangle=(\left|0\right\rangle+\left|1\right\rangle)/\sqrt{2}$.

2. 2.
   ​

   Use the database chip in quantum mode to apply the operation $O_{f}$.

3. 3.
   ​

   Apply the Hadamard gate $H$ to the output qubit and measure it.

4. 4.
   ​

   If the outcome is $0$ then Hila and Iman have the same blood type and otherwise they have different blood types.

Note that in this procedure Hila and Iman only query the database chip once to determine if they have the same blood type. Here is an implementation of the algorithm in Quirky:

The picture shows that the outcome is $1$, so Hila and Iman have different blood types.

But why does Deutsch’s algorithm work? Let us analyze it step by step. The first Hadamard gate creates the state $\left|+\right\rangle=H\left|0\right\rangle$. Next, we apply the sign oracle $O_{f}$, which leads to the state

After applying the second Hadamard, we obtain the following state:

Note that the two signs $(-1)^{f(0)}$ and $(-1)^{f(1)}$ are added in the first amplitude, but subtracted in the second amplitude. Depending on the values of $f(0)$ and $f(1)$, for each amplitude we will observe either constructive or destructive interference (see Section 2.6.1). In fact, which of the two amplitudes will remain is determined only by whether $f(0)$ and $f(1)$ are equal or not:

It is a good exercise to verify this explicitly:

Eq. 5.8 shows that the final measurement yields outcome 0 if and only if $f(0)=f(1)$. Thus, Deutsch’s algorithm correctly determines whether $f(0)=f(1)$. Importantly, it evaluates the function $f:\{0,1\}\to\{0,1\}$ only once by using the sign oracle. In contrast, we discussed above that any classical algorithm necessarily needs to evaluate both function values $f(0)$ and $f(1)$ separately.

Another way to interpret Deutsch’s algorithm is that it computes the sum of the two bits $f(0)$ and $f(1)$ modulo two. This is because $f(0)\oplus f(1)=0$ if and only if $f(0)=f(1)$. Indeed, recall from Eq. 3.21 that addition modulo two works as follows:

This is also why the sum modulo two is known as the XOR (short for ‘exclusive OR’) of the two bits, since it is one if exactly one of the two bits is set.