Machine Learning and Other Algorithms
In quantum chemistry, factoring, and generalized search we have seen three of the four important classic (so to speak) algorithms of quantum computing, all developed in the 1990s. (The fourth, the Deutsch-Jozsa algorithm, was actually the first quantum algorithm developed in detail and showing a potential scaling improvement for quantum computers, but it is of limited practical use, so we will not discuss it in this course.) Shor is fairly cut and dried, but variants of search continue to evolve, and quantum chemistry has developed substantially in the last ten years or so. But these are far from the only uses for a quantum computer.
Let us briefly introduce a few of the other potential uses. The details of these algorithms, including the set of use cases where they are faster on a quantum computer than a classical one, are complex, so deeper study of them is left for a more advanced course. In Week 3, when we cover algorithms in detail, we will introduce one important algorithm from this group, discussing the problems it solves rather than how it operates.
Operations involving matrices and vectors of numbers are called linear algebra or linear systems. They are used in many important calculations, from rotating an object in a video game to calculating characteristics of the economy to almost every physics and engineering problem. They are even used in describing quantum computers.
Quantum computers can achieve a significant speedup on a number of linear problems: checking the result of multiplying two matrices, or finding some property of a matrix by calculating for some function , some matrix , and some vector , for example. They can also calculate approximate values of exponents of matrices, .
For some specialized variants of these problems, quantum computers can offer superpolynomial speedups. For others, the speedup is polynomial.
Machine learning is one popular subfield of artificial intelligence, especially the form known as deep learning, which is revolutionizing many real-world online services such as image recognition, voice recognition and automated language translation. In fact, it builds on subroutines for linear algebra, and so can benefit from some of the algorithms alluded to above. This area is considered particularly attractive due to the obvious economic value of solving real-world problems.
For some specialized variants of these problems, quantum computers can offer superpolynomial speedups.
Many problems can be phrased as graph problems. A graph consists of vertices and edges (also often called nodes and links). The figure below is a simple graph consisting of nine vertices and fourteen links.
If the letters a to i are cities, and the number above or next to each line is the number of kilometers between the pair of cities, what is the best way to get from a to e? This is the shortest path problem.
Is it actually possible to get all the way from a to e? In this simple example it is easy to see that the graph is connected, that is possible to get from any vertex to any other, but in larger graphs it can become a harder problem.
On the left, a is connected to b and h, and b and h are also connected to each other, forming a triangle. How many triangles are there in this graph? Sometimes, it is important to know.
Efficient classical algorithms exist for many of these questions, but quantum algorithms that offer a polynomial speedup have been developed.
More generally, one of the most important uses of classical computers is to solve problems in optimization. The field known as operations research involves optimizing some value, often for business purposes: reducing the amount of material used in a factory, or maximizing profit based on some set of assumptions.
Organizations considering purchasing a (hypothetical) quantum computer will, in general, not care much about whether a particular algorithm is polynomial or exponential in running time. Instead, they care about how well it works for their particular problem, given the size of the problem and perhaps some of the characteristics of the input data.
Quantum algorithms for a variety of specialized optimization problems already exist, but how well they work for different problems in the real world is not yet well understood. Researchers are probing this area actively, and it is considered to be one of the most compelling reasons for building quantum computers.
© Keio University