Квантовый алгоритм Шора впервые отмасштабировали

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

Алгоритм Питера Шора — это квантовый алгоритм разложения чисел на простые множители, то есть факторизации. Суть алгоритма заключается в сведении задачи факторизации к поиску периода функции. Если известен ее период, то факторизация осуществляется при помощи алгоритма Евклида за полиномиальное время на классическом компьютере. Таким образом, алгоритм Шора включает в себя две части: классическую и квантовую. Квантовая часть занимается поиском периода функции, а классическая часть сначала подготавливает эту функцию, а потом проверяет период, найденный квантовой частью. Если период найден правильно, то задача будет решена.

Ученые спроектировали квантовый компьютер, который реализует масштабируемую версию алгоритма Шора, предложенную российским физиком Алексеем Китаевым. Эта версия позволяет сократить количество используемых кубитов для выполнения операции. Один из авторов работы, Айзек Чуанг (Isaac Chuang), заявляет, что, в то время как для факторизации числа 15 — наименьшего нечетного составного числа, не представимое в виде степени простого (ограничение алгоритма Шора) — традиционно требуется 12 кубитов, их квантовому компьютеру требуется всего пять кубитов.

Для реализации алгоритма используется пять ионов ⁴⁰Ca+, находящихся в состоянии суперпозиции и заключенных в квадрупольную ионную ловушку или ловушку Пола. Компьютер использует лазерные импульсы в качестве логических переключателей. Четыре атома используются для совершения операции, а один используется для извлечения и интерпретации данных.

По результатам экспериментов вероятность ошибки при вычислении периода составила менее одного процента. Однако сами исследователи в своей работе указали, что, чтобы в действительности получить такой уровень вероятности, эксперимент следует повторить восемь раз. Вероятность получения достоверного периода с первого раза ученые оценили приблизительно в 50%.

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

Если масштабы подобных систем в будущем действительно удастся увеличить, то это поставит под угрозу существующие системы защиты на базе алгоритма шифрования RSA. Этот алгоритм представляет собой криптосистему с открытым ключом, в основе которого как раз и лежит факторизация произведения двух простых больших чисел. Он используется при передаче информации через интернет, считывании информации с банковских карточек и других конфиденциальных операциях.

Стоит отметить, что несколько лет назад американские физики из университета Санта Барбары смогли реализовать квантовый алгоритм Шора на системе с тремя кубитами. Алгоритм давал правильный ответ примерно в 48 процентах случаев, однако не допускал масштабирования.

Кристина Уласович