Большинство современных алгоритмов шифрования полагается на вычислительную сложность разложения на множители больших чисел, но недавно ученые объявили о создании квантового компьютера, последующие поколения которого способны отправить подобные схемы шифрования на свалку истории.

В традиционных компьютерах значение бита может быть либо 0, либо 1, а квантовые компьютеры основаны на элементах атомных размеров, называемых «кубитами», которые способны за счет пребывания в состоянии квантовой суперпозиции одновременно хранить оба значения. Для разложения на множители числа 15 обычно требуется порядка 12 кубитов, но исследователи из Массачусетского технологического института и Инсбрукского университета нашли способ сократить количество требуемых кубитов всего до пяти, каждый из которых представлен одиночным атомом.

Стабильность системы обеспечивается за счет лазерных импульсов, удерживающих атомы в ионной ловушке. Как утверждается, систему можно масштабировать просто путем добавления атомов и лазеров — таким образом можно построить более крупный и быстрый квантовый компьютер, способный разлагать на множители гораздо большие числа. А это, в свою очередь, ставит под угрозу алгоритмы вроде RSA, которые основаны на разложении больших чисел на множители, и которые сегодня используются для защиты банковских карт, государственных тайн и не только.

Создание квантового компьютера стало ответом на задачу, поставленную еще в 1994 году, когда профессор МТИ Питер Шор разработал квантовый алгоритм, вычисляющий простые множители большого числа гораздо эффективнее, чем это возможно на классическом компьютере.

Самое маленькое число, на котором возможна проверка действенности алгоритма Шора, — 15. Не зная заранее ответа, система из МТИ выдала результат — тройка и пятерка — со степенью уверенности в результате 99%.

«Мы показали, что существует возможность построить квантовый компьютер для выполнения алгоритма Шора таким образом, что для создания более крупной системы будет достаточно просто добавить конструктивных элементов, — подчеркивает Айзек Чуанг, профессор МТИ. — Вероятно, на это понадобится огромная сумма денег, так что вряд ли в скором времени можно будет построить квантовый компьютер, чтобы поставить себе на стол. Однако сегодня это уже в гораздо большей степени инженерная задача, чем проблема теоретической физики».

Отчет о работе ученых опубликован в недавнем выпуске журнала Science.

«Мы уверены, что последующие поколения системы станут легко масштабируемыми, когда наш аппарат сможет захватывать в ловушки больше атомов и получит больше лазерных излучателей для управления импульсами, — продолжил Чуанг. — С точки зрения физики мы не видим препятствий к тому, чтобы это стало возможным».

Работоспособный квантовый компьютер, достаточно большой, чтобы взломать алгоритм RSA, появится, возможно, еще не скоро, но в американском Агентстве национальной безопасности США эту вероятность воспринимают всерьез: в январе на сайте ведомства появился список вопросов и ответов о потенциале квантовой технологии.

«Правительствам, пожалуй, не стоит в доступном месте хранить свои секреты под защитой систем шифрования, надежность которых зависит от сложности разложения чисел на множители, — добавляет Чуанг. — Иначе когда появятся квантовые компьютеры, все государственные тайны быстро станут известны противнику».

Поделитесь материалом с коллегами и друзьями