Algorithms that Leverage the Strengths of Quantum Computers

Algorithms Determine How Quantum Computers Are Used

Quantum computers are expected to see real-world application in a diverse set of fields. Quantum chemistry simulation is one clear example of application. Machine learning and artificial intelligence (AI) are other fields that, while unrelated to quantum computing at first glance, are expected to apply quantum computers. Regardless of the specific field, application of quantum computing technology requires algorithms optimized to leverage the strengths of quantum computers. Recent years have seen an increase in the development of such quantum algorithms and the emergence of software development kits (SDKs) for their implementation.

This article will share the essence of quantum algorithms by explaining one typical algorithm: Grover's search algorithm.

How Quantum Computers Solve Problems

To understand how quantum computers solve problems, we will compare the process to that of classical computers.

Quantum computers use qubits to perform calculations. Whereas classical bits can only take on one binary value of “0” or “1” at a time, through the principle of superposition from quantum mechanics qubits can be used to perform calculations while taking both states of “0” and “1” simultaneously (See Quantum Computers Part 1). In principle, anything that can be calculated by a classical computer using bits can be calculated by a quantum computer using qubits.

The question remains: what kind of problems are quantum computers good at solving? For example, a simple calculation such as “1 + 1 = 2” can require as many as four qubits for its implementation; the use of quantum computers for such calculations is excessive. Quantum computers work best with problems geared toward quantum algorithms that leverage the unique properties of qubits as opposed to the algorithms of classical computers.

The Unique Properties of Qubits

This section discusses the unique properties of qubits. Qubits contain three forms of information: the probability of observing a “0”, the probability of observing a “1”, and phase. Qubits feature wave properties with waves to represent the “0” and “1” states. “Phase” is essentially the difference between the two waves. The fact that information of a qubit can be expressed as any point on the surface of a Bloch sphere, the geometrical representation of state in a qubit, is a primary difference from classical bits, which can only take either the “0” or “1” states. Figure 1 illustrates the meaning for different points on the Bloch sphere of corresponding qubits.

Quantum Algorithms Shed Light on Correct Answers

Quantum computers do best with problems suited to quantum algorithms, or algorithms that leverage the unique properties of qubits. In order to explain quantum algorithms, this article will examine Grover’s search algorithm, a quantum algorithm capable of solving problems faster than classical computers.

In this example, the task is to search for the English translation of the Japanese term “Mangoh” from the Japanese-English table of fruit names (Figure 2 left). One glance at the table shows the obvious answer “Mango,” but when a classic computer conducts the search it takes the approach outlined in the middle box of Figure 2. Assuming there is no order to the content of the table, the classical computer will check each line one by one from the top until coming across the desired value on its fourth and final check (Figure 2 right). With eight rows in the table, this procedure could require a maximum of eight checks.

The picture is very different when solving this problem with a quantum algorithm. This problem requires three qubits for the quantum algorithm to search among 2³ (i.e. 8) data entries, because conducting a search among 2^N data entries requires N qubits. The values in the ID column have been changed to binary notation from 000 to 111 to clarify their correlation with the three qubits (Figure 3).

Details for the three steps of the quantum algorithm shown in Figure 3 are described below.

The key to this search algorithm is Step 2. During the execution of Step 2, it becomes clear that state “011” is the correct answer. However, if the qubits are not manipulated during this step, observation of the three qubits will result in random output of any of the states “000” through “111”, and the correct answer cannot be obtained. Therefore, the phase corresponding to the “011” state must be inverted to arrive at the correct answer. The probability of observing the inverted phase is increased through further manipulation in Step 3 and onward.

Though a rough explanation, we hope that this article has helped to provide a clearer picture of the usefulness of quantum algorithms in shedding light on the correct answer to a problem and thus what it means to solve problems with quantum computers.

Future Expectations for Quantum Algorithms and Fields of Application

Grover’s search algorithm was designed for fault-tolerant quantum computation (FTQC). The development of practical FTQC hardware still requires considerable time and practical use will not be immediate. On the other hand, noisy intermediate-scale quantum computers (NISQs) are expected to see practical application in relatively little time. In fact, algorithms for combinatorial optimization problems have seen active development in recent years, with potential application to quantum chemical simulation, machine learning, and optimal route search in logistics (See Quantum Computers Part 2). We have high hopes for future progress in the development of quantum algorithms and hardware for quantum computers.