Skip main navigation

New offer! Get 30% off one whole year of Unlimited learning. Subscribe for just £249.99 £174.99. New subscribers only. T&Cs apply

Find out more

Linear Systems Algorithms/線形システムアルゴリズム

Linear Systems Algorithms/線形システムアルゴリズム
決断を下すために、何かデータを分類するというのは機械学習で可能なタスクの一種です。完全な解を見つけるための「効率的な」古典的アルゴリズムが存在しますが、データ量が膨大なので計算時間がかかります。 機械学習を支える技術やデータに特定の制約があると仮定すると、量子アルゴリズムは、既知の古典的なアルゴリズムよりも指数関数的に速く、データに関する特定の質問に答えることができます。

行列演算

高校(または中学校)の代数では、簡単な方程式は線を表すことができることと、連立方程式の解き方を学びました。

(3x + 4y = 7)
(4x + 3y = 7)

(x = 1)、(y = 1)の答えを見つけるためには、2つの線が交差する場所を示します。 多くの方程式と多くの変数が存在するなら、それらを行列として記述し、ベクトル方程式にします。 一般的に行う演算は、方程式(Ax=b)の(x)を見つけることです。このとき、(A)は方程式の左辺表し、(b)は方程式の右辺を表すベクトルで、(x)は最終的に値を求めたい変数です。

線形代数の数学的な分野は、それ自体が行列やベクトルに関係しており、これらの技法は人工知能、特にコンピュータがデータから学習するようにプログラムされた機械学習の分野で顕著です。

機械学習

機械学習では、データが特定のクラスに属するかどうかを示す分類器を作成します。分類器の作成に使用された戦略と、解決されている問題の詳細を区別することができます。

分類器は、自分の仕事のやり方を学びます。分類器は訓練データを使用して、手元の問題に最適な パラメータのセットを見つけ、訓練データは実際の分類を行う前に破棄されます。教師あり学習は、他の誰かが既に分類したデータ(「これはマルウェアかそうでないか」など)を使用して、データのどの特性がクラスを定義するかを学習します。教師なし学習は代わりにデータを調べ、データ内にいくつのグループまたはクラスタが存在するかを把握します。強化学習は反復的で、実際の状況でどのように報酬を受けるかを学習します。

これらには多くの数学的分類手法が存在します。(k)近傍法、サポートベクターマシン(SVM)、および平均ク ラスタリングは比較的単純であり、HHLとして知られる量子アルゴリズムを使用してすべての手法を部分 的に解決またはサポートすることができます。

HHLアルゴリズム

2009年には、Aram Harrow、Avinatan Hassidim、Seth Lloydが、A行列の逆行列(A^{-1})である、(vert xrangle = A^{-1}vert brangle)状態を準備するのに役立つアルゴリズム(自然に十分なHHLと呼ばれる)を発見しました。一見すると、数学の問題でよく言われているように、「(x)を解く」と思われるかもしれませんが、データ表現に関わる話があります。

これらの線形代数問題では、自然なデータ表現はデータを大きなベクトルとして書き出すことです。たとえば、たとえば、10億のデータ項目があった時、これは10億項目のベクトルとして記述できます。 このベクトルを書き留めるには、必然的に10億の時間ステップが必要です。代わりに、HHLは、これらのデータ要素のそれぞれを、レジスタ内の単一の量子値の振幅で符号化し、10億の要素すべてを重ね合わせて使用​​します。なぜなら、10億の別々の記憶の代わりに、すべてのデータを30量子ビット(合計)で保存できるからです。もちろんその際、レジスタは正規化されなければなりません。

次に、重ね合わせ状態を利用し、すべての10億の値を同時に計算することができます。上の方程式では、HHLを使用して、データを重ね合わせてから始め、すべての結果を重ね合わせて終了します。キャッチというのは、すべての量子アルゴリズムと同様に、すべてのデータ値を抽出することができな いということです。代わりに、元のデータ配信について何かを示すパターンで干渉を生成するアルゴリズムを設計します。たとえば、ベクトルの1,117番目のエントリが最大のデータ要素であることがわかります。あるいは、データセット全体を次元空間(この場合は30次元空間)のベクトルとして扱うと、そのベクトルと他のベクトルの距離を見つけることができます。

HHLを特定のタスクに適切に使用すると、同じタスクで最もよく知られている古典的なアルゴリズムよりも速くなります。しかし、その性能を達成するための障壁があり、研究者はすべての制約 を考慮に入れて、同じタスクに対して効率的な古典コンピュータを超えることはできていません。

QRAM

データを用意する上で注意しなければならない重要な点としては、元のデータを含むベクトルの準備です。それが古典的なコンピュータに保存され たデータ値の重ね合わせであれば、10億の値を重ね合わせるのに10億ステップかかることがあり、 量子アルゴリズムの性能上の利点を活かすことができません。これは最初の週に量子コンピュータが大きなデータ問題に苦しんでいるという私たちの主張の基礎です。

しかし、Giovannetti、Lloyd、Macconeは、開発されれば、迅速に準備するために使用できるハードウェアの一部を提案しています:量子ランダムアクセスメモリ、すなわちQRAMというものです。通常の(古典的な)メモリ(RAM)では、メモリにアドレスを与え、そのアドレスに格納されている値を返します。 一方QRAMは、古典的なデータを保持しつつも、量子クエリを可能にするように設計されています。重複してアドレスを与えることができ、データを重ね合わせて返すと、いくつかのアダマールゲートとQRAMへの単一のクエリだけを使用して重畳を作成することができます。もちろん、データ自体の作成には(O(N))の時間が必要ですが、すべての実行で重畳が破棄される純粋な量子メモリ ではなく、同じデータに対して複数のプログラムを繰り返し実行することができます。それを再作成 する必要があります。

他のアルゴリズム

HHLは量子アルゴリズムの先駆けとなりましたが、より実用的なアルゴリズムを作るにはさらなる作業が必要となります。Lloyd、Mohseni、Rebentrostは教師なし機械学習のアルゴリズムを作成しました。 Ambainisは、複雑なデータセットで利用できるように、HHLをより実用的に拡張しました。 HHLの実行時間は、答えに必要な精度に一部依存します。 Childs、Kothari、Sommaはこの依存を劇的に減らす方法を示しました。

量子アルゴリズムの分野では、量子機械学習と、量子ニューラルネットワークのような より汎用的な量子人工知能が量子アルゴリズムの中でもおそらく最も高速化可能な領域です。現在様々に解決しようとされている問題の重要性が認められ、大きなデータセットへの依存を解決できれば、量子AIは量子コンピュータの幅広い応用を促進する可能性があります。

© Keio University
This article is from the free online

量子コンピュータ入門

Created by
FutureLearn - Learning For Life

Reach your personal and professional goals

Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.

Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.

Start Learning now