En av få [[Kvantealgoritmer]] med eksponentiell speedup sammenlignet med den beste klassiske. Inspirasjonskilden til [[Shors algoritme]]. Kan brukes til å knekke Evan-Mansour-chifferet dersom det blir gitt full kvantetilgang ([[Q2-world]]). Relatert: [[Hva slags struktur tillater overlegne kvantealgoritmer?]] #### Oppgaven La $f: \{0,1\}^n \rightarrow R$ (for "some range" $R$) være en strengt periodisk funksjon, det vil si det eksisterer en $s \in \{0,1\}^n$ slik at $f(x) = f(y)$ hvis og bare hvis $x = y$ eller $x = y \oplus s$. Simons problem er da: Finn $s$. Denne algoritmen kjører eksponentielt raskere enn noen klassisk algoritme kan gjøre. (Merk at dette ikke impliserer at [[P]] $\neq$ [[NP]], tross at det er lett å sjekke om $s$ er korrekt når den først har blitt funnet og at problemet derfor er i [[NP]], fordi dette er et *orakelproblem*, som ofte tillater teoremer som ikke lar seg vise (enda) i den "virkelige verden". Optimal klassisk strategi er basically å bare gjette to verdier helt til man finner en kollisjon, som per [[Bursdagsparadokset]] gir oss en forventet kjøretid på $\Theta(\sqrt{2^n})$. #### Kvantealgoritmen Kvantisk derimot kan vi få en kjøretid på $O(n)$ på følgende vis. Kjør den følgende subrutinen $n$ ganger: 1. Forbered uniform superposisjon: $\frac{1}{\sqrt{2^{n}}} \sum_{x\in\{0,1\}^n} |x,0\rangle$ 2. Beregn $f(x)$ i superposisjon: $\frac{1}{\sqrt{2^{n}}} \sum_{x\in\{0,1\}^n} |x,f(x)\rangle$ 3. Gjennomfør en Hadamard-transformasjon av de første $n$ kvantebitsene (altså input-delen av tilstanden). 4. Gjennomfør en måling av de første $n$ kvantebitsene. Dette vil gi en tilfeldig verdi $x$ *slik at* $x \cdot s = 0$. Med andre ord: $x \perp s$. Dette betyr at straks vi har $n$ slike, så kan vi bruke lineær algebra til å regne ut $s$.