Покроковий алгоритм квантового пошуку Гровера на 16-елементному регістрі. Спостерігайте підсилення амплітуди цільового елемента за O(√N) ітерацій проти класичних O(N).
Алгоритм використовує дві операції: оракул, що інвертує знак цільової амплітуди, та оператор дифузії, що відображає амплітуди відносно середнього. Після ~√N ітерацій ймовірність цілі наближається до 1.
Оберіть цільовий елемент у 16-елементному регістрі. Проходьте ітерації та спостерігайте гістограму амплітуд. Порівняйте квантовий O(√N) = 3 ітерації з класичним O(N) = 16.
Алгоритм Гровера забезпечує доведено оптимальне квадратичне прискорення для невпорядкованого пошуку. Для бази даних із 1 мільйона елементів він знаходить відповідь за ~1000 запитів замість 500000.