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

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

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

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

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

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

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

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

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

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

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

N+1

Похожие новости:
Американские физики реализовали квантовый алгоритм Шора
Американские физики из университета Санта Барбары сделали очередной шаг на пути создания полноценного квантового компьютера - они смогли полноценно реализовать квантовый алгоритм Шора на системе с тремя кубитами. Статья ученых вышла в Nature Physics, а ее препринт доступен на сайте arXiv.org.В ..
2012-08-20 1773 0 Научные открытия
0
Создана первая масштабируемая реализация квантового алгоритма
Физики из Массачусетского технологического института в США и Инсбрукского университета в Австрии создали квантовый компьютер, который впервые допускает масштабирование при реализации квантового алгоритма Питера Шора. Исследование ученых опубликовано в журнале Science.Ученые спроектировали и построили квантовый компьютер из пяти атомов ..
2016-03-04 1506 0 Научные открытия
3
Математики придумали алгоритм поиска источников загрязнения
Французские математики предложили алгоритм, который позволяет выявлять местоположения источников загрязнения по данным о загрязнении конкретных областей. Статья ученых появилась в журнале Inverse Problems. В рамках работы ученые рассмотрели так называемую обратную задачу - достаточно широкий класс ..
2012-06-27 1525 0 Научные открытия
2
Бабай приблизился к решению «проблемы тысячелетия»
Математик Ласло Бабай из Чикагского университета в США разработал теоретический алгоритм, позволяющий существенно ускорить сравнение графов друг с другом. Исследование ученого связано с проблемой равенства классов P и NP, являющейся одной из «проблем тысячелетия». Об этом сообщает Nature News.Исследование ученого ..
2015-11-20 3452 0 Научные открытия
0
Расчет дифракционных решеток ускорили «искривлением пространства»
Физики из МФТИ и французского Университета Жана Монне предложили новый метод моделирования рассеяния света на дифракционных решетках. Алгоритм требует меньше ресурсов, чем традиционные подходы и оптимизирован для расчетов на процессорах обыкновенных компьютерных видеокарт. Это позволяет получить значительный прирост в скорости вычислений. Исследование ..
2017-01-25 7577 0 Научные открытия
0
Математики превратили геном в гомоморфную криптосистему
Криптологи компании Microsoft разработали алгоритм шифрования последовательностей ДНК, который позволяет анализировать их традиционными биоинформатическими методами и при этом не дает скомпроментировать обладателя генома. Технология была представлена на конференции Американского научного общества AAAS, кратко о ней пишет Science. Технология ..
2014-02-18 1628 0 Научные открытия
0
Учёные совершают прорыв в расшифровке геномов человека
В 2001-ом году «Human Genome Project» и «Celera Genomics» объявили, что после 10-ти летней работы они завершили проект последовательности генома человека, бюджет которого составил примерно $ 400 миллионов. Сегодня же, всего за пару недель секвенирование генома человека может ..
2012-08-13 1949 0 Научные открытия
0
Челябинский ученый решил одну из семи неразрешимых задач
Математик из Челябинска Анатолий Панюков нашел решение одной из важнейших задач в современной науке. Как сообщил «Новому Региону» доктор физико-математических наук, профессор, заведующий кафедрой экономико-математических методов и статистики на факультете вычислительной математики и информатики Анатолий Панюков, с 1983 ..
2013-12-16 2940 0 Научные открытия
-1
Математики открыли новое наибольшее простое число
Математик Кертис Купер из Центрального университета Миссури в городе Уорренсберг открыл новое наибольшее из известных науке простое число. Оно равно 274207281 – 1 и содержит 22 338 618 цифр. Об этом сообщает издание New Scientist.Простым числом называется натуральное число, имеющее только ..
2016-01-20 2107 0 Научные открытия
2
Российские программисты помогли астроному МГУ найти черные дыры
Международная группа астрономов под руководством Ивана Золотухина из Московского государственного университета имени Михаила Ломоносова (МГУ) при помощи российских программистов-волонтеров приблизилась к пониманию черных дыр промежуточной массы. Результаты исследований опубликованы в The Astrophysical Journal. О них сообщается в пресс-релизе МГУ, поступившем ..
2016-01-24 1394 0 Научные открытия
0
Математики помогут ускорить интернет
Сотрудники Массачусетского технологического института разработали теорию передачи информации в коммуникационных сетях, позволяющую оптимизировать емкость сетей и объем передаваемых данных. Работа разбита на две части, первая и которых опубликована в журнале IEEE Transactions on Information Theory. Препринты статей ..
2012-05-15 1302 0 Научные открытия
0
Учёные объяснили несимметричность вселенной
Ученые показали, как физические законы, симметрично действующие в пространстве, могут приводить к образованию несимметричных объектов, которых в нашей вселенной большинство. Работа опубликована в журнале Physical Review Letters. Краткое содержание статьи можно прочитать на сайте Американского физического общества. Исследователи ..
2012-04-26 1501 0 Научные открытия
0
В клетках обнаружены прогнозирующие рак «часы смерти»
Вероятность развития рака у человека может быть предопределена двумя «часами» мутаций ДНК, обнаруженными практически во всех клетках организма человека. Об открытии сообщается на страницах журнала Nature Genetics, а коротко о нем рассказал New Scientist.Речь идет о мутациях в ДНК (изменениях отдельных ..
2015-11-11 2001 0 Научные открытия
0
Физики построили квантовый компьютер в алмазе
Новое устройство содержит всего два кубита, но зато демонстрирует хорошую устойчивость. При этом кристалл работает при комнатной температуре. Последняя деталь будет очень важна, если исследователи когда-нибудь попытаются сделать квантовые компьютеры по-настоящему массовыми.  Физики из Нидерландов и США создали ..
2015-10-11 1896 0 Научные открытия
1
Компьютер проверил доказательство гипотезы Кеплера
Машина подтвердила правильность доказательства гипотезы Кеплера математиком Томасом Хейлзом (Thomas Hales) из Питтсбургского университета в США. Как считают специалисты, это демонстрирует широкие возможности компьютеров для проведения трудоемких вычислительных доказательств, позволяя человеку сконцентрироваться на концептуальных сторонах проверки, ..
2014-08-14 1638 0 Научные открытия
0