Райан Ф. Мандельбаум, старший технический писатель, Qiskit
Среди наиболее важных текущих задач на заре квантовых вычислений - выявление проблем, которые современные квантовые устройства могут решать лучше, чем классические компьютеры. Новая статья доказала, что при правильных обстоятельствах бывают ситуации, когда даже шумные квантовые компьютеры, склонные к неожиданным изменениям в их значениях кубитов, могут превзойти классический компьютер - на схеме, которую вы можете запустить самостоятельно.
Сегодняшние квантовые компьютеры ограничены своими ошибками, количеством кубитов, с помощью которых кубиты могут взаимодействовать друг с другом, и тем фактом, что они могут запускать схемы только с ограниченным количеством дискретных шагов, прежде чем они потеряют свою квантовость. Два года назад группа международных исследователей, включая Сергея Бравого из IBM, доказала, что квантовые эффекты позволяют этим ограниченным квантовым компьютерам превосходить классические компьютеры для определенного набора задач, при условии, что классические компьютеры были ограничены запуском схем с постоянной глубиной - схемы с верхней границей количества дискретных шагов, которые они могут выполнить. Команда Брави теперь опубликовала доказательство алгоритма, в котором квантовые компьютеры, которым мешает шум, как те, которые существуют сегодня, могут превзойти классический компьютер, работающий со схемами постоянной глубины.
Почему нужно восхищаться тем, что квантовый компьютер превосходит ограниченный классический компьютер? Что ж, спросить, может ли квантовый компьютер, работающий со схемами малой глубины, превзойти любой классический алгоритм, слишком сложно. Что, если есть какой-то классический алгоритм, о котором мы еще не придумали? Кроме того, такое сравнение похоже на гонку картофельных мешков, где классическому компьютеру не нужен мешок - сопоставление квантовых схем постоянной глубины с классическими схемами постоянной глубины, возможно, является более подходящим способом продемонстрировать преимущества вычислений. с кубитами имеет чрезмерные вычисления с классическими битами, особенно с учетом того, что количество и качество кубитов в квантовых компьютерах увеличивается. Эта новая статья представляет собой скорее прямое сравнение двух различных методов вычислений и строгое доказательство того, что квантовые биты, даже зашумленные квантовые биты, превосходят классические биты в той же гонке.
Или, говоря словами Брави: С точки зрения теории сложности, этот результат представляет собой первое строгое разделение вычислительной мощности шумных квантовых схем постоянной глубины и бесшумных классических схем постоянной глубины.
Исследователи занялись игрой в магический квадрат Мермина-Переса, которая обсуждалась в статьях 1990 года физиков Ашера Переса и Н. Дэвида Мермина. Алисе и Бобу показан квадрат размером три на три. Судья просит Алису назначить 0 и 1 трем полям в одном из столбцов так, чтобы было нечетное количество единиц, и просит Боба сделать то же самое для одной из строк, чтобы было четное количество единиц, все, не общаясь друг с другом. Они выигрывают, если присваивают одинаковое значение ячейке, в которой пересекаются столбец и строка, и проигрывают в противном случае. Никакая стратегия, основанная на угадывании, не позволит Алисе и Бобу выиграть более восьми раз из девяти, потому что общее количество единиц в сетке должно быть четным или нечетным - так что, если бы Алиса и Боб заполняли всю сетку на основе своих соответствующие четные и нечетные ограничения, один квадрат гарантированно будет отличаться между двумя их заполнениями. Однако, если им разрешено генерировать и совместно использовать пару запутанных кубитов до заполнения своего столбца или строки, и если они могут взять с собой портативный квантовый компьютер (или, возможно, свой мобильный телефон, имеющий доступ к квантовому компьютеру в облаке), они могут выигрывать игру каждый раз, даже если они не разговаривают друг с другом.
Вы можете представить квантовое решение игры «магический квадрат» на квантовой схеме, как показано на рисунке (а). Обратите внимание, что U- и V-вентили здесь не относятся к общим U-образным вентилям Qiskit, а относятся к классически управляемым вентилям, которые принимают пару битов, обозначенных в таблице в (b):
Здесь гамма представляет двоичную форму столбца 1, 2 и 3 (01, 10 и 11), а альфа и бета обозначают строку или столбец, которые выбирают Алиса и Боб, соответственно. Измерение этой схемы дает два бита x для Алисы, x1 и x2, и она устанавливает третий бит равным x1 + x2 + 1 по модулю 2. Боб вычисляет два бита y, y1 и y2, и устанавливает свой третий бит равным y1 + y2 по модулю 2. Алиса и Боб используют эти три бита для заполнения своих столбцов / строк, и вуаля, они выиграли.
Для доказательства, опубликованного на этой неделе в журнале Nature Physics, команда разработала более обобщенную форму задачи для проверки на классических схемах постоянной глубины. Вы можете думать об этом как о привлечении большего количества игроков к игре, где два игрока - это Алиса и Боб, а остальные игроки должны помочь им запутать свои кубиты на большем расстоянии.
Почему квантовый компьютер превосходит ограниченный классический компьютер? Что ж, квантовый компьютер может вычислить ответ на эту проблему за одно и то же количество шагов, независимо от размера проблемы. Но согласно доказательству, если вам требуется, чтобы классическое решение постоянной глубины подходило для девяти из десяти экземпляров проблемы, то время, необходимое для решения проблемы, будет логарифмически увеличиваться с размером входных данных. Чтобы доказать, что это работает даже для шумных квантовых компьютеров, исследователи моделируют шумовой вентиль, включая случайный вентиль Паули, то есть вентили X, Y и Z, которые будут действовать с некоторой вероятностью P после каждого идеального вентиля. Математическое доказательство демонстрирует, что даже квантовый компьютер, включающий эти ошибки, может найти ответ на проблему магического квадрата более чем в 99% случаев, если он включает в свое решение стратегию исправления ошибок. По словам Брави, команда не пыталась рассчитать самый шумный квантовый компьютер, который выиграет, поэтому «шумный» все же может относиться к компьютеру, где ошибка возникает только для одного из каждых 10¹⁰ или даже для одного из каждых 10¹⁰⁰ ворот. Но он ожидал, что самый шумный из возможных квантовых компьютеров-победителей может иметь ошибку на каждые 100 или 1000 вентилей, что примерно соответствует уровню ошибок современных квантовых устройств.
Будущие поколения квантовых компьютеров могут действительно иметь возможность запускать эту схему с помощью этих стратегий исправления ошибок, которые вводят избыточные кубиты во избежание ошибок. Некоторым гейтам требуется много избыточных кубитов для исправления ошибок, но этот алгоритм полагается исключительно на вентили Клиффорда, группу, состоящую по существу из комбинаций четырех вентилей Паули (I, X, Y, Z), управляемые вентили Паули и вентиль Адамара, на которых исправление ошибок может быть реализовано с меньшим количеством избыточных кубитов. Доказательство использует метод исправления ошибок поверхностный код (который, вероятно, полностью заслуживает отдельного блога), где каждый кубит связан с несколькими другими кубитами, что предотвращает переворот его битового значения или изменение его фазы. Короче говоря, квантовый компьютер ближайшего будущего с реализованными стратегиями исправления ошибок поверхностного кода может успешно решить проблему магического квадрата в 99% случаев.
Решение задачи магического квадрата тоже не выходит за рамки возможностей устройства IBM с Qiskit. Вот код, который вы можете попробовать и изменить:
Эти статьи не представляют собой квантовые компьютеры, полностью сокрушающие классические компьютеры, и не представляют алгоритмы с очевидными приложениями. Но думайте о них как о фундаменте; каждое место, где ученые недвусмысленно доказывают ускорение квантового компьютера по сравнению с некоторыми элементами классических вычислений, помогает нам лучше понять эти устройства и может служить указателем на пути к квантовым приложениям в будущем.
Обновление 19.03.2021: Дэвид Дрекслин внес некоторые изменения и расширил написанный выше код, чтобы отобразить полное решение на четырех кубитах. Обратите внимание, что в приведенном выше коде была проблема с порядком ворот, которую я с тех пор исправил. Вы можете ознакомиться с версией Дэвида здесь, а также с другими забавными квантовыми проектами, организованными Яном-Райнером Лахманном здесь.
Попытка найти собственные квантовые преимущества - отличный повод научиться программировать с помощью Qiskit! Узнайте о Глобальной летней школе Qiskit и зарегистрируйтесь здесь до 10 июля, и начните свое квантовое путешествие.
