GitHubここで、量子線形システム問題にまつわる少し発展的な話題を紹介する。これらのコラムの内容は本編の理解に必須ではないので、難しくて分からない場合は適宜飛ばして次の章に進んでほしい。量子計算機で効率的にシミュレートすることができる。ハミルトニアンの効率的なシミュレートは量子位相推定アルゴリズムやHHLアルゴリズムを行うための前提条件であるから、量子計算機は低ランクな行列に対して種々の高速なアルゴリズムを自然に実行できる。そのような応用の一つで、量子計算機は低ランクな行列の任意の行ベクトルに対し、Top-\(k\)特異値空間へ射影したベクトルからのL2サンプリングを行えるというものである。このサンプリング操作は、例えばWebサービスにおける購買履歴に基づくユーザへのアイテム推薦の操作に対応しており、、量子計算機は高速な推薦システムとして活用することができる。(注:ユーザへの推薦は、行がユーザ・列がアイテム・要素が指定ユーザが指定アイテムを好きかどうか、という嗜好行列(通常は低ランクだと仮定される)に基づいて行われる)しかし、一般に問題に低ランク近似可能性などの強い近似が加わった場合、通常の古典計算機での計算も高速になる点に注意しなければならない。近年、上記の量子推薦システムが行う操作は、種々のデータ構造やアルゴリズムを用いることで通常の計算機でも多項式時間で実現可能だということがわかった。このコラムでは、低ランクな行列に対する打ち切り特異値分解、および特異値空間に射影されたベクトルからのサンプリングが、通常の計算機だけでも行列のサイズに対して従来より指数的に高速になるという点について解説する。Tangによって行われたものである[1][2][3]。この研究は以下の個別の主要要素をつなげたものである。棄却サンプリング内積の推定まず、問題設定を提示し、そののち上記の三つについてそれぞれ解説し、これを組みあわせて低ランク近似した特徴量からのサンプリングが可能であることをコードを実行しながら概観する。低ランク近似からの特異値空間の射影サンプリングは以下のような問題として定義される。2^m\)の大きさの行列\(A\)を考える。行列\(A\)は全ての要素が0である。この時、以下の二つの操作がランダムな順序で\(q\)個要求される。値の更新\(A\)の\(i\)行\(j\)列の要素を\(v\)に更新する。射影サンプリング\(A\)の\(i\)行目の成分を\(A\)のTop-\(k\)特異値空間に射影したベクトル\(v\)を得る。v_l^2}\)の確率で出力する。\(k\)は高々\(O(n,m)\)である。上記に\(\epsilon\)の誤差を許容した時、高速に処理を行いたい。poly}(2^n,2^m)\)で行う方法である。poly}(q,n,m,\epsilon^{-1})\)の計算量で行いたい。poly}(q,n,m,\epsilon^{-1})\)で行うことができる。projectionというプロトコルを実施することで可能となる。poly}(q,n,m,\epsilon^{-1})\)で可能であるというものである。通常、我々がプログラムで配列を確保すると、メモリ上の連続的なアドレスに指定した容量の数列が確保される。ランダムアクセスメモリでは読み出しと書き込みはO(1)で完了できるため、通常はこの方法で確保される。したデータの保持の仕方は必ずしも高速とは限らない。従って、データに対する要求が単なる読み出しと書き込みに限らない場合、その目的に適した特殊なデータの保持方法が用いられる。これをデータ構造と呼ぶ。和に関するセグメント木はデータ構造の一種であり、データの更新、区間和の計算やサンプリングを高速に行うことができる。対象となるデータの大きさを\(N=2^n\)とする。2の累乗でない場合は、累乗になるまで末尾を0で埋める。\(2N\)の長さの配列を確保する。最初は\(2N\)個の要素は0で埋まっている。和のセグメント木では以下の4つの操作を行える。\(i\)番目のデータに値\(v\)を書き込む。\(i\)番目のデータを取り出す。全データの和を取り出す。a_j}\)の確率で取り出す。上記を通常の配列で愚直に行うと以下のようなコードになる。resultランダムな読み出し/書き込み等を行って、上記の関数をベンチマークしてみよう。(sec)")plt.xscale("log")plt.yscale("log")plt.legend()plt.show()他の関数の時間が定数でスケールする中、samplingだけが線形に時間がかかっていることがわかる。セグメント木では4つの命令を以下のように実装する。この処理は\(O(n)\)で終わる。この処理は\(O(1)\)で終わる。総和の取得\(a_0\)を返す。この処理は\(O(1)\)で終わる。サンプリング\(i=1\)とする。a_{i+1}}\)、\(b=1\)が\(\frac{a_{i+1}}{a_i+a_{i+1}}\)の確率で得られるサンプリングを行う。i+2^k\)と更新する。i+2^{k+1}\)と更新する。2^n\)となったら終了し、\(i-2^n\)を返す。この処理は\(O(n)\)で終わる。N)\)で行うことができる。実装は以下のようになる。self.size//2セグメント木をベンチマークしてみよう。(sec)")plt.xscale("log")plt.yscale("log")plt.legend()plt.show()先ほどの素朴なデータ構造の時間と比較してみよう。(sec)")plt.xscale("log")plt.yscale("log")plt.legend()plt.show()updateの関数はsegtreeの方が多少遅いものの、samplingのコストが圧倒的に減っていることがわかる。N)\)で行うことができる。これは通常のベクトルでは最悪で\(O(N)\)かかる。セグメント木は二つの要素間の演算がモノイド、すなわちゼロ元を持ち結合則が成り立てば様々な対象に対し適用することができる。\(f(a,b)=\min(a,b)\)とすることで区間最小値を求めるセグメント木を構築できる。セグメント木はベクトルに対するデータ構造だが、多少の拡張をすることで行列をセグメント木の集合として表すことができる。n\)行列を考えよう。\(i\)行目の長さ\(n\)のベクトル\(T_i\)をセグメント木\(S_i\)として保持する。\{|T_i|\}\)をセグメント木\(S'\)として保持する。\((i,j)\)要素を\(v\)に更新する。\((i,j)\)要素を取得する。与えられた行添え字\(i\)に対し、\(i\)行目のノルム\(|T_i|\)を取得する。T_{ij}}}\)の確率で得る。T_{ij}\)を取得する。|T_i|}\)の確率で得る。実装は以下のようになる。正方行列とは限らない行列\(A\)について、\(A=UDV^{\dagger}\)という分解を行う行列操作である。ユニタリ行列であり、\(D\)は実対角行列である。\(\dagger\)はエルミート共役(転置の複素共役)を表す。\(D\)の対角要素を\(A\)の特異値と呼ぶ。行列\(A\)の幅と高さの小さいほうの値が\(n\)である場合、特異値は\(n\)個あり、分解の計算量は\(O(n^3)\)である。\(U\)と\(V\)の\(i\)番目の列ベクトルを、\(A\)の\(i\)番目の特異値の左特異値ベクトル、右特異値ベクトルと呼ぶ。特異値分解はnumpyに標準で搭載されている。0.98272594]]計算コストは以下のようになる。(sec)")plt.show()打ち切り特異値分解とは、定数\(k\)について、特異値の集合のうち大きいものから\(k\)個の特異値と特異値ベクトルを取り出す操作である。定数\(k=n\)である場合は通常の特異値分解と一致するため、通常は\(k\)が\(n\)よりはるかに小さい場合をしばしば考える。k)\)のアルゴリズムである。k\)の行列\(B\)を作成する。計算コストは\(O(nk)\)。