Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
本論文は、空間感受的な圧縮オラクル技術を開発することにより、ラベルの対称性下における衝突発見および要素一意性判定に関するタイトな時間・空間の下界を確立し、そのようなアルゴリズムがいずれも 回のクエリと のリソースを必要とすることを証明し、それによって、このクラス内におけるBHTやAmbainisの量子ウォークといった既存の量子アルゴリズムの最適性を確認するものである。