Квантовые вычисления — одно из приоритетных научно-технических направлений для достижения технологического суверенитета Российской Федерации. В основе квантовых вычислений лежат междисциплинарные исследования информатики, физики и математики на принципах квантовой механики для ускорения решения вычислительно сложных для классических компьютеров фон Неймана задач. Здесь особый интерес вызывает квантовый алгоритм Шора, который способен факторизовать целые числа за полиномиальное время, что ставит под угрозу стойкость традиционных криптографических систем RSA, DSA, EdDSA, ГОСТ Р 34.10-2012 и др., не обладающих свойством квантовой устойчивости. Однако на практике реализация алгоритма Шора сталкивается с рядом технических проблем, ключевой из которых является эффективное построение квантового преобразования Фурье (QFT) — важнейшей составляющей упомянутого алгоритма. В настоящей статье рассмотрен новый гибридный подход построения аппроксимированного квантового преобразованию Фурье (АQFT) с ограниченным числом вентилей, направленный на оптимизацию алгоритма Шора. Предлагается способ последовательного применения различных методов сокращения квантовых ресурсов и повышения эффективности схемы квантового преобразования Фурье, которые критичны для улучшения производительности алгоритма Шора с требуемой точностью при ограниченных ресурсах.
< ... >
Quantum computing is based on interdisciplinary research from computer science, physics and mathematics using the principles of quantum mechanics to speed up the solution of computationally complex problems compared to von Neumann computers. Here, of particular interest is Shor’s quantum algorithm, which is capable of factoring integers in polynomial time, which threatens the strength of traditional cryptographic systems. However in practice, its implementation faces a number of technical problems, the key of which is the effective construction of the quantum Fourier transform (QFT). This article discusses a new hybrid approach to constructing an approximate quantum Fourier transform (AQFT) with a limited number of gates, aimed at optimizing the Shor algorithm. A method is proposed to sequentially apply various methods for reducing quantum resources and increasing the efficiency of the quantum Fourier transform circuit, which are critical for improving the performance of the Shor algorithm with the required accuracy under limited resources.
Keywords:
quantum threat, quantum Fourier transform, quantum stability, quantum and post-quantum cryptography, strength of cryptoprimitives, quantum-resistant cryptosystems
Полную версию статьи смотрите на страницах журнала «Защита информации. Инсайд»
