Квантовый вычислитель опередил классический в решении новой задачи, а точнее в проверке этого решения. Физики экспериментально реализовали протокол проверки решения задачи, которую нельзя решить на классическом компьютере за полиномиальное время. Они показали, что для проверки квантовой машине требуется в тысячу раз меньше информации. Работа опубликована в 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.
Поделиться
Поделиться
Помимо этого, для неверного решения имеет значение число условий, которое оказалось невыполненным. Ученые зафиксировали это значение на уровне 15 процентов, число переменных они выбирали равным десяти тысячам. Для расчета реальной экспериментальной схемы, они учли неидеальность детекторов и выбрали значение видности в 0.91 (в идеале она равна 1). При всех перечисленных параметрах, исследовали искали такое оптимальное число фотонов в импульсе для демонстрации преимущества квантового вычислителя перед классическим. Оказалось, что разрыв между вероятностью C и S близок к единице в широком диапазоне и для эксперимента авторы использовали величину в 1.31. Эксперимент показал, что для проверки квантовый вычислитель требует в тысячу раз меньше бит, чем классический.
Задача проверки решения в отличие от предыдущих задач для демонстрации возможностей квантовый вычислителей, делает шаг на пути к реальным применениям. Физики предлагают использовать мощные квантовые вычислители для решения задач, а проверку верности решений проводить на менее мощных машинах. Другим возможным применением они видят квантовый интернет.
«Железом» в эксперименте ученых служили фотоны, как и в эксперименте китайских физиков, которые показали преимущество квантового вычислителя в решении задачи бозонного сэмплинга. А самой первой демонстрацией квантового превосходства была работа ученых из Google, в которой они использовали вычисилитель на сверхпроводниках.
Оксана Борзенкова