Simon algoritması
Bir fonksiyondaki gizli XOR periyodunu, her klasik yöntemden üstel olarak daha hızlı bulan kuantum algoritması.
Problem yapay görünür: bir f fonksiyonu, bir gizli s için f(x) = f(x ⊕ s) eşitliğini sağlıyor; s’yi bul. Klasik olarak bir çakışma çıkana kadar yaklaşık 2n/2 sorgu gerekir. Daniel Simon 1994’te bir kuantum bilgisayarın bunu n ile doğrusal sayıda sorguyla başardığını gösterdi. İyi tanımlı bir problemde kuantum ile klasik arasındaki ilk üstel ayrımdı ve Peter Shor’un çarpanlara ayırmaya saldırmaya girişmesini Simon’ın makalesinin sağladığını söylediği aktarılır.
Yirmi yıl boyunca algoritma çoğunlukla tarihsel bir dipnottu. Sonra pek çok Even–Mansour yapısının ve MAC kipinin tam da böyle bir XOR periyodu içerdiği anlaşıldı; böylece simetrik şemalara karşı kuantum kriptanalizinin iş atı oldu.