A.k.a. BHT-algoritmen, for [Brassard, Hoyer, Tapp - Quantum algorithm for the collision problem](https://arxiv.org/abs/quant-ph/9705002). En variant av [[Grovers algoritme]], anvendt problemet å finne en kollisjon i en black-box funksjon. Løser problemet i forventet kjøretid $O(N^{1/3})$, som er noe raskere enn den klassisk optimale $O(N^{1/2})$ (via [[Bursdagsparadokset]]). Paraphrasing [Andrew Childs](https://youtu.be/M0e5gkf7QSQ?si=ut9xdiKLocZXafxi): > Basically, query $K$ items classically, then use [[Grovers algoritme]] to search through the remaining items for a duplicate, yielding cost $O(K + \sqrt{N/K})$. The optimal value is reached for $K = \Theta(N^{1/3})$, yielding the stated runtime. Denne algoritmen har blitt vist til å være *optimal*, slik at situasjonen er: - Klassisk: $T = \Theta(N^{1/2})$ - Kvantisk: $T = \Theta(N^{1/3})$ ### [[NISQ]]-kompleksitet Bra paper/talk ved [[Eurocrypt'24]]: [EC:HamLiuSin24 - The NISQ Complexity of Collision Finding](https://eprint.iacr.org/2024/360.pdf) Introduserer tilsynelatende nyttige modeller for [[NISQ]]-maskiner, "of independent interest", som det heter seg. Introduserer også "hybrid [[The Compressed-Oracle Technique|compressed oracles]]"? ### Optimalitet i [[Quantum Random Oracle Model]] I [EC:CFHL21 - On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work](https://eprint.iacr.org/2020/1305) benytter forfatterne deres modulariserte reformulering av [[The Compressed-Oracle Technique]] til å gi et (tidligere kjent, men nå lettere å forstå) bevis for optimaliteten av BHT-algoritmen for kvante-kollisjonsøk. ### Generalisering til subset cover problem Se Bouaziz-Ermann, Grilo, Vergnaud: [ITC:BouGrilVer23 – Quantum security of subset cover problems](https://eprint.iacr.org/2022/1474).