# 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.

## Linear Algebra

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 \(f(A)\vec{b}\) for some function \(f\), some matrix \(A\), and some vector \(\vec{b}\), for example. They can also calculate approximate values of exponents of matrices, \(A^m\).

For some specialized variants of these problems, quantum computers can offer superpolynomial speedups. For others, the speedup is polynomial.

## Machine Learning

*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.

## Graph Algorithms

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.

## Optimization

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