Machine learning involves classifying data, in order to make decisions. “Efficient” classical algorithms for finding full solutions exist, but the sheer volume of data means that computation times are high. Assuming the availability of certain supporting technologies or constraints on the data, quantum algorithms can answer certain questions about the data exponentially faster than the best known classical algorithms.

Matrix Operations

In high school (or junior high school) algebra, you learned that a simple equation can represent a line, and how to solve pairs of equations, like

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

to find the answer (x = 1), (y = 1), indicating the place where the two lines intersect. With a larger set of equations and a larger set of variables, we write them as a matrix, and combine them in equations with vectors. A common operation is to try to find (x) in the equation (Ax = b), where (A) is a matrix that represents the left hand side of a set of equations, (b) is a vector representing the right hand side of the equations, and (x) is a vector of variables for which we are trying to find values.

The mathematical field of linear algebra concerns itself with matrices and vectors, and these techniques figure prominently in artificial intelligence, especially the field of machine learning, in which computers are programmed to learn from data.

Machine learning

Machine learning involves creating a classifier that will tell us whether a datum belongs to a particular class. We can make a distinction between the strategy used to create the classifier, and the details of the problem being solved.

Classifiers learn how to do their work. They use training data to find the best set of parameters for the problem at hand, then the training data is discarded before the classifier is used for production work. Supervised learning uses data that someone else has already classified (e.g., “this is malware, that isn’t”) and learns what characteristics of the data define a class. Unsupervised learning instead looks at the data and figures out how many different groups, or clusters, there are in the data. Reinforcement learning is more iterative, with the program learning how to be rewarded in real-world situations.

There are many mathematical classification techniques. (k)-nearest neighbor, support vector machines (SVM), and (k)-means clustering are relatively straightforward, and all can be partially solved or supported using a quantum algorithm known as HHL.

The HHL algorithm

In 2009, Aram Harrow, Avinatan Hassidim and Seth Lloyd found an algorithm (called, naturally enough, HHL) that helps us prepare a state (|xrangle = A^{-1}|brangle), where (A^{-1}) is the inverse of the matrix (A). At first glance, it might appear that it will “solve for (x)”, as we are often told to do in math problems, but there is a catch involving the data representation.

In these linear algebra problems, the natural data representation is to write down the data as a large vector. We might have, for example, a billion data items, which we can write as a vector with a billion entries. Writing down this vector naturally requires a billion time steps. HHL, instead, encodes each of those data elements in the amplitude of a single quantum value in a register, using a superposition of all one billion elements. Because (2^{30} > 10^9), we can store all of our data in 30 qubits, total, instead of a billion separate memories. Of course, the register has to be normalized.

Then we can calculate on all billion values at the same time, in superposition. In the above equation, using HHL, we start with our data in the superposition of (|brangle), and end with the superposition of all results in (|xrangle). The catch, as in all quantum algorithms, is that we can’t extract all of the data values. Instead, once again, we design our algorithm to create interference in a pattern that tells us something about the original data distribution. For example, we can learn that the 1,117th entry in the vector (x) is the largest data element. Or, treating the whole data set as a vector in an (n)-dimensional space (in this case, a 30-dimensional space), we can find the distance between (|xrangle) and some other vector (|zrangle).

If we use HHL properly for certain tasks, it is exponentionally faster than the best known classical algorithm for the same task. However, there are caveats to achieving that performance, and researchers have not yet been able to rule out that efficient classical algorithms exist for the same tasks when all of the constraints are taken into account.

QRAM

An important caveat is the preparation of the vector (|brangle) containing our original data. If it is a superposition of data values we have stored in a classical computer, then it can take a billion time steps to create a superposition of all billion values, and we have discarded our quantum algorithm’s performance advantage. This is the basis of our assertion in the first week that quantum computers in general aren’t good at big data problems.

However, Giovannetti, Lloyd and Maccone proposed piece of hardware that, if developed, could be used to prepare (|brangle) quickly: a quantum random access memory, or QRAM. In a normal (classical) memory (RAM), we give the memory an address, and it returns the value stored at that address. A QRAM is designed to hold classical data but allow quantum queries. If we can give it an address in superposition, and it returns us the data also in superposition, then we can create our superposition for (|brangle) using only a few Hadamard gates and a single query to the QRAM. Of course, the creation of the data itself requires (O(N)) time for (N) data items, but then we can run many programs repeatedly against the same data, amortizing that cost, as opposed to a purely quantum memory, where the superposition is destroyed on every run and we must recreate it.

Other algorithms

HHL planted the seed, but the more practical algorithms have been in follow-on work and in other work. Lloyd, Mohseni and Rebentrost created algorithms for supervised and unsupervised machine learning. Ambainis extended HHL to be more practical with complex datasets. HHL’s running time depends in part on the precision you need in the answer; Childs, Kothari and Somma showed how to reduce this dependence dramatically.

Within the field of quantum algorithms, quantum machine learning and more broadly quantum artificial intelligence, including such topics as quantum neural networks, is perhaps the fastest-moving area. Given the importance of the problems being attacked, if the dependence on large data sets can be resolved, quantum AI has the potential to drive the broad adoption of quantum computers.

線形システムアルゴリズム

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

行列演算

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

(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は量子コンピュータの幅広い応用を促進する可能性があります。