Алгоритмы Шора и Гровера: взлом RSA и квантовый поиск
Кронекеровское произведение матриц Адамара способно искать скрытую периодичность по модулю 2 (как у Саймона). В 1994 году Питер Шор заменил на квантовое преобразование Фурье (обобщение матрицы Адамара с использованием комплексных корней из единицы) и научился находить обычный период функции .
Почему это вызвало шок? Безопасность современного интернета и банковского шифрования RSA держится на том, что перемножить два 300-значных простых числа и легко, а разложить обратно — непосильно сложно для классических алгоритмов. Алгоритм Шора решает задачу факторизации за полиномиальное время (класс ). Пока квантовые процессоры смогли разложить так лишь небольшие числа вроде 15 и 21, но угроза реальна — поэтому уже сейчас активно развиваются постквантовая криптография (шифры, стойкие к квантовым атакам) и квантовые сети вроде спутника Micius.
Второй титан квантовых алгоритмов — алгоритм Гровера (1996) для поиска в неупорядоченной базе из элементов. Классике нужно в среднем и в худшем проверок. Гровер за два шага (переворот знака амплитуды искомого элемента оракулом + инверсия всех амплитуд относительно среднего) усиливает вероятность верного ответа. Для хватает всего 1 запроса вместо в среднем. В общем случае время поиска снижается с до — квадратичное ускорение, и доказано, что быстрее для неструктурированного поиска быть не может.