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

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

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

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

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

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

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

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

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

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

Нашли опечатку? Выделите фрагмент и нажмите Ctrl+Enter.
Безумие в наследство — 2

Как развитие технологий позволило нащупать «топологическое решение» загадки шизофрении

Шизофрения — одна из самых загадочных и сложных болезней человека. Уже более ста лет ученые пытаются понять причины ее возникновения и найти ключ к терапии. Пока эти усилия не слишком успешны: до сих пор нет ни препаратов, которые могли ли бы ее по-настоящему лечить, ни даже твердого понимания того, какие молекулярные и клеточные механизмы ведут к ее развитию. О том, как ученые бьются с «загадкой шизофрении» мы уже неоднократно писали: сначала с точки зрения истории психиатрии, затем с позиции классической генетики (читателю, который действительно хочет вникнуть в суть проблемы, будет очень полезно сначала прочитать хотя бы последний текст). На этот раз наш рассказ будет посвящен новым молекулярно-биологическим методам исследования, которые появились в распоряжении ученых буквально в последние несколько лет. Несмотря на сырость методик и предварительность результатов, уже сейчас с их помощью получены важнейшие данные, впервые раскрывающие механизм шизофрении на молекулярном уровне.