quantum-computing - 4 対 1 の関数で高確率の量子アルゴリズム

Answer 1

さて、x0 を選択すると が得られf(0) = f(a) = f(b) = f(a xor b)ます。そして、一致する他の入力はありませんf(0)。vしたがって、私たちは満足のいくものを探しているだけですv != 0, f(v) = f(0)。したがって、v他の条件を満たす場合に位相を反転させ、それ以外の場合は何もしない回路を作成します。次に、グローバーのアルゴリズムを適用します。実行時間はO(sqrt(N))、最初の値を見つけることです。次に、それも調整して繰り返します。

一方、衝突が見つかるまで古典的にランダムにサンプリングするだけでも時間がかかるO(sqrt(N))ため、おそらくもっと賢いことができます。