## Want to keep learning?

This content is taken from the Keio University's online course, Understanding Quantum Computers. Join the course to learn more.
1.10

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

# 機械学習とその他のアルゴリズム

ここまで、量子化学、素因数分解、汎用検索と、1990年代に開発された重要な4つの（古典的）量子アルゴリズムうちの3つについて学んできました。Shorにより、より洗練されたものとなりました。（４つ目に挙げられるDeutsch-Jozsaアルゴリズムは、４つのうちで最初に形成されたアルゴリズムで、量子スケーリング等について詳しく説明されていますが、実用的ではないため、このコースでは省略しています。）Shorは既に実用レベルですが、さらに様々な検索技術は革新的に進歩しており、量子化学もここ１０年ほどで急速に発展してきています。しかし、これらの用途は量子コンピュータの役割のほんの一部でしかありません。

ここでは、量子コンピュータその他の潜在的な使い道について簡単に紹介していこうと思います。アルゴリズムの詳細や、なぜ量子コンピュータが古典的コンピュータより早く解を得られるかを理解するためには、より多くの知識を必要とするため、後の章で取り上げることにします。第３週に、より詳細にアルゴリズムについて学び、それらが解き得る問題に関して紹介していく予定です。

## 機械学習

この領域においても、問題によっては超多項式関数的に速く解を得ることが可能です。

## グラフ理論

もし a から i が都市で、線の隣にある数字が、その距離を表しているとしたとき、a から e へ行く最善のルートはどれでしょうか？こういった問題を一般に最短経路問題と呼びます。

では、a からe へ行く全ての道順を確認することはできるでしょうか？この例のような簡単なグラフの問題であれば、どの頂点からの経路も容易に確認することができますが、都市（ノード）と道（リンク）が増えれば増えるほど、最短経路の計算が困難になってくることは容易に想像が付きます。

もちろん、このような問題を効率よく解く既知の古典的アルゴリズムは多数存在していますが、同じ問題を多項式関数的に速く解く量子アルゴリズムも考案されています。

## 最適化

ある特定最適化問題を解くのに特化した量子アルゴリズムはすでに存在していますが、その技術が実社会に存在する個々の問題にどこまで応用できるかはまだよく分かっていません。研究者たちは、この領域の研究に非常に熱心で、それこそが量子コンピュータを創造しようとする最も大きな動機でもあるのです。