Алгоритм Гровера
Квантовые вычисления в некоторых частных задачах могут быть эффективнее и быстрее чем классические алгоритмы. Одним из первых квантовых алгоритмов, который даёт ассимптотически более быстрое решение, чем классика — это алгоритм Гровера.
Постановка задачи: пусть у нас есть булевая функция f: {0, 1}^n -> {0, 1} и мы хотим найти искомое решение x, для которого верно f(x)=1, а для всех остальных x верно f(x)=0. То есть алгоритм Гровера осуществляет поиск нужной строки в базе данных. Мы не знаем, как f(x) устроена внутри, но можем применять квантовые гейты для решения задачи.
В 1996 году Гровер предложил алгоритм, который использует оракул U_f, «помечающий» искомое состояние и диффузионный оператор U_d, который отражает состояние относительно среднего и приближает его к искомому. Подробнее про алгоритм можно прочитать в оригинальной статье или тут.
Асимптотика алгоритма оказывается равна O(n^0.5), тогда как у классических алгоритмов только O(n). Эта задача является прекрасным примером того, как квантовые алгоритмы могут дать ускорение при решении практических задач.