Groverのアルゴリズムとオラクル
Groverのアルゴリズムという量子アルゴリズムがあります。
wikipediaから引用します。
グローバーのアルゴリズムとは、N個の要素をもつ未整序データベースの中から指定された値を検索する探索問題を解くための量子コンピュータのアルゴリズムであり、$O(\sqrt{N})$のオーダーの計算量と、$O(\log(N))$のオーダー（ランダウの記号も参照）の記憶領域を消費する。1996年にロブ・グローバー（英語版）によって開発された。
Wikipedia
Dojo, 8-2. グローバーのアルゴリズム
QAA,Grover,QAEを勉強する。
Groverのアルゴリズムでは「オラクル」というブラックボックスを使います。
しかし、この「オラクル」というものが曲者で、
「これは解を知っていないと作れないのでは。インチキだ！」
と言いたくなる例・説明が頻出し、初学者を地獄へ突き落とします。
この記事では、この点をちゃんと説明したいと思います。
この話は、Nielsenの教科書に書いてあります。
Nielsen et al., Quantum Computation and Quantum Information
オラクル
オラクルとは、$x$が解であるときは$1$を返し、そうでないときは$0$を返すような関数$f(x)$のことです。
量子計算では、このオラクルが量子並列的な性質を満たすとします。
すなわち、解の候補が2つあった($x_a$,$x_b$とします）場合に、その重ね合わせ状態$x_a + x_b$をオラクルに入力することができ、
その出力もまた重ね合わせである$f(x_{a})+f(x_{b})$になるということです。
オラクルを使えば、解の候補を同時に複数試す事ができます。Groverアルゴリズムはこれを使って解を効率的に探索します。
例えば
Dojo, 8-2. グローバーのアルゴリズム
では、5量子ビットの状態に対して、解が'11111'である状態をGroverアルゴリズムで発見しています。
オラクルは、解が'11111'である状態をマーキングさせるものとして定義されています。
オラクルは解を知っているか？
先のDojoの例だと、解が'11111'であることを知っていてオラクルを用意しています。
解を知っているのであれば、量子アルゴリズムなど必要ないのでは？
という当然の疑問がわきます。そのとおりです。解を知っていないと動かないアルゴリズムは意味がありません。
しかしオラクルは解を知らないと作れないわけではありません。
例えば、次のような問題を考えます。
- 自然数Nを素因数分解せよ
このとき、オラクルに求められることは、
与えられた素数$p$に対して、それがNの約数であるかチェックし、約数であれば1を返し、そうでなければ0を返せ
です。これは、明らかに$N$の素因数分解を知らなくてもできることです。実際に$p$ で割ってみればいいからです。
オラクルは与えられた$p$が解であるかを検証できればいい（条件を満たすかどうかを検証できればいい）のです。
解を知っている(know)ことと、与えられた解の候補を試す(recognize)ことは難易度が違います。
別の例をあげましょう。
- 方程式$x^{2}-2x+1=0$の解$x$を求めよ
この場合もオラクルの役割は
与えられた数$x$に対して、それが方程式を満たすのかチェックし、満たすのであれば1を返し、そうでなければ0を返せ
です。
オラクルは解を知っているのではなく、解の候補が与えられた時にそれが解であるか否かを検証できるだけなのです。
先のDojoの例だと、もっとそれらしい問題設定は、
次の性質を満たす2進数5桁のbit列xxxxxを見つけよ。任意の隣り合うbitは一致しており、かつ右端のbitは1である。
明らかに解が11111であることに気づきますが、、とにかくGroverのアルゴリズムで解くとすると、
- 隣り合うbitが同じであるかどうかを検証するオラクル
- 右端のbitが1であるかどうかを検証するオラクル
を持ってきて、これを組み合わせれば良いでしょう。
どこにも 解が11111である という情報は登場しませんね。
実際にはもっと複雑な制約条件が与えられ、解がわからない状態を扱うわけです。
解を検証できるのであれば、ただちに解がわかるのではないか？
まだ、次のような疑問を持つかもしれません。
オラクルは解かどうかを検証できるのだから、手当たりしだいに候補を与えて、たまたま解だったらそこで処理を終わればいい。量子アルゴリズムの意味は？
これは正しいです。しかし解の候補が$N$個あるとき、最悪で$N$回程度オラクルを使う必要があります。
量子アルゴリズム(Groverのアルゴリズム）では、解の候補が$N$個あるとき、最悪で$\sqrt{N}$回程度(量子)オラクルを使えば済みます。
なぜこんなことができるかというと、それは先の述べた性質によるものです。
Groverのアルゴリズムでは「オラクル」というブラックボックスを使います。
オラクルとは、$x$が解であるときは$1$を返し、そうでないときは$0$を返すような関数$f(x)$のことです。
量子計算では、このオラクルが量子並列的な性質を満たすとします。
すなわち、解の候補が2つあった($x_a$,$x_b$とします）場合に、その重ね合わせ状態$x_a + x_b$をオラクルに入力することができ、
その出力もまた重ね合わせである$f(x_{a})+f(x_{b})$になるということです。
オラクルを使えば、解の候補を同時に複数試す事ができます。Groverアルゴリズムはこれを使って解を効率的に探索します。
しかしオラクルの量子版を具体的に可能な量子操作の組み合わせで実現することはそれほど簡単ではないと思います。
しかし、幸いなことにも以下の事実があります。
「古典論理演算において万能な論理操作であるNANDを、量子ゲートで表現する方法がある。よってすべての古典論理演算は量子計算で実現可能である。
もちろん、実現可能なだけであって、少ないリソースで実現できるとはいっていません。
オラクル部分の処理が”重い”と、いくらGroverアルゴリズムを使ってオラクル呼び出し回数を減らしても、総計算コストは高いでしょう。
実際、素因数分解のところで例に出した 約数かどうかチェックするオラクル を用いた方法は、既存の古典ベストアルゴリズムに比べるとあまり賢くないそうです。
結論
オラクルは解を知らなくても作れる。
解を知っている(know)ことと、与えられた解の候補を試す(recognize)ことは難易度が違います。
オラクルはrecognizeができれば良いのです。
が、アルゴリズムの説明段階では解を知ってて作るオラクル(know)が出てくることが多く、混乱を招いているのです。