4 кубита
Алгоритм Саймона
Находит скрытый период функции — предшественник алгоритма Шора.
История
Предложен Дэниелом Саймоном в 1994 году.
Задача
Найти период a функции f с f(x) = f(x⊕a).
Математика
Суперпозиция + оракул + H^⊗n → случайные y ⊥ a.
Сложность
O(n) запросов vs O(2^(n/2)) классически
vs Классика
Экспоненциальное ускорение.