BHTアルゴリズム

量子コンピューティングにおいて、ブラッサード・ホイヤー・タップアルゴリズムまたはBHTアルゴリズムは衝突問題を解決する量子アルゴリズムです。この問題では、nとr対1の関数が与えられ、 fが同じ出力にマッピングされる2つの入力を見つける必要があります。BHTアルゴリズムは、ブラックボックスモデルの下限と一致するfに対してのみクエリを実行します。^{[1] [2]}${\displaystyle f:\,\{1,\ldots ,n\}\rightarrow \{1,\ldots ,n\}}$${\displaystyle O(n^{1/3})}$${\displaystyle \オメガ (n^{1/3})}$

このアルゴリズムは、1997年にジル・ブラッサード、ピーター・ホイヤー、アラン・タップによって発見されました。^[3] このアルゴリズムは、前年に発見された グローバーのアルゴリズムを使用しています。

直感的に言えば、このアルゴリズムは、（古典的な）ランダム性を使用した誕生日のパラドックスによる平方根の高速化と、グローバーの（量子的な）アルゴリズムによる平方根の高速化を組み合わせたものです。

まず、fへのn ^{1/3 個の}入力がランダムに選択され、それらすべてに対してfが照会されます。これらの入力に衝突がある場合は、衝突する入力のペアを返します。それ以外の場合、これらすべての入力はfによって異なる値にマップされます。次に、グローバーのアルゴリズムを使用して、衝突するfへの新しい入力を見つけます。 fにはn 個の入力があり、そのうちのn ^{1/3がすでに照会された値と衝突する可能性があるため、グローバーのアルゴリズムは}fへの追加の照会で衝突を見つけることができます。^[3]${\displaystyle O\left({\sqrt {\frac {n}{n^{1/3}}}}\right)=O(n^{1/3})}$

• 要素の明確性の問題
• グローバーのアルゴリズム