衝突問題

r対 1 衝突問題は、計算量理論、量子コンピューティング、計算数学における重要な理論的問題です。衝突問題は、ほとんどの場合、2 対 1 バージョンを指します。^[1]と関数が与えられた場合、 f は1 対 1または 2 対 1のいずれかであることが保証されます。任意の について、 の値についてのみクエリを実行できます。問題は、 f が 1 対 1 であるか 2 対 1 であるかを確実に判断するために、このようなクエリを何回実行する必要があるかを尋ねます。 ${\displaystyle n}$${\displaystyle f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}}$${\displaystyle f(i)}$${\displaystyle i\in \{1,\ldots ,n\}}$

2 対 1 バージョンを決定論的に解決するにはクエリが必要であり、一般に r 対 1 関数と 1 対 1 関数を区別するにはクエリが必要です。 ${\textstyle {\frac {n}{2}}+1}$${\textstyle {\frac {n}{r}}+1}$

これは、鳩の巣原理の直接的な応用です。関数が r 対 1 の場合、クエリの後に衝突が見つかることが保証されます。関数が 1 対 1 の場合、衝突は存在しません。したがって、クエリで十分です。運が悪ければ、最初のクエリで異なる回答が返される可能性があるため、クエリも必要です。 ${\textstyle {\frac {n}{r}}+1}$${\textstyle {\frac {n}{r}}+1}$${\displaystyle n/r}$${\textstyle {\frac {n}{r}}+1}$

ランダム性を許容すれば、問題はより簡単になります。誕生日のパラドックスにより、(異なる)クエリをランダムに選択すると、クエリ後に任意の固定された 2 対 1 関数で衝突が発生する可能性が高くなります。 ${\displaystyle \Theta ({\sqrt {n}})}$

Grover のアルゴリズムを使用するBHT アルゴリズムは、fへのクエリのみを実行することでこの問題を最適に解決します。 ${\displaystyle O(n^{1/3})}$