
187
10
章
量子探索
6
章では、振幅増幅プリミティブを用いてレジスタ内の位相の違いを、検出可能な振幅の大きさ
(
magnitude
)の変化に変換する方法を示しました。振幅増幅を導入する際に、アプリケーションが
QPU
レジスタの値の位相を反転するサブルーチンを用意することが前提でした。単純な例では、仮の
措置として
flip
回路を使用しました。
flip
回路は、レジスタの値の位相を反転します。この章では、
自明ではない論理演算で量子状態の位相を反転する手法のいくつかを詳しく説明します。
量子探索(
Quantum Search
)は、ある種の問題に対して、振幅増幅によって
QPU
レジスタから確実
に解を読み取ることができるように、
flip
サブルーチンを修正するテクニックです。つまり、量子探
索は、振幅増幅の応用に他ならず、それは、あるクラスの問題の解を、レジスタの位相に書き込む非
常に重要なサブルーチンによって構成されます
*
1
。
量子探索で解くことができる問題は、
yes/no
を判定するサブルーチンを繰り返し評価するものです。
このサブルーチンから得られる
yes/no
の答えは、ほとんどの場合、従来型のブール論理表現の出力に
なります
*
2
。データベース内で特定の値を探索するような問題は、明らかにこの条件を満たします。こ
こで想定しているのは、入力データと探索するデータベース内の要素が一致する場合にのみ
1
を返すよ
うなブール関数です。このデータベース検索は、量子探索の応用のプロトタイプに相当するものであり、
開発者にちなんで ...