Исследователи из Университета Тренто, Италия, разработали новый подход к факторизации простых чисел посредством квантового отжига, используя компактную парадигму модульного кодирования и позволяя факторизовать большие числа с помощью квантовых устройств D-Wave.
Факторизация простых чисел — это процедура разложения числа на простые компоненты. Каждое целое число больше единицы можно однозначно выразить как произведение простых чисел.
В криптографии простая факторизация имеет особое значение из-за ее значимости для безопасности алгоритмов шифрования, таких как широко используемая криптосистема RSA.
Процесс факторизации простых чисел становится сложным из-за природы простых чисел, и он становится еще более сложным по мере того, как факторизуемые числа становятся больше, что приводит к огромному количеству возможностей для рассмотрения.
Непрактичность эффективной факторизации больших чисел обеспечивает целостность зашифрованной связи. Надежность этих криптографических систем зависит от вычислительной сложности простой факторизации, что делает ее важнейшим компонентом защиты конфиденциальной информации в эпоху цифровых технологий.
Если кто-то сможет эффективно факторизовать произведение двух больших простых чисел, он потенциально может нарушить безопасность криптографических систем. Понимание и развитие методов простой факторизации способствуют обеспечению надежности криптографических протоколов и защите конфиденциальной информации в цифровой связи.
В новом исследовании, опубликованном в журнале Scientific Reports , исследователи под руководством профессора Роберто Себастьяни из Университета Тренто, Италия, стремились решить этот процесс с помощью квантовых отжигателей. В состав команды также входили Цзинвэнь Дин и Джузеппе Спаллитта, доктор философии. Студенты Университета Тренто.
«Как ученый-компьютерщик, посвятивший всю свою карьеру разработке классических процедур для решения сложных вычислительных логических и оптимизационных задач , я был очень заинтригован возможностью иметь дело с такой технологией, как квантовый отжиг, основанной на вычислительной парадигме, далекой от всего, с чем я сталкивался раньше», — сказал профессор. Себастьяни рассказал Tech Xplore.
Квантовые отжиги
Квантовые компьютеры уникально подходят для решения задач простой факторизации благодаря их способности выполнять параллельные вычисления и использовать квантовые явления. В частности, квантовые отжиги, подобные устройствам от D-Wave, предназначены для решения задач оптимизации путем одновременного поиска оптимальных решений среди огромного количества возможностей.
В контексте факторизации простых чисел, где поиск простых множителей предполагает быстрое изучение множества комбинаций, присущий квантовым вычислениям параллелизм предлагает потенциальное преимущество.
Квантовые отжиги используют квантовые явления, такие как квантовая суперпозиция и квантовое туннелирование, для одновременного исследования нескольких решений, что делает их хорошо подходящими для решения задач простой факторизации. Такое параллельное исследование возможностей может значительно повысить эффективность поиска простых множителей по сравнению с классическими алгоритмами.
Компактное кодирование
Исследование имеет двоякий характер. В первом аспекте своей работы исследователи достигли прорыва, разработав компактное модульное кодирование схемы двоичного умножителя размером 21×12 бит непосредственно в один 8-кубитный модуль в топологии Pegasus квантовых отжигателей D-Wave.
Подумайте о топологии Pegasus как о сети, соединяющей кубиты и определяющей поток данных.
«Поворотным моментом в этой работе, который стал для нас положительным сюрпризом, стало успешное кодирование подсхемы управляемого полного сумматора (CFA) в одиночный 8-кубитный модуль топологии Pegasus Quantum Annealer», — объяснил он. Проф. Себастьяни.
CFA — это квантовая подсхема, выполняющая 1-битные операции сложения при определенных условиях управления, которые команда закодировала в модуле топологии отжига с помощью теории оптимизации по модулю (OMT), технологии, сочетающей логические рассуждения и оптимизацию.
В отличие от предыдущих подходов, которые игнорировали компоновку системы, команда использовала OptiMathSAT, свой инструмент теории оптимизации по модулю, для создания кодировки, хорошо учитывающей топологию. Это продемонстрировало эффективность их подхода и ознаменовало значительный прогресс в методах кодирования для квантовых отжигателей.
Модульность их подхода к кодированию меняет правила игры. Они продемонстрировали возможность кодирования в отжигателе факторизации числа до 8 587 833 345 в произведение двух простых чисел: 2 097 151 и 4 095. Это знаменует собой крупнейшую проблему факторизации, когда-либо закодированную в квантовом отжиге с использованием их нового метода.
«Мы заметили два ключевых факта. Мы можем разложить схему умножителя размером n×m на матрицу взаимосвязанных подсхем CFA и выровнять ее с решеткой Пегаса из 8-кубитных модулей», — объяснил профессор Себастиани.
Это позволило исследователям создать структуру, которая может легко масштабироваться с ростом числа кубитов в будущих чипах квантового отжига.
Экспериментальная факторизация
На втором этапе своего исследования команда провела обширную экспериментальную оценку квантового отжигателя D-Wave Advantage 4.1. Целью было исследовать фактическое решение закодированных проблем PF и оценить возможности квантового отжига на практике.
«В целом, из-за неисправных кубитов и ограниченных ресурсов времени QUPU, 8 219 999 = 32 749 × 251 было наивысшим простым произведением, которое мы смогли факторизовать. Насколько нам известно, это самое большое число, когда-либо факторизованное с использованием квантового устройства, не полагаясь на на процедурах внешнего поиска или предварительной обработки, выполняемых на классических компьютерах», — пояснил профессор Себастьяни.
Это достижение имеет важное значение для квантовых вычислений и их приложений. Исследователи продемонстрировали прогресс в решении сложных вычислительных задач, доказав, что существенные достижения возможны даже при ограничениях современного оборудования квантового отжига.
Одна из проблем в этой работе заключается в том, что, поскольку каждая задача простой факторизации имеет не более двух решений (например, 35 = 7 × 5 или 35 = 5 × 7), квантовый отжиг должен искать эти глобальные минимумы в экспоненциально обширном решении. космос.
Профессор Себастьяни пояснил: «Это похоже на поиск иголки в стоге сена. К счастью, существует множество методов и приемов отжига, позволяющих справиться с этими проблемами, но для получения удовлетворительных результатов потребовалось много практики».
За пределами факторизации
Профессор Себастьяни подчеркнул потенциал расширения использования этих устройств за пределы простой факторизации, предусмотрев приложения для кодирования и проверки выполнимости различных схем.
«Мы считаем, что квантовые отжиги можно использовать для кодирования и проверки выполнимости многих других представляющих интерес схем. Таким образом, мы обращаемся к пропозициональной выполнимости булевых схем (SAT) — гораздо более общей проблемы, чем факторизация простых чисел, и которая позволяет представлять множество реальных чисел. — мировые проблемы», — поделился профессор Себастьяни.
Забегая вперед, исследователи подчеркнули важность разработки гибридных квантово-классических процедур, в которых классические процедуры могут использовать отжиг для решения небольших, но очень сложных в вычислительном отношении комбинаторных подзадач.
Однако важно отметить, что, несмотря на выдающиеся достижения, представленные в их статье, исследователи осторожно относятся к ограничениям. Они подчеркивают, что они все еще далеки от решения проблем простой факторизации, достаточно серьезных, чтобы поставить под угрозу безопасность существующих криптографических систем.
