2 кубита
Алгоритм Гровера
Квантовый поиск в неструктурированной базе данных с квадратичным ускорением.
История
Открыт Ловом Гровером в 1996 году.
Задача
Найти помеченный элемент среди N = 2^n элементов.
Математика
Амплификация амплитуды через оракул и диффузию: O(√N) запросов.
Сложность
O(√N) vs O(N) классически
vs Классика
Квадратичное ускорение — оптимально для неструктурированного поиска.