量子コンピュータに入門してるその3 量子探索アルゴリズム

κeenです。前々回、前回に引き続き量子コンピュータと量子通信を読んでいます。 今回は6章の量子探索アルゴリズム。読み切ってから少し間が空いてしまいましたが頑張ってまとめます。 勉強中の身で自分の理解を書いているのでみなさん内容は一切信用しないでくださいね。

前回が位相を使って計算する話だったのに対して今回は振幅(観測確率)を上手く調整して目的の値を観測する話です。

Groverのアルゴリズムというやつです。 「探索空間の要素を1つ1つ検査してそれが解足りうるならその値を返す」操作を $O(N^{\frac{1}{2}})$ で実行します。 計算複雑性理論を全然知らないんですがこれって要はNP完全問題を $O(2^{n/2})$ で解けるってことでいいんですよね？ NPは「探索空間の要素が与えられたときにそれが解であるかは簡単に(多項式時間で?)決定できる」で、その自明な解法が「探索空間の要素を1つ1つ検査してそれが解足りうるならその値を返す」という認識なんですが合ってますか？

さて、Groverのアルゴリズムは計算複雑性的に古典コンピュータの性能を上回る例として有名なので割愛します。重ね合わせ状態に対して繰り返しオラクルを使った演算を適用することで解の観測確率を上げます。 以下個人的に興味深かった点を挙げます。

1つ。解釈が面白かったです。Groverのアルゴリズムは、時間発展し問題の解に状態が収束する系を考え、それをエミュレーションしていると捉えられます。 4章のところで量子コンピュータの有用性の1つに量子状態のシミュレーションが挙がっていたので伏線だった模様。

1つ。解の観測確率を1/2にするために探索空間を水増しする処理が入る点。Groverのアルゴリズムは解集合の濃度が探索空間の濃度の1/2以下の仮定を置いているため、解集合があらかじめ分からない場合は探索空間を水増しすることで濃度を1/2以下にします。これはオラクルの自明な拡張で実現できます。操作も簡単ですし計算上それで速くなるのは確かめられるのですが直観に反していて面白いですね。

最後。これ重要で、アルゴリズム中の反復の中でオラクルを参照している点。このオラクルは問題の検算をしている訳なので多少の複雑な計算が予想されます。自分は量子コンピュータはアクセラレータのつもりでいたのでそういう複雑な計算はは古典コンピュータのものと思っていました。しかしGroverのアルゴリズムでそういった計算が必要になるなら量子コンピュータに思ったより複雑な演算が必要になるのかもしれません。このあたりはI巻に書いてそうな雰囲気なのでやっぱ読まないとだめそうですね。

Groverのアルゴリズム以外にも量子計数(数え上げ)やブラックボックスアルゴリズムなども載っているのですがちょっとおもしろかったのが量子データベース探索。 データベースというからには流石にデータはレジスタではなくメモリにあるのですが、量子アルゴリズムを使うには重ね合わせができないと面白いことができません。 メモリ素子も量子重ね合わせができるハードウェアを考えるのかなと思ったらそうではないようでした。 LOAD するアドレスを重ね合わせにして、メモリから複数の値を読み出しその複数の値を重ね合わせ状態にしてレジスタに返すマシンを考えていました。こっちの方がまだ実現可能性がありそうでいいですね。

引き続き7章を読みます。