Deutsch’s algorithm - Computational approach

Learning objectives

The aim of the lesson is to learn about the Deutsch algorithm for discovery of a mystery function. It shows how classical approaches to the problem are unable to discover the hidden function in fewer than two queries, but that a quantum approach can find the class of functions in one. The lesson introduces the idea of using superposition to probe multiple different states at once, which is the key principle behind all of the later algorithms in this course.

Lesson plan

You can download the worksheet (as pdf and docx) and the spreadsheet (as excel) at the end of the page.

Conceptual introduction

Deutsch's algorithm, developed by David Deutsch in 1985, marks a significant milestone in the world of computing. It is the first instance where a quantum algorithm showed a potential advantage over classical algorithms. This discovery opened the door to the idea that computers based on the principles of quantum mechanics could solve certain types of problems more efficiently than traditional computers. Deutsch's work laid the foundation for quantum computing, inspiring further research and development in this exciting field. In this lesson, you will learn how Deutsch's algorithm works. To fully grasp its significance, you will first need to understand how the problem the algorithm solves can be approached using classical computing methods.

Student exercises and teacher notes

Exercise 1

The “Deutsch Functions” spreadsheet shows how these four functions operate and has a mystery function generator. Click on the “Generate mystery function” button to pick one of the four functions at random. If you change the input in Cell B12 the output of the mystery function will be returned in Cell E12. How can you deduce what the mystery function is by altering the inputs and how many guesses does it take? Justify your answer.

Exercise 2

Using the spreadsheet again, how many guesses does it take to establish whether the mystery function is either a constant function or a balanced function? How does this compare to finding the actual function itself? Justify your answer.

Summary of classical results

We have seen that for both of these problems it takes two queries to find the desired result using classical search techniques. For the first case (finding the specific function), a quantum computer would also require two queries. However, for the second case (deciding whether the function is constant or balanced), quantum computing can provide a radical improvement.

Building the function on a quantum computer

The first step to investigating the problem on a quantum computer is to construct the functions using quantum gates. It is possible to construct all of the four functions using combinations of NOT gates, CNOT gates and no gates at all.

We will need two qubits: q₀ which will take the input of the function and q₁ which will return the output (after being initial set to state ${\displaystyle |0⟩}$).

Use the IBM quantum composer to build each of the following four circuits:

Example

For circuit (a), if we set the input qubit q₀ to state ${\displaystyle |0⟩}$ and the output qubit q₁ initially to state ${\displaystyle |0⟩}$, we see that the final state of q₁ is also state ${\displaystyle |0⟩}$(as the CNOT gate is not triggered):

This means that an input of 0 for the function is mapped to an output of 0.

If we now change the input qubit q₀ to state ${\displaystyle |1⟩}$, we see that the final state of  is now state ${\displaystyle |1⟩}$(as the CNOT gate is now triggered, flipping the state of q₁):

This means that an input of 1 for the function is mapped to an output of 1.

These mappings correspond to function f₃ (the first of the balanced functions)

Exercise 3

The spreadsheet “Quantum Circuits” contains each of the four circuits shown. The input state for q₀ is shown in the bold blue cells, the final state for the output qubit q₁ is shown in the bold red cells. By changing the initial inputs to q₀ and measuring the final outputs of  q₁, work out which function (f₁, f₂, f₃ and f₄) each of the circuits (b), (c) and (d) corresponds to. Write your answers below:

Summary of quantum results

By using superposition, we were able to find whether the function was constant or balanced in one query rather than two, i.e. a quantum computer can solve this problem twice as fast as a classical computer. There are two important points the Deutsch problem also highlights:

• Quantum computers cannot outperform classical computers in every situation. As we have seen here, the quantum algorithm only helped us with the problem of constant versus balanced functions, not which specific function was in the black box. Whether a problem can be solved by a quantum computer always requires careful thought.
• The solution to this problem was found by looking at the input qubit rather than the output qubit. Information was gained in the input qubit at the expense of information lost in the output qubit. Quantum computing often involves such trade-offs, and we often have to look for solutions in unusual places!

While Deutsch’s problem is a slightly artificial example, it showed the potential for quantum computers and paved the way for more meaningful quantum algorithms that we will explore in the next lessons.