Simon-Algorithmus
Ein Quantenalgorithmus, der eine versteckte XOR-Periode einer Funktion exponentiell schneller findet als jedes klassische Verfahren.
Das Problem wirkt konstruiert: Eine Funktion erfüllt f(x) = f(x ⊕ s) für ein geheimes s; finde s. Klassisch braucht man etwa 2n/2 Abfragen, bis eine Kollision auftaucht. Daniel Simon zeigte 1994, dass ein Quantencomputer das mit einer in n linearen Zahl von Abfragen schafft. Es war die erste exponentielle Trennung zwischen Quanten- und klassischer Berechnung für ein klar definiertes Problem, und Peter Shor hat gesagt, dass es Simons Arbeit war, die ihn auf die Faktorisierung ansetzte.
Zwanzig Jahre lang war der Algorithmus meist eine historische Fußnote. Dann stellte sich heraus, dass viele Even-Mansour-Konstruktionen und MAC-Modi genau so eine XOR-Periode enthalten – und er wurde zum Arbeitspferd der Quantenkryptanalyse gegen symmetrische Verfahren.