8-1. オラクル

本節では、探索問題を一般的に扱い、その計算量を考えるために必要な概念であるオラクルを紹介する[1]。

オラクルとは

探索問題とは、一般に \(N\) 個の要素から \(M\) 個の解を見つける問題である。例えば、人名がたくさん入った名簿データベースがあって、その中から佐藤さんだけ取り出したい、といった問題である。 \(N\) 個の要素が \(n\) 桁ビット列の \(x=x_1\ldots x_n\) でラベル付けされているとして、 この探索問題に対応する「古典オラクル」を次のように定義する。

\[\begin{split}f(x) = \begin{cases} 1 \:\:\text{(xは解)} \\ 0 \:\: \text{(xは解でない)} \end{cases}\end{split}\]

つまり、 \(f\) は要素のラベル \(x\) を与えるとその要素が解であるかを二択で教えてくれる関数である。 人名の例でいうと、名簿\(_0\)=高橋、名簿\(_1\)=佐藤のとき、\(f(0)=0, f(1)=1\) となる。 オラクル (Oracle) は日本語で神託という意味であり、中身はブラックボックスだけれどとにかく答えを教えてくれる抽象的な存在で、それがどのように実装されているかは気にしない（実際に実装が存在する必要もない）。 探索問題を解く古典アルゴリズムの計算量は、\(x\) が解であるかを古典オラクルに尋ねる回数で評価する。こうすることで、問題の子細に依らない統一的な評価が可能になる。

一方、探索問題を解く量子アルゴリズムの計算量は、次の（量子）オラクル \(\mathcal{O}_f\) を呼ぶ回数で評価する。

\[|x \rangle |q \rangle \xrightarrow{\mathcal{O}_f} |x \rangle |q \oplus f(x) \rangle.\]

ここで入力状態 \(|x \rangle\) は入力ビット列 \(x\) を計算基底で表した状態、\(|q \rangle\) は補助ビット、\(\oplus\) はモジュロ2の加算（XOR演算）である。 \(x\) が探索問題の解であるかは、補助ビット \(q\) が反転したかどうかをチェックすればわかる：\(|x \rangle |0 \rangle \xrightarrow{\mathcal{O}_f} |x \rangle | f(x) \rangle\). 他にも、補助ビットを \(|- \rangle = (|0 \rangle - |1 \rangle)/\sqrt{2}\) とセットしておけば、

\[|x \rangle |- \rangle \xrightarrow{\mathcal{O}_f} (-)^{f(x)}|x \rangle |- \rangle\]

となるから、\(x\) が探索問題の解の時にのみ状態の位相が反転するようにもできる。

オラクル \(\mathcal{O}_f\) の最も大きな特徴の一つは、入力状態が重ね合わせであってもそのまま動作することである。 例えば、入力状態として全ての状態の重ね合わせ \(N^{-1/2} \sum_x |x\rangle\) をとり、補助ビットを \(|-\rangle\)とすれば、

\[\frac{1}{\sqrt{N}} \sum_x |x \rangle |- \rangle \xrightarrow{\mathcal{O}} \frac{1}{\sqrt{N}} \sum_x (-)^{f(x)}|x \rangle |- \rangle\]

となる。このような、\(x\)が解の時のみ位相が反転する性質をうまく用いて解を見つけるのが、次節で紹介するグローバーのアルゴリズムである。

参考文献

[1] M. A. Nielsen and I. L. Chuang, “Quantum Computation and Quantum Information 10th Anniversary Edition“, University Printing House の 6.1 The quantum search algorithm