Vector Spaces

Алгоритмы Шора и Гровера: взлом RSA и квантовый поиск

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

Кронекеровское произведение матриц Адамара H⊗nH^{\otimes n} способно искать скрытую периодичность по модулю 2 (как у Саймона). В 1994 году Питер Шор заменил H⊗nH^{\otimes n} на квантовое преобразование Фурье (обобщение матрицы Адамара с использованием комплексных корней из единицы) и научился находить обычный период функции ax mod Na^x \bmod N.

10214283142546871829410811xпериод 4период 4период 4
Функция f(x)=2x mod 15f(x)=2^x \bmod 15 повторяется с периодом 44. Именно период и находит квантовая часть алгоритма Шора.

Почему это вызвало шок? Безопасность современного интернета и банковского шифрования RSA держится на том, что перемножить два 300-значных простых числа pp и qq легко, а разложить N=pqN = pq обратно — непосильно сложно для классических алгоритмов. Алгоритм Шора решает задачу факторизации за полиномиальное время (класс BQPBQP). Пока квантовые процессоры смогли разложить так лишь небольшие числа вроде 15 и 21, но угроза реальна — поэтому уже сейчас активно развиваются постквантовая криптография (шифры, стойкие к квантовым атакам) и квантовые сети вроде спутника Micius.

Второй титан квантовых алгоритмов — алгоритм Гровера (1996) для поиска в неупорядоченной базе из mm элементов. Классике нужно в среднем m/2m/2 и в худшем m−1m-1 проверок. Гровер за два шага (переворот знака амплитуды искомого элемента оракулом + инверсия всех амплитуд относительно среднего) усиливает вероятность верного ответа. Для m=4m = 4 хватает всего 1 запроса вместо 2,252{,}25 в среднем. В общем случае время поиска снижается с mm до m\sqrt{m} — квадратичное ускорение, и доказано, что быстрее для неструктурированного поиска быть не может.

½½½½1. Равномернаясуперпозиция½½½−½¼2. Оракул меняетзнак у ответа00013. Отражениеотносительно среднего
Алгоритм Гровера для m=4m=4 элементов: один запрос к оракулу и одно отражение относительно среднего дают ответ с вероятностью 11.