Simons algoritm
En kvantalgoritm som hittar en dold XOR-period i en funktion exponentiellt snabbare än någon klassisk metod.
Problemet ser konstruerat ut: en funktion uppfyller f(x) = f(x ⊕ s) för något hemligt s, hitta s. Klassiskt krävs ungefär 2n/2 anrop innan en kollision dyker upp. Daniel Simon visade 1994 att en kvantdator klarar det med ett antal anrop som växer linjärt med n. Det var det första exponentiella gapet mellan kvant och klassiskt för ett väldefinierat problem, och Peter Shor har berättat att det var just Simons artikel som fick honom att ge sig på faktorisering.
I tjugo år var algoritmen mest en historisk fotnot. Sedan visade det sig att många Even–Mansour-konstruktioner och MAC-lägen innehåller exakt en sådan XOR-period, vilket gjorde den till huvudverktyget i kvantkryptoanalys av symmetriska system.