Квантовый вычислитель опередил классический в решении новой задачи, а точнее в проверке этого решения. Физики экспериментально реализовали протокол проверки решения задачи, которую нельзя решить на классическом компьютере за полиномиальное время. Они показали, что для проверки квантовой машине требуется в тысячу раз меньше информации. Работа опубликована в Nature Communications.
Квантовый компьютер сильнее и мощнее классического не в любой задаче, об этом мы подробнее рассказывали в материале «Когда ждать квантового превосходства». Пока ученым удалось продемонстрировать квантовое превосходство на задачах генерации случайной строки и бозонного сэмплинга. С прикладной точки зрения эти задачи не представляют какой-то ценности — они показывают возможности квантовых вычислителей и их будущего в целом. Демонстрация решения более применимых и реальных задач упирается в маленькое число кубитов вычислителя.
Выбор задач, которые учатся решать на квантовых вычислителях, неслучаен. Квантовый компьютер должен справиться с задачами, решение которых занимает у классического неограниченное время. Ученые давно сталкиваются с такими задачами и уже успели разделить их на классы сложности в зависимости от того, как быстро увеличивается время решения задачи при увеличении числа входных данных. Причем под временем решения задачи подразумевается время, которое потребуется самому быстрому алгоритму. Неопределенность, которая таится в термине «самый быстрый алгоритм» (вдруг он есть, а ученые его еще не придумали и не нашли) рождает известную задачу равенства классов P и NP. NP класс сложности включает задачи, решение которых можно проверить за полиномиальное время при наличии дополнительных сведений, а класс P — задачи, для которых зависимость времени решения от размерности задачи полиномиальная. Считается, что квантовые алгоритмы могут поставить точку в этом вопросе.
Одна из популярных задач для квантовых вычислителей — задача о выполнимости булевых формул (SAT). Она не просто принадлежит классу NP, но и любую NP сложную задачу можно свести к ней (такой подкласс NP сложности называют NP-полным). N-SAT задача состоит из набора условий, каждое из которых в свою очередь состоит из N булевых переменных (могут принимать значения 0 или 1). В условие может входить как переменная, так и ее отрицание (НЕ). Задачу можно решить, если найти такой набор переменных, что итоговая формула будет верна (равна 1). К примеру, 2-SAT задача может выглядеть так: (X1 ИЛИ X3) И (НЕ X2 ИЛИ X1). Получается, что для решения задачи нужно, чтобы каждая скобка была равна 1. Тогда для решения достаточно зафиксировать X1 = 1, а X2 и X3 могут быть любыми. Понятно, что увеличение числа условий (скобок) усложняет задачу, как и число элементов в скобке.
Команда физиков под руководством Иорданиса Керенидиса (Iordanis Kerenidis) смогли показать экспериментально, что квантовый вычислитель быстрее справляется с проверкой решения NP-полной задачи, чем классический и рассмотрели все возможные реальные ограничения, которые возникают в эксперименте. Ученые рассматривали интересную задачу 2-out-of-4 SAT: в каждой скобке из четырех переменных как минимум две должны быть 1.
Схема для проверки решения, которое присылает Мерлин. Артур при этом генерирует последовательность когерентных импульсов, которые по очереди взаимодействуют с импульсами Мерлина и в зависимости от того, на каком детекторе обнаружен клик можно понять что за состояние послал Мерлин
Для того чтобы реализовать проверку решения, необходимо два человека — в квантовом мире это Мерлин и Артур. Мерлин находит какое-то предположительно верное решение задачи и отправляет его Артуру, который проверяет это решение на верность. Важно отметить, что Мерлин и Артур работают в условиях ограниченной информации, то есть Мерлин не может выслать все задание целиком. И в классическом мире, если же Артур будет проверять по одному случайному условию, то Мерлин может каждый раз менять значения переменных, что исказит проверку. В квантовом мире, Мерлин кодирует возможное решение задачи с помощью когерентных состояний и отправляет его Артуру. Артур готовит свой набор последовательных состояний с нужной амплитудой и разделением по времени. Состояния Артура и Мерлина интерферируют на светоделителе и в зависимости от фазы состояния Мерлина кликает либо один, либо другой детектор. Увеличение числа фотонов в одном импульсе увеличивает вероятность задетектировать состояние и делает схему более эффективной.
В проверке верности решения играют важную роль две вероятности: первая показывает как часто при действительно правильном решении результат верификации это подтверждает, а вторая описывает ситуацию, когда проверяющий принял неверное решение за верное. Первую (С) стараются увеличить, а вторую (S) уменьшить. Авторам удалось получить C больше 0.9 при удержании S меньше 0.6.
Помимо этого, для неверного решения имеет значение число условий, которое оказалось невыполненным. Ученые зафиксировали это значение на уровне 15 процентов, число переменных они выбирали равным десяти тысячам. Для расчета реальной экспериментальной схемы, они учли неидеальность детекторов и выбрали значение видности в 0.91 (в идеале она равна 1). При всех перечисленных параметрах, исследовали искали такое оптимальное число фотонов в импульсе для демонстрации преимущества квантового вычислителя перед классическим. Оказалось, что разрыв между вероятностью C и S близок к единице в широком диапазоне и для эксперимента авторы использовали величину в 1.31. Эксперимент показал, что для проверки квантовый вычислитель требует в тысячу раз меньше бит, чем классический.
Задача проверки решения в отличие от предыдущих задач для демонстрации возможностей квантовый вычислителей, делает шаг на пути к реальным применениям. Физики предлагают использовать мощные квантовые вычислители для решения задач, а проверку верности решений проводить на менее мощных машинах. Другим возможным применением они видят квантовый интернет.
«Железом» в эксперименте ученых служили фотоны, как и в эксперименте китайских физиков, которые показали преимущество квантового вычислителя в решении задачи бозонного сэмплинга. А самой первой демонстрацией квантового превосходства была работа ученых из Google, в которой они использовали вычисилитель на сверхпроводниках.
По информации https://nplus1.ru/news/2021/02/15/QMA-advantage
Обозрение "Terra & Comp".
