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

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

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

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

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

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

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

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

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

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

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

N+1

Похожие новости:
Американские физики реализовали квантовый алгоритм Шора
Американские физики из университета Санта Барбары сделали очередной шаг на пути создания полноценного квантового компьютера - они смогли полноценно реализовать квантовый алгоритм Шора на системе с тремя кубитами. Статья ученых вышла в Nature Physics, а ее препринт доступен на сайте arXiv.org.В ..
2012-08-20 2338 0 Научные открытия
1
Создана первая масштабируемая реализация квантового алгоритма
Физики из Массачусетского технологического института в США и Инсбрукского университета в Австрии создали квантовый компьютер, который впервые допускает масштабирование при реализации квантового алгоритма Питера Шора. Исследование ученых опубликовано в журнале Science.Ученые спроектировали и построили квантовый компьютер из пяти атомов ..
2016-03-04 2035 0 Научные открытия
2
Физики вплотную приблизились к стандартному квантовому пределу
Ученым из Калифорнии в своих измерениях удалось наиболее близко приблизиться к значению стандартного квантового предела. Свое исследование авторы опубликовали в журнале Science, кратко с ним можно ознакомиться на сайте Национальной лаборатории имени Лоуренса в Беркли. Физикам впервые удалось добиться ..
2014-06-28 2249 0 Научные открытия
0
Физики управляли квантовой симметрией двухслойного графена
Ученые из США, Канады и Японии наблюдали дробный квантовый эффект Холла в двухслойном графене и показали возможность управления свойствами такого материала действием электрического поля. Свое исследование авторы опубликовали в статье в журнале Science. Физикам удалось при помощи электрического ..
2014-07-04 2127 0 Научные открытия
0
Физики построили квантовый компьютер в алмазе
Новое устройство содержит всего два кубита, но зато демонстрирует хорошую устойчивость. При этом кристалл работает при комнатной температуре. Последняя деталь будет очень важна, если исследователи когда-нибудь попытаются сделать квантовые компьютеры по-настоящему массовыми.  Физики из Нидерландов и США создали ..
2015-10-11 2360 0 Научные открытия
1
В алмазе увидели квантовый эффект Зенона
Древнегреческий мыслитель и математик Зенон Элейский известен своими логическими парадоксами. Один из них — Стрела Зенона — звучит следующим образом: "Летящая стрела неподвижна, так как в каждый момент времени она занимает равное себе положение, то есть покоится; поскольку ..
2013-08-22 3263 0 Научные открытия
0
НАСА исследует на МКС рекордно холодный квантовый газ
Специалисты НАСА в условиях микрогравитации изучат ультрахолодный квантовый газ. Специалисты собираются исследовать материю при температурах, никогда ранее не наблюдаемых человеком, сообщается на сайте НАСА. Для этого на Международную космическую станцию (МКС) агентство собирается доставить соответствующее оборудование: ..
2014-09-30 2089 0 Научные открытия
0
Ученые провели самые масштабные квантовые вычисления
Американские и канадские ученые провели самое масштабное вычисление при помощи квантового компьютера на настоящий момент. Им удалось посчитать так называемые двухцветные числа Рамсея. Препринт статьи появился на сайте arXiv.org. Теория Рамсея, названная в честь английского математика Франка Рамсея, ..
2012-01-14 2931 0 Научные открытия
1
Расчет дифракционных решеток ускорили «искривлением пространства»
Физики из МФТИ и французского Университета Жана Монне предложили новый метод моделирования рассеяния света на дифракционных решетках. Алгоритм требует меньше ресурсов, чем традиционные подходы и оптимизирован для расчетов на процессорах обыкновенных компьютерных видеокарт. Это позволяет получить значительный прирост в скорости вычислений. Исследование ..
2017-01-25 8073 0 Научные открытия
0
Математики превратили геном в гомоморфную криптосистему
Криптологи компании Microsoft разработали алгоритм шифрования последовательностей ДНК, который позволяет анализировать их традиционными биоинформатическими методами и при этом не дает скомпроментировать обладателя генома. Технология была представлена на конференции Американского научного общества AAAS, кратко о ней пишет Science. Технология ..
2014-02-18 2089 0 Научные открытия
0
Графен поможет заново определить единицу силы тока
Британские физики разработали первый одноэлектронный насос на основе квантовой точки, выполненной из графена. Установка, собранная группой ученых из Национальной физической лаборатории (NPL) и Кембриджского университета, описана в статье в Nature Nanotechnology. Обзор публикации приводит Phys.org.Одноэлектронный насос ..
2013-05-16 1914 0 Научные открытия
0
Математики придумали алгоритм поиска источников загрязнения
Французские математики предложили алгоритм, который позволяет выявлять местоположения источников загрязнения по данным о загрязнении конкретных областей. Статья ученых появилась в журнале Inverse Problems. В рамках работы ученые рассмотрели так называемую обратную задачу - достаточно широкий класс ..
2012-06-27 2050 0 Научные открытия
2
Физики продемонстрировали работу квантового переключателя
Физики Гарвардского университета и Массачусетского технологического института под руководством Михаила Лукина придумали квантовые переключатели, управлять работой которых можно единичными фотонами. Свое исследование авторы опубликовали в журнале Nature, кратко с ним можно ознакомиться на сайте Гарвардского университета. В ..
2014-04-25 2421 0 Научные открытия
0
Наконец-то осуществлена полная квантовая телепортация!
Новый метод позволяет перейти от вероятностной передачи квантовых битов на расстоянии к детерминированной — без помех и нужды в последующем измерении. Группа Акиры Фурусавы (Akira Furusawa) из Токийского университета (Япония) смогла реализовать полную квантовую телепортацию фотонных кубитов при помощи ..
2013-09-11 2896 0 Научные открытия
0
Химик из МГУ помог пролить свет на теорию сверхпроводимости
Международной группе исследователей впервые удалось продемонстрировать, что распределение кислородных дефектов у сверхпроводящих купратов не является случайным, а показывает упорядоченное поведение, которое взаимодействует с волной зарядовой плотности. Статья на данную тему опубликована в журнале Nature, а коротко о ней сообщается в пресс-релизе ..
2015-09-19 3079 0 Научные открытия
-1