Vector Spaces

От Дойча-Джозы к алгоритму Саймона: в чём секрет квантового ускорения

Алгоритмы, статья 18 из 20

В популярных текстах говорят: «квантовый компьютер быстрый, потому что проверяет все входы сразу в суперпозиции». Но при измерении мы вытащим лишь один случайный ответ! Настоящее искусство квантового алгоритма — так преобразовать базис с помощью ортогональных матриц, чтобы неправильные ответы погасили друг друга за счёт интерференции, а правильный усилился.

Усиление½ + ½ = 1Гашение½ − ½ = 0
Интерференция амплитуд: одинаковые знаки усиливают результат, противоположные — гасят. На этом держатся квантовые алгоритмы.

Чтобы сравнивать скорость без привязки к деталям реализации, в теории используют запросную сложность (сколько раз нужно обратиться к «чёрному ящику» — оракулу):

  • Задача Дойча — Джозы: дана булева функция nn переменных, гарантированно либо константная (всегда 0 или всегда 1), либо сбалансированная (ровно половина нулей и половина единиц). Классическому алгоритму в худшем случае нужно 2n−1+12^{n-1} + 1 запросов (экспоненциально много). Квантовая схема с матрицами Адамара H⊗nH^{\otimes n} даёт точный ответ за 1 запрос (разделяя классы PP и QPQP по запросной сложности).
  • Задача Саймона: дана функция, у которой f(x)=f(y)f(x) = f(y) тогда и только тогда, когда y=x⊕sy = x \oplus s для секретной строки ss. Классике (даже с допустимой ошибкой — класс BPPBPP) нужно экспоненциальное число запросов ∼2n/2\sim 2^{n/2} (в худшем случае 2n−1+12^{n-1}+1). Квантовая цепь Саймона использует свойства матрицы H⊗nH^{\otimes n}: строки с a⋅s=1a \cdot s = 1 гасятся до нуля, и измерение выдаёт случайный вектор aa, ортогональный секрету (a⋅s=0a \cdot s = 0). Повторив цикл n+Nn + N раз, мы получаем линейную систему и находим ss за квадратичное время — задача лежит в классе BQPBQP.
классический алгоритм, худший случайквантовый алгоритм31n = 251n = 391n = 4171n = 5331n = 6651n = 7
Задача Дойча — Джозы: в худшем случае классический алгоритм делает 2n−1+12^{n-1}+1 запросов к оракулу, квантовый — один.