От Дойча-Джозы к алгоритму Саймона: в чём секрет квантового ускорения
В популярных текстах говорят: «квантовый компьютер быстрый, потому что проверяет все входы сразу в суперпозиции». Но при измерении мы вытащим лишь один случайный ответ! Настоящее искусство квантового алгоритма — так преобразовать базис с помощью ортогональных матриц, чтобы неправильные ответы погасили друг друга за счёт интерференции, а правильный усилился.
Чтобы сравнивать скорость без привязки к деталям реализации, в теории используют запросную сложность (сколько раз нужно обратиться к «чёрному ящику» — оракулу):
- Задача Дойча — Джозы: дана булева функция переменных, гарантированно либо константная (всегда 0 или всегда 1), либо сбалансированная (ровно половина нулей и половина единиц). Классическому алгоритму в худшем случае нужно запросов (экспоненциально много). Квантовая схема с матрицами Адамара даёт точный ответ за 1 запрос (разделяя классы и по запросной сложности).
- Задача Саймона: дана функция, у которой тогда и только тогда, когда для секретной строки . Классике (даже с допустимой ошибкой — класс ) нужно экспоненциальное число запросов (в худшем случае ). Квантовая цепь Саймона использует свойства матрицы : строки с гасятся до нуля, и измерение выдаёт случайный вектор , ортогональный секрету (). Повторив цикл раз, мы получаем линейную систему и находим за квадратичное время — задача лежит в классе .