Step by step guide to Deutsch's Algorithm

We are still in the early days of quantum computing, and we are yet to see real-world applications of it with real impact. But we are already seeing the first signs of quantum advantage, where quantum computers can outperform classical computers on certain tasks.

In this post, we will demonstrate quantum advantage by walking through Deutsch's algorithm step by step.

Note that this is a simple, contrived example without any real-word applications. However, it is a good starting point to understand the potential of quantum computing.

What is Deutsch's Algorithm?

Deutsch's algorithm (invented by David Deutsch in 1985) is an example of a quantum algorithm that can solve a problem faster, by some measure, than any classical algorithm.

Faster in this context means that the algorithm solves a very specific problem in one go (if we had a noise-free quantum computer). This is in contrast to a classical algorithm that we would have to run twice to solve the same problem.

The Problem Deutsch's Algorithm Solves

Deutsch's algorithm solves a simple problem: given a function $f(x)$ that takes a single bit (i.e. 0 or 1) as input and returns a single bit (i.e. 0 or 1) as output, determine if the function is constant or balanced.

• A constant function is one where the output is always 0 or always 1, regardless of the input.
• A balanced function is one where the output is 0 for one input and 1 for the other input.

In other words, we are given some function $f(x)$, which is unknown to us, but which we can call and observe the output, and the problem is to determine if $f(x)$ is constant or balanced.

As the function takes a single bit as input, there are only four possible functions.

1. The first 2 possible functions are constant:
   1. $f(0) = 0$ and $f(1) = 0$ $\to$ $f$ is constant (always 0)
   2. $f(0) = 1$ and $f(1) = 1$ $\to$ $f$ is constant (always 1)
2. The other 2 possible functions are balanced:
   1. $f(0) = 0$ and $f(1) = 1$ $\to$ $f$ is balanced
   2. $f(0) = 1$ and $f(1) = 0$ $\to$ $f$ is balanced

The problem is to determine if the function we're given is constant or balanced.

The Classical Solution involves 2 queries

It's easy to see that if we approach this problem classically, we would have to call the function twice to determine if it's constant or balanced.

For example, we can call the function with input 0 and learn that the output is $f(0) = 1$, we can tell that we are either in case 1.2 (constant) or case 2.2 (balanced).

But we would still have to call the function a second time with input 1 to distinguish between the two cases.

The Quantum Solution involves just 1 query

The Quantum solution (Deutsch's algorithm) can solve this problem in one go. As you might expect, the solution is a lot more involved than the classical one. But in a nutshell we will rely on the following principles:

• Superposition: We're putting a qubit in superposition, and then apply $f(x)$ on it. This allows us to evaluate $f(x)$ for both inputs at the same time.
• Phase Kickback: The effect where the phase of a qubit is "kicked back" onto another qubit during a controlled quantum operation like the CNOT gate.

High level overview of Deutsch's Algorithm

On a high level the algorithm works as follows:

1. Prepare the qubits $x$ and $y$ in the state $\ket{0}\ket{1}$. We call the joint state $\ket{\phi}_0$.
2. Apply a Hadamard gate to both qubits to put them in superposition. We call this state $\ket{\phi}_1$
3. Apply the gate $U_f$ (there are 4 choices as we know): $\ket{\phi}_2$. More on the gate $U_f$ below.
4. Apply a Hadamard gate to qubit $x$. We call this state $\ket{\phi}_3$
5. Measure qubit $x$.

The result will depend on the function $f$ we chose: If the function is constant, the measurement will always be 0. If the function is balanced, the measurement will be 1. Crucially, we only have to call the function once.

Some Math Preliminaries

The XOR operator/ addition modulo 2

Before we continue, let's introduce a little bit of notation. The XOR operator, also known as exclusive OR, or addition modulo 2, is a binary operation that takes two bits and returns 1 if the bits are different, and 0 if they are the same. We sometimes use the symbol $\oplus$ to denote the XOR operator.

For example: if we write $4 \oplus 2$, we mean the XOR of the binary numbers $100$ and $010$, which is 110 (6 in decimal). So $4 \oplus 2 = 6$.

Given this, the classical solution to the problem is to call the function twice and apply the XOR operator to the results.

In other words:

• if $f(0) \oplus f(1) = 0$ we know that the function is constant
• if $f(0) \oplus f(1) = 1$ we know that the function is balanced

Introducing a controlled quantum operation

The algorithm involves 2 qubits: one which will we'll call $x$, the qubit that we'll evaluate $f(x)$ on, and another one which we will call $y$ that will be used for the phase kickback mentioned above.

First, there is one important quantum gate that we have to define: the gate $U_f$. This is a unitary, i.e. reversible, 2-qubit gate that applies our function $f(x)$ to the qubits $x$ and $y$.

What $U_f$ does is that it maps the state $\ket{x}\ket{y}$ to $\ket{x}\ket{y \oplus f(x)}$. Remember that $\oplus$ is the XOR (or addition modulo 2) operator and $f(x)$ is one of the 4 cases defined above.

As you can see, $U_f$ is a controlled operation in the sense that it applies alters the state of $y$ based on the value of $f(x)$. That is, the state of $x$ controls the state of $y$.

Let's see how $U_f$ acts in, for example, the case of a constant function $f(x) = 0$:

• $\ket{0}\ket{0} \to \ket{0}\ket{0 \oplus 0} = \ket{0}\ket{0}$
• $\ket{0}\ket{1} \to \ket{0}\ket{1 \oplus 0} = \ket{0}\ket{1}$
• $\ket{1}\ket{0} \to \ket{1}\ket{0 \oplus 0} = \ket{1}\ket{0}$
• $\ket{1}\ket{1} \to \ket{1}\ket{1 \oplus 0} = \ket{1}\ket{1}$

Nothing happens.

Now let's try the balanced function $f(x) = x$:

• $\ket{0}\ket{0} \to \ket{0}\ket{0 \oplus 0} = \ket{0}\ket{0}$
• $\ket{0}\ket{1} \to \ket{0}\ket{1 \oplus 0} = \ket{0}\ket{1}$
• $\ket{1}\ket{0} \to \ket{1}\ket{0 \oplus 1} = \ket{1}\ket{1}$
• $\ket{1}\ket{1} \to \ket{1}\ket{1 \oplus 1} = \ket{1}\ket{0}$

You get the idea.

Walking through Deutsch's Algorithm step by step

Ok let's get into the nitty gritty. We'll use $\textcolor{Red}{red}$ to keep track of qubit $x$ and $\textcolor{Blue}{blue}$ for qubit $y$. We start with

After applying to the Hadamard gates, the state becomes:

Now we apply the gate $U_f$, which as we know applies this transformation: $\ket{\textcolor{Red}{x}}\ket{\textcolor{Blue}{y}} \to \ket{\textcolor{Red}{x}}\ket{\textcolor{Blue}{y} \oplus f(\textcolor{Red}{x})}$

We can simplify this, since $\ket{0 \oplus a} - \ket{1 \oplus a} = (-1)^{a}(\ket{0} - \ket{1})$, where $a$ is either $f(0)$ or $f(1)$, so it's 0 or 1. So, rewriting we get:

since $\ket{-} = \frac{\ket{0} - \ket{1}}{\sqrt{2}}$.

We just observed Phase Kickback in action: Notice how the application of $U_f$ left $y$ in state $\ket{\textcolor{Blue}{-}}$, but kicked back the phase factor $(-1)^{f(x)}$ in front of $x$.

Now we can pull out $(-1)^{f(\textcolor{Red}{0})}$

where we used the fact that $(-1)^{f(\textcolor{Red}{1}) - f(\textcolor{Red}{0})} = (-1)^{f(\textcolor{Red}{0}) \oplus f(\textcolor{Red}{1})}$.

This is because $f(0)$ and $f(1)$ are either 0 or 1, so the difference between them is either 0, 1 or -1. If the difference is 0, then we get $(-1)^0 = 1$. And if the difference is 1 or -1 we get $(-1)^1 = (-1)^{-1} = -1$.

We do this because now we can see more clearly the effect of phase kickback: it introduces a relative phase of $(-1)^{f(0) \oplus f(1)}$ in qubit $x$.

Let's look at the term $\left(\frac{ \ket{\textcolor{Red}{0}} + (-1)^{f(\textcolor{Red}{0}) \oplus f(\textcolor{Red}{1})} \ket{\textcolor{Red}{1}} }{\sqrt{2}} \right)$ for a moment. Since $f(0) \oplus f(1)$ can be either 0 or 1, this is either $\ket{+} = \frac{\ket{0} + \ket{1}}{\sqrt{2}}$ if $f(0) \oplus f(1) = 0$ or $\ket{-} = \frac{\ket{0} - \ket{1}}{\sqrt{2}}$ if $f(0) \oplus f(1) = 1$.

In other words we have the following 2 cases:

Importantly, notice that the state of qubit $x$ is now either $\ket{+}$ or $\ket{-}$, depending on whether the function is constant or balanced!

This is all due to the phase kickback we observed earlier. To reiterate: the application of $U_f$ kicked back the phase factor $(-1)^{f(x)}$ in front of $x$. This introduced a relative phase of $(-1)^{f(0) \oplus f(1)}$ in qubit $x$.

It also introduced a global phase of $(-1)^{f(0)}$ in front of the whole state. But we don't care about this because we can't measure it.

It's worth noting that there are 2 necessary conditions for this to work:

1. we had to apply the Hadamard gate to qubit $x$ at the beginning. Otherwise the gate $U_f$ wouldn't have any effect on qubit $x$. As you remember from the formula $\ket{x}\ket{y \oplus f(x)}$, $U_f$ has no effect on qubit $x$ in the computational basis.
2. we had to start with the state $\ket{1}$ for qubit $y$, otherwise the phase kickback on qubit $x$ wouldn't have occurred.

The final step is to apply a Hadamard gate to qubit $x$:

Now we can measure qubit $x$ and we will get 0 if the function is constant and 1 if the function is balanced.

Conclusion

Deutsch's algorithm is a simple example of a quantum algorithm that can solve a problem faster than any classical algorithm. It's a significant milestone in the history of quantum computing, as it shows that quantum computers can outperform classical computers on certain tasks.

The speedup in this case modest, it's a linear speed up, but it's a proof of concept and laid the groundwork for more advanced quantum algorithms, which we'll explore in future posts.

It also provides a hint as to how to structure quantum algorithms in general: modulating the phase of qubits to create interference patterns that make certain measurements more likely than others. In the case of Deutsch's algorithm, making the correct answer 100% likely.

If you want to put theory into practice, check out Running Deutsch's Algorithm on a Real Quantum Computer.