Deutsch’s Algorithm

Classical computers solve problems. If they didn’t solve any problems, we’d call them “classical waste.”

So, what about quantum computers? Are there any problems that quantum computers can solve? If you’ve read Chapters 1 to 6, you may be suspicious.

Chapters 1 to 4 describe qubits, but those chapters say nothing about problems you can solve with those qubits. Chapters 5 and 6 show you how to move qubits around, but neither of those chapters involves a question-and-answer scenario. You can ask a classical computer whether 15 equals 3 times 5. Could you ask a quantum computer to do that?

In this chapter, we pose a question and a quantum computer provides an answer. The question concerns binary-valued functions, and the answer comes courtesy of something called Deutsch’s algorithm.

When you read about Deutsch’s algorithm, your first impression may be that this algorithm is a complete waste of resources...

Technical requirements

The code used in this chapter can be found online on GitHub at https://github.com/PacktPublishing/Quantum-Computing-Algorithms.

Describing Deutsch’s problem

Deutsch’s algorithm solves a problem concerning constant and balanced functions. So, as you start this chapter, I want to make sure that you’re familiar with the terms algorithm, function, constant function, and balanced function. This section covers those essential ideas.

Algorithms

You may have seen friendly signs that display the equivalent of “Welcome!” in many languages. Figure 7.1 does the same kind of thing for a particular sequence of instructions:

Figure 7.1 – Expressing the steps that add 1 to a number

Each part of Figure 7.1 inputs a number and outputs that number plus 1. The parts look different, but they all describe the same sequence of steps. This sequence of steps is an example of an algorithm.

Definition

An algorithm is a sequence of steps.

You can change the way you describe a particular sequence of steps. But when you do, you still have the same algorithm...

Solving Deutsch’s problem

The circuit that solves Deutsch’s problem has very few gates. It doesn’t look very complicated. But to understand why the circuit works, you have to understand some important concepts. This section covers those critical concepts.

Phase kickback

In Chapter 4, we introduced the controlled NOT (CNOT) gate with its control and target qubits. In a typical scenario, the control qubit tells the target qubit what to do, and the target qubit obeys willingly. But what about a non-typical scenario? Is there such a thing as a disobedient target qubit? To find out, let’s do an experiment.

Run the following code:

from qiskit import QuantumCircuitfrom qiskit.quantum_info import Statevector
from qiskit.visualization \
    import plot_bloch_multivector
circ = QuantumCircuit(2)
circ.x(1)
circ.h(0)
circ.h(1)
display(circ.draw('latex'))
state = Statevector(circ)

display(plot_bloch_multivector(state, reverse_bits...

Deutsch’s algorithm F.A.Q.

Like most people, you may view Deutsch’s algorithm with a bit of skepticism. Is this all we can do with a multi-million-dollar quantum computer? Let’s consider such questions:

• With Deutsch’s algorithm, you evaluate f(x) once instead of twice. Is that time-saving such a big deal?

The time saving is tiny, but tiny time savings add up when you’re doing billions of calculations. Besides, the fact that we can evaluate a function only once and discover something about two possible output values (f(0) and f(1)) is amazing. You have to admit that.

• Deutsch’s algorithm requires circuitry that’s not needed in the classical algorithm. You need a few Hadamard gates and an oracle with two outputs. Does this mean that Deutsch’s algorithm is less efficient than the classical algorithm?

To measure efficiency, computer scientists consider the relationship between the amount of input and the...

Coding Deutsch’s algorithm

Most of the code in this section uses Qiskit features from previous chapters.

First, we have our import declarations:

from qiskit import QuantumCircuit, executefrom qiskit_ibm_provider import IBMProvider
from enum import Enum

To distinguish between the simple binary functions, we create a Python enumeration:

class SimpleBinary(Enum):    ZERO        = 0
    ONE         = 1
    SAME_AS     = 2
    OPPOSITE_OF = 3

This chapter’s code makes little use of the SimpleBinary enumeration. But having an enumeration feels better than just assigning the numbers 0, 1, 2, and 3 to the four functions.

Our get_oracle code adds different gates to a circuit depending on which of the simple binary functions we want to implement:

def get_oracle(circ, function...

Summary

Deutsch’s algorithm doesn’t solve problems concerning world hunger or climate change, and it doesn’t even print Hello world. But the algorithm serves as a proof of concept for the potential of quantum computing. Using Deutsch’s algorithm, you can compare two possible input values, 0 and 1, with only one computational step. In the classical world, that would be impossible. It’s like seeing inside two boxes by opening only one of them.

In the next chapter, we up the ante by exploring a slightly more complicated quantum algorithm. This new algorithm may not help us develop cold fusion or achieve world peace, but it demonstrates the power of quantum processing over classical computing strategies.

Questions

1. Is this circuit reversible?

2. In this chapter’s Coding Deutsch’s algorithm section code, change the number of shots from 1 to 100. Then, run the modified code on a real quantum computer. How many of those 100 shots give you the correct answer (constant versus balanced)?

Run the modified code more than once. Observe the variation in the number of correct shots from one run to another.

3. When we run Deutsch’s algorithm, the result depends on whether or not there’s a CNOT gate inside the oracle. But the result doesn’t depend on whether or not there’s an X gate in the oracle. Why not?
4. Does the following circuitry implement the Opposite_of function? Why, or why not?

5. Look up the compose method belonging to the QuantumCircuit class in the Qiskit documentation.

Modify the get_oracle code in this chapter’s Coding Deutsch’s algorithm...