3 кубита
Алгоритм Гровера (3 кубита)
Поиск помеченного состояния |111⟩ среди 8 базисных состояний.
История
Открыт Ловом Гровером в 1996 году.
Задача
Найти |111⟩ среди N = 8 элементов.
Математика
Оракул на CCX + диффузионный оператор; ≈ ⌊π/4 √N⌋ итераций.
Сложность
O(√N) vs O(N) классически
vs Классика
Квадратичное ускорение на 3 кубитах.