Ученые компании Quantinuum опубликовали в Nature Communications результаты нового теста квантового превосходства. Принципиальная особенность работы: в отличие от большинства прежних демонстраций, итоги этого эксперимента проверяются классическими методами и не опираются на недоказанные предположения о вычислительной сложности.
Авторы — Marcello Benedetti, Gabriel Marin-Sanchez, Jordi Weggemans, Matthias Rosenkranz и Harry Buhrman из лондонского офиса Quantinuum — разработали игру на основе задачи complement sampling. Суть в следующем: все возможные ответы делятся на два равных множества, A и B. Игрок получает случайный элемент из A и должен вернуть ответ из B, то есть из дополнения. Классическому компьютеру для этого нужно все больше попыток с каждым добавленным битом задачи: шансы на успех падают экспоненциально, и никакой алгоритм не обходит этот математический предел.
Квантовая машина работает принципиально иначе. Кубит в суперпозиции способен удерживать все множество A одновременно, а переключающая схема преобразует его в дополнение B — и компьютер выдает правильный ответ за один шаг. Там, где классике нужны сотни проб пропорционально размеру задачи, квантовой машине достаточно одной. Именно это делает классический успех математически невозможным по мере роста задачи.
В эксперименте задействовали квантовый компьютер H2 от Quantinuum на ионах-ловушках. Система прогнала тысячи схем и масштабировалась до 55 кубитов; максимальная сложность задачи составила 37-битные строки. Во всех тестах квантовая система устойчиво превышала теоретический предел лучшей классической стратегии, а разрыв нарастал экспоненциально по мере усложнения задачи. При 37-битных строках зафиксировано «экспоненциально большое нарушение классичности», хотя идеального теоретического результата достичь не удалось.
Пока у эксперимента есть одно ограничение: роли судьи и игрока выполнял один и тот же квантовый компьютер, а канал связи между ними имитировала квантовая телепортация. Следующий шаг — повторить тест на двух отдельных машинах с настоящим квантовым каналом.
Ранее мы рассказывали, как квантовый компьютер справился с задачей за гранью возможного для классических машин.
Источник новости: hi-tech.mail.ru
