4 кубита
Bernstein–Vazirani
Находит скрытую битовую строку за один запрос к оракулу.
История
Предложен Этаном Бернштейном и Умешем Вазирани в 1993 году.
Задача
Найти скрытую строку s в f(x) = s·x mod 2.
Математика
H^⊗n · U_f · H^⊗n восстанавливает s.
Сложность
1 запрос vs n классически
vs Классика
Линейное ускорение в числе запросов к оракулу.