本節では、探索問題を一般的に扱い、その計算量を考えるために必要な概念であるオラクルを紹介する[1]。個の解を見つける問題である。人名がたくさん入った名簿データベースがあって、その中から佐藤さんだけ取り出したい、といった問題である。この探索問題に対応する「古典オラクル」を次のように定義する。与えるとその要素が解であるかを二択で教えてくれる関数である。日本語で神託という意味であり、中身はブラックボックスだけれどとにかく答えを教えてくれる抽象的な存在で、それがどのように実装されているかは気にしない(実際に実装が存在する必要もない)。解であるかを古典オラクルに尋ねる回数で評価する。することで、問題の子細に依らない統一的な評価が可能になる。モジュロ2の加算(XOR演算)である。探索問題の解の時にのみ状態の位相が反転するようにもできる。大きな特徴の一つは、入力状態が重ね合わせであってもそのまま動作することである。\rangle\]となる。このような、\(x\)が解の時のみ位相が反転する性質をうまく用いて解を見つけるのが、次節で紹介するグローバーのアルゴリズムである。