Kjent kvantealgoritme. Kvadratrot-speedup i forhold til beste klassiske. Kan sies å fungere ved å kjøre alle mulige løsninger i parallell … men opererer ikke umiddelbart (ellers ville [[BQP]] = [[P]], og kvantedatamaskiner ville *virkelig* vært revolusjonerende).
Mer spesifikt, gitt black-box tilgang til en funksjon $f: \{1, \dots, N\} \rightarrow \{0,1\}$, finn $i \in \{1, \dots, N\}$ slik at $f(i) = 1$.
Klassisk krever dette $O(N)$ queries (forventningsverdien er vel $N/2$ tenker jeg), mens Grovers algoritme krever $O(\sqrt{N})$.
Det har blitt bevist at algoritmen er optimal i den forstand at det eksisterer nedre skranke, $\Omega(\sqrt{N})$ (og tilsvarende klassisk $\Omega(N)$, og vi kan dermed konkludere med at kjøretiden for å løse dette problemet er:
- Klassisk: $\Theta(N)$
- Kvantisk: $\Theta(\sqrt{N})$
### Operasjon av algoritmen
Fra [Andrew Childs kvantealgoritmetutorial](https://youtu.be/M0e5gkf7QSQ?si=ut9xdiKLocZXafxi):
Hvis det er $M$ "markerte" verdier slik at $f(i)=1$:
- "phase kickback" lar oss implementere følgende orakel: $|i\rangle \rightarrow (-1)^{f(i)}|i\rangle$
- gir en refleksjon om de $M$ markerte verdiene
- alterner dette med en refleksjon om uniform superposisjon $\frac{1}{\sqrt{N}} \sum_{i=1}^N |i\rangle$
- "rotation by an angle $\Theta(1/\sqrt{N})$ in a 2D subspace"
- dette er sikkert en setning som er intuitiv og klar for Andrew Childs men jeg er ikke Andrew Childs
- min egen intuisjon er at vi kommer ca. $1/\sqrt{N}$ "nærmere" løsningen (i den forstand at det blir omtrent så mye større sjangse for at det er den verdien tilstanden kollapser til ved måling)
- "significant overlap with marked subspace in time $O(\sqrt{N/M})
quot;
- altså så mange ganger dette må gjentas for at sannsynligheten for å få *én* markert verdi ut i andre enden er akseptabelt høy
### Påvirkning på sikkerhet
##### Sikkerhetsanalyse av AES
De fleste antar at symmetrisk kryptografi som [[AES]] forblir sikkert mot [[Kvantedatamaskiner]], og at Grover-baserte angrep simpelthen betyr at vi må doble nøkkellengden. I virkeligheten er til og med dette mest sannsynlig å ta hardt i, da det finnes langt bedre klassiske angrep mot [[AES]] enn simpelthen brute-force nøkkelsøk, og disse lar seg *ikke* enkelt aksellerere av Grover; se [FSE:BonNaySch20 – Quantum Security Analysis of AES](https://eprint.iacr.org/2019/272).
##### Et feilet forbedringsforsøk
Mer nylig introduserte [EPRINT:ZheGaoWan – Nested Quantum Search Model on Symmetric Ciphers and Its Applications](https://eprint.iacr.org/2023/327) en variant av nøkkelsøksalgoritmen, som de påstår gir en forbedring; sammendraget konkluderer:
> Our search model can be applied to symmetric ciphers. And it has been shown that doubling the key length is not an effective way anymore to resist the quantum search attacks. Even if the key length is increased by $r−1$ times *(sic)*, symmetric ciphers still struggle to obtain desired security for a re-selected value of $r$.
... Hvor $r$ er "the iteration number".
Jeg skulle til å skrive at jeg stiller meg skeptisk, og sannelig: **Artikkelen ble tilbaketrukket fire måneder etter opplasting til eprint.**