Анализ квантового алгоритма нахождения скрытого сдвига и его криптографические последствия

Abstract

Современные квантовые алгоритмы представляют серьезную угрозу для безопасности многих криптографических схем. В данной статье рассматривается квантовый алгоритм нахождения скрытого сдвига - задачи, связанной с восстановлением неизвестного параметра s в функции вида f(х) = g(х+ s). Представленный алгоритм использует квантовое преобразование Фурье (QFT) и решает задачу со сложностью O(log N), тогда как классические методы требуют как минимум O(Jn) запросов. Рассмотрена реализация алгоритма с использованием Qiskit, проведен анализ результатов измерений, а также обсуждаются потенциальные криптографические риски.