Machine Learning and Other Algorithms/機械学習とその他のアルゴリズム

ここまで、量子化学、素因数分解、汎用検索と、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 は三角形を形成しています。ではどれだけの数の三角形がこのグラフの中にあるでしょうか？一見すると、三角形を探しても得があるようには思えませんが、グラフ問題においては、それを知ることは時として重要なこととなるのです。

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

最適化

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

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

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