非構造化探索

まとめ

グローバーのアルゴリズムが解く問題の説明から始めましょう。 以降の議論では、$\Sigma = \{0,1\}$ を二値アルファベットとして表します。

次のような関数を考えます。

$$f:\Sigma^n \rightarrow \Sigma$$

これは、長さ $n$ の二値文字列からビットへの関数です。 この関数は効率的に計算できると仮定しますが、それ以外の点では任意であり、特定の構造や都合のよい実装を持つとは限りません。

グローバーのアルゴリズムが行うことは、$f(x) = 1$ となる文字列 $x\in\Sigma^n$ を探索することです。 このような文字列を探索問題の解と呼びます。 解が複数存在する場合はそのうちのいずれか一つが正しい出力とみなされ、解が存在しない場合は「解なし」と報告することが正しい答えとなります。

このタスクが非構造化探索問題と呼ばれる理由は、$f$ が何らかの特定の構造を持つとは仮定できないためです。 整列されたリストを探索するわけでも、探索を容易にするために設計されたデータ構造を使うわけでもなく、本質的には干し草の山の中から針を探すような作業です。

直感的には、$f$ を計算する非常に複雑なブール回路があり、選択した入力文字列に対してその回路を簡単に実行できる状況を想像できます。 しかし、回路があまりにも複雑なため、選択した入力文字列に対して評価する能力を超えて、回路を調べることで意味を見出す見込みはありません。

このような探索タスクを古典的に実行する一つの方法は、$\Sigma^n$ のすべての文字列 $x$ を順番に調べ、それぞれに対して $f$ を評価して解かどうかを確認することです。 以降、便宜上

$$N = 2^n$$

と書くことにします。 $\Sigma^n$ には $N$ 個の文字列があるため、すべてを網羅するには $f$ の $N$ 回の評価が必要です。 選択した入力に対して $f$ を評価することのみに制限されているという前提のもとでは、成功を保証したい場合、決定性アルゴリズムでできることはこれが最善です。 確率的アルゴリズムでは、$f$ への入力文字列をランダムに選ぶことで時間を節約できるかもしれませんが、高確率で成功させたい場合はやはり $O(N)$ 回の $f$ の評価が必要です。

グローバーのアルゴリズムは、わずか $O(\sqrt{N})$ 回の $f$ の評価で高確率にこの探索問題を解きます。 明確にしておくと、これらの関数評価は重ね合わせの状態で行われる必要があります。これは、ドイチュのアルゴリズム、ドイチュ＝ジョザアルゴリズム、サイモンのアルゴリズムを含む量子クエリアルゴリズムレッスンで議論されたクエリアルゴリズムに類似しています。 それらのアルゴリズムとは異なり、グローバーのアルゴリズムは反復的なアプローチを採ります。すなわち、入力文字列の重ね合わせに対して $f$ を評価し、その評価と干渉パターンを生成する他の操作を交互に行うことで、$O(\sqrt{N})$ 回の反復後に高確率で（解が存在する場合は）解に到達します。

形式的な問題の定義

グローバーのアルゴリズムが解く問題を、計算のクエリモデルを用いて形式化します。 すなわち、関数 $f:\Sigma^n\rightarrow\Sigma$ へのアクセスは、通常の方法で定義されたクエリゲートを通じて行われると仮定します。

$$U_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle$$

ここで、$x\in\Sigma^n$ および $a\in\Sigma$ です。 これは標準基底状態に対する $U_f$ の作用であり、一般的な作用は線形性によって決まります。

量子アルゴリズムの基礎レッスンで議論されたように、$f$ を計算するブール回路があれば、そのブール回路の記述を $U_f$ を実装する量子回路に変換できます（計算の開始と終了を $\vert 0\rangle$ 状態とするいくつかのワークスペース量子ビットを使用します）。 したがって、グローバーのアルゴリズムが解く問題の形式化にクエリモデルを使用しているものの、このモデルに限定されるわけではありません。ブール回路が用意されている任意の関数 $f$ に対してグローバーのアルゴリズムを実行できます。

以下は問題の正確な定義です。解、すなわち $f$ を $1$ と評価させる文字列 $x$ を探索しているため、この問題は探索（Search）と名付けられています。

探索（Search）

入力：関数 $f:\Sigma^n\rightarrow\Sigma$
出力：$f(x) = 1$ を満たす文字列 $x\in\Sigma^n$、またはそのような文字列 $x$ が存在しない場合は「解なし」

これは約束問題ではないことに注意してください。関数 $f$ は任意です。 ただし、解がちょうど一つ存在することが保証されている次の約束問題の変種を考えると便利です。 この問題は量子クエリアルゴリズムレッスンで約束問題の例として登場しました。

一意探索（Unique search）

入力：$f:\Sigma^n \rightarrow \Sigma$ の形式の関数
約束：$f(z) = 1$ となる文字列 $z\in\Sigma^n$ がちょうど一つ存在し、$x\neq z$ のすべての文字列 $x$ に対して $f(x) = 0$
出力：文字列 $z$

また、同じレッスンで言及されたOr問題は探索と密接に関連していることにも注意してください。 その問題では、実際に解を見つけるのではなく、解が存在するかどうかを判定することが目標です。