Лекция 11. Простейшие квантовые алгоритмы с использованием оракулов

На этой Лекции мы обсудили модель вычислений с чёрным ящиком и простейшие алгоритмы, дающие приемущество при вычислениях с оракулом. Как правило, выделяют два вида квантовых черных ящиков для описания действия булевой функции – $\mathrm{XOR}$-оракулы и фазовые оракулы. Эти два вида оракулов экивалентны, но их применение оказывается полезным в разных ситуациях. Так, используя фазовый оракул, удобно изучать свойства Фурье-спектра булевой функции: при помощи преобразований Уолша-Адамара и фазового оракула можно делать выборку из спектральной меры булевой функции. Благодаря этому, эффективно решаются некоторые задачи теории булевых функций. Так, если функция $f$ является линейной булевой функцией, то, согласно алгоритму Бернштейна-Вазирани, можно узнать её вид за одно обращение к оракулу; согласно алгоритму Дойча-Джозсы ща одно обращение к оракулу можно решить, является ли булева фунция константной или сбалансированной. Решения этих задач при помощи классических оракулов требует большего числа обращений. Если дана функия $f$, для которой выполнено $f(x) = f(y)$ если и только если $y = x\oplus s$, то алгоритм Саймона позволяет найти скрытый сдвиг $s$ за $\mathcal{O}(n)$ обращений к оракулу, в то время как классический алгоритм требует $\mathcal{O}(\sqrt{2^n})$ обращений. Алгоритм Саймона можно значительно обобщить, чтобы решать задачи скрытой подгруппы в любых конечных абелевых группах.