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は既に実用レベルですが、さらに様々な検索技術は革新的に進歩しており、量子化学もここ１０年ほどで急速に発展してきています。しかし、これらの用途は量子コンピュータの役割のほんの一部でしかありません。

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

線形代数学

行列や、ベクトルについて計算を行うことを、線形代数学と呼びます。これらの理論はビデオゲーム内の物体の運動の再現や、経済の分析、そして、あらゆる物理的・工学的問題を解決する上で応用されており、量子コンピュータを語る上でも必要不可欠な理論です。

量子コンピュータを用いることで、多数の線形問題をより高速に処理し、解を得ることができます。 例えば、ある関数 (f)に行列(A)を代入した式に、ベクトル(b)をかけ合わせることや、２つの行列の掛け算などといった問題がそれに値します。 また、ある行列Aのm乗、(A^m)の近似解を素早く計算することもできます。

問題によっては超多項式関数的に高速に、もしくは多項式関数的に高速に解を計算することが可能です。

機械学習

機械学習は人工知能の一種で、特に深層学習として知られており、現実世界のオンラインサービスや、音声認識、自動翻訳等に革命を起こしている技術です。一般的に、それらの技術は線形代数をベースとしており、上記と同様の理由から量子コンピュータによる恩恵を受けることが可能とされています。この領域は特に、現実世界に存在する問題を解決することによる明白な経済的価値に対して、多くの注目を集めています。

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

グラフ理論

世の中に存在する多くの問題は頂点(ノード)と辺(リンク)からなるグラフ問題に置き換えることができます。 下の図は９個の頂点と、１４本の辺からなるグラフの例です。

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

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

図の左側において、a は b と h とつながっており、 b と h はお互い同士もまたつながっているため、 a と b と h は三角形を形成しています。ではどれだけの数の三角形がこのグラフの中にあるでしょうか？一見すると、三角形を探しても得があるようには思えませんが、グラフ問題においては、それを知ることは時として重要なこととなるのです。

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

最適化

最適化問題を解くことは、古典的コンピュータの最も重要な用途の一つです。「オペレーションズリサーチ」と呼ばれるこの分野は、様々な値を最適化するもので、しばしばビジネスの目的でも使われます。例えば、工場で使われる材料削減のための計算や、ある仮定のもとでの利益を最大化するための計算に用いられることがあります。

量子コンピュータの購入を検討している会社は特定のアルゴリズムの実行時間が、多項式的に高速化されるか、指数関数的に高速化されるかなどはさほど気にしていません。そのかわり、。そのかわり、特定の問題を解く場合、問題の規模サイズや、入力の値の違いによってどれだけうまく動作するかという点に重きを置いています。

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