Квантовым компьютерам приписывают возможности, далеко превосходящие обычные вычислительные системы. Но здесь давно существует неудобная проблема: как доказать, что квантовая машина действительно сделала нечто недоступное классическому компьютеру, если проверка ее ответа сама может оказаться чрезвычайно сложной?
Исследователи предложили необычное решение — превратить проверку в своего рода игру, для которой можно математически определить предел возможностей любого обычного компьютера.
А затем дали ту же задачу квантовой машине.
Она этот предел уверенно превысила. Более того, чем сложнее становился эксперимент, тем больше увеличивался разрыв между результатом квантового компьютера и максимально возможным результатом классической системы.
В основе эксперимента лежит одно из главных свойств квантовых вычислений — суперпозиция.
В обычном компьютере бит может принимать одно из двух значений: ноль или единицу. Квантовый бит до момента измерения способен находиться в суперпозиции двух состояний. При измерении это состояние превращается в один конкретный результат.
Именно возможность работать с суперпозицией до измерения исследователи и решили проверить.
Для этого они использовали задачу, которую можно представить довольно просто.
Допустим, все возможные ответы тайно разделили на две равные группы — А и Б. Компьютеру дают один случайно выбранный ответ из группы А и предлагают назвать любой ответ из группы Б.
У обычного компьютера информации почти нет. Он знает только одно: полученный вариант принадлежит группе А, поэтому возвращать его нельзя. Но про остальные варианты он не знает, какие относятся к А, а какие — к Б.
Чем больше возможных ответов, тем меньше пользы от этой единственной подсказки.
Исследователям удалось математически доказать, насколько успешно в такой ситуации вообще может действовать лучшая возможная классическая стратегия. То есть речь идет не о том, что пока никто не придумал достаточно хороший алгоритм. Существует строгий предел, выше которого классический компьютер подняться не может.
У квантового компьютера ситуация принципиально иная.
Вместо одного случайного ответа из группы А он может получить квантовое состояние, в котором вся группа А представлена в суперпозиции. Затем это состояние можно изменить еще до измерения.
Исследователи использовали специальную квантовую схему, которая превращала состояние, соответствующее группе А, в состояние ее дополнения — группы Б.
И только после этого проводилось измерение. В идеальной квантовой системе результат всегда должен принадлежать группе Б.
Именно здесь возникает огромное различие между двумя подходами. По мере роста задачи возможности лучшей классической стратегии ухудшаются экспоненциально, тогда как идеальная квантовая система продолжает давать правильный результат каждый раз.
Получив такой тест, исследователи решили проверить уже не теорию, а настоящий квантовый компьютер.
Эксперименты провели на квантовых системах компании Quantinuum с захваченными ионами. Ученые использовали тысячи различных схем и постепенно увеличивали размер эксперимента до 55 квантовых битов.
Реальные устройства, конечно, оказались неидеальными. Чем больше становился эксперимент и чем больше квантовых операций требовалось выполнить, тем сильнее аппаратные помехи ухудшали результат.
Но даже с этими ошибками квантовый компьютер стабильно превышал математически установленный предел классических систем.
Во всех проведенных экспериментах результаты были настолько высокими, что статистически не соответствовали тому, чего могла бы добиться любая классическая стратегия.
Причем с увеличением сложности задачи преимущество росло. Наблюдаемый разрыв увеличивался экспоненциально вместе с длиной последовательностей битов и был близок к тому, что предсказывалось для оптимальной квантовой стратегии.
В самом крупном из таких испытаний использовались последовательности длиной 37 бит. Теоретически идеального результата квантовый компьютер не достиг, однако исследователи все равно зафиксировали экспоненциально большое нарушение классического предела.
У эксперимента остается важное ограничение. Система, которая задавала исходное состояние, и система, которая должна была его обработать, фактически находились внутри одного квантового компьютера. Передачу между ними имитировали с помощью квантовой телепортации.
В более строгом варианте такого теста потребовались бы два отдельных квантовых компьютера, соединенных настоящим квантовым каналом связи.
Тем не менее нынешний эксперимент уже показывает принципиальную возможность такого подхода. Его результат сравнительно легко проверить, сложность можно постепенно увеличивать, а предел для классических компьютеров основан на математическом доказательстве, а не на предположении, что подходящего обычного алгоритма пока просто не нашли.
Авторы работы отмечают, что их тест позволяет продемонстрировать вычислительную силу квантовой суперпозиции без необходимости опираться на квантовую запутанность и нелокальность.
Исследование опубликовано в журнале Nature Communications.
