В каких конкретных случаях квантовые компьютеры превосходят свои классические аналоги? На этот вопрос сложно ответить, отчасти потому, что современные квантовые компьютеры — привередливые штуки, изобилующие ошибками, которые могут накапливаться и портить их вычисления.

По одному показателю, конечно, они уже сделали это. В 2019 году физики Google объявило что они использовали 53-кубитную машину для достижения квантовое превосходство, символическая веха, отмечающая точку, в которой квантовый компьютер делает что-то, что выходит за рамки досягаемости любого практического классического алгоритма. Подобные демонстрации вскоре последовали физики из Университета науки и технологий Китая.

Но вместо того, чтобы сосредотачиваться на экспериментальном результате для одной конкретной машины, ученые-компьютерщики хотят знать, смогут ли классические алгоритмы идти в ногу со временем, когда квантовые компьютеры становятся все больше и больше. «Надежда состоит в том, что в конечном итоге квантовая сторона просто полностью уйдет, пока не исчезнет конкуренция», — сказал он. Скотт Аронсон, ученый-компьютерщик Техасского университета в Остине.

На этот общий вопрос до сих пор трудно ответить, опять же отчасти из-за этих надоедливых ошибок. (Квантовые машины будущего будут компенсировать свои несовершенства с помощью техники, называемой квантовая коррекция ошибок, но до такой возможности еще далеко.) Можно ли получить долгожданное безудержное квантовое преимущество даже при неисправленных ошибках?

Большинство исследователей подозревали, что ответ отрицательный, но они не могли доказать это во всех случаях. Теперь, в бумаги Опубликовано на сервере препринтов arxiv.org, группа ученых-компьютерщиков сделала важный шаг к всестороннему доказательству того, что исправление ошибок необходимо для устойчивого квантового преимущества при выборке случайных цепей — специальной задачи, которую Google использовал для демонстрации квантового превосходства. Они сделали это, разработав классический алгоритм, который может имитировать эксперименты со случайной выборкой схемы при наличии ошибок.

«Это прекрасный теоретический результат», — сказал Ааронсон, подчеркнув при этом, что новый алгоритм практически бесполезен для имитации реальных экспериментов, подобных экспериментам Google.

В экспериментах по выборке случайных цепей исследователи начинают с массива кубитов или квантовых битов. Затем они случайным образом манипулируют этими кубитами с помощью операций, называемых квантовыми вентилями. Некоторые вентили вызывают запутывание пар кубитов, то есть они имеют общее квантовое состояние и не могут быть описаны отдельно. Повторяющиеся слои ворот приводят кубиты в более сложное запутанное состояние.

Чтобы узнать об этом квантовом состоянии, исследователи затем измеряют все кубиты в массиве. Это приводит к тому, что их коллективное квантовое состояние схлопывается до случайной строки обычных битов — нулей и единиц. Число возможных результатов быстро растет вместе с количеством кубитов в массиве: с 0 кубитами, как в эксперименте Google, получается почти 1 квадриллионов. И не все строки одинаково вероятны. Выборка из случайной схемы означает многократное повторение таких измерений для построения картины распределения вероятностей, лежащей в основе результатов.

Вопрос квантового преимущества заключается просто в следующем: трудно ли сымитировать это распределение вероятностей? с классическим алгоритмом который не использует запутанность?

В 2019 исследователи доказанный что ответ положительный для безошибочных квантовых схем: действительно трудно классически смоделировать эксперимент случайной выборки схемы, когда нет ошибок. Исследователи работали в рамках теории вычислительной сложности, которая классифицирует относительную сложность различных задач. В этой области исследователи не рассматривают количество кубитов как фиксированное число, такое как 53. «Думайте об этом как о n, то есть какое-то число, которое будет увеличиваться, — сказал Арам Харроу, физик Массачусетского технологического института. «Тогда вы хотите спросить: делаем ли мы что-то, где усилия экспоненциальны в n или многочлен от n?» Это предпочтительный способ классификации времени выполнения алгоритма — когда n становится достаточно большим, алгоритм, экспоненциальный в n сильно отстает от любого полиномиального алгоритма n. Когда теоретики говорят о проблеме, сложной для классических компьютеров, но простой для квантовых, они имеют в виду следующее различие: лучший классический алгоритм требует экспоненциального времени, в то время как квантовый компьютер может решить задачу за полиномиальное время.

Тем не менее, в статье 2019 года не учитывались последствия ошибок, вызванных несовершенными вентилями. Это оставило открытым случай квантового преимущества для случайной выборки схемы без исправления ошибок.

Если вы представляете постоянное увеличение числа кубитов, как это делают теоретики сложности, и хотите также учитывать ошибки, вам необходимо решить, собираетесь ли вы также продолжать добавлять дополнительные слои вентилей — увеличивая глубину схемы, как говорят исследователи. Предположим, вы поддерживаете постоянную глубину схемы, скажем, относительно неглубокие три слоя, по мере увеличения количества кубитов. Вы не получите большой запутанности, а результат все равно будет поддаваться классическому моделированию. С другой стороны, если вы увеличите глубину схемы, чтобы не отставать от растущего числа кубитов, кумулятивный эффект ошибок вентилей размоет запутанность, и результат снова станет легко моделировать классически.

Но между ними лежит зона Златовласки. До появления новой статьи существовала вероятность того, что здесь сохранится квантовое преимущество, даже если число кубитов увеличилось. В этом случае с промежуточной глубиной вы увеличиваете глубину схемы очень медленно по мере роста числа кубитов: даже несмотря на то, что выход будет постоянно ухудшаться из-за ошибок, все же может быть сложно классически моделировать на каждом шаге.

Новая газета закрывает эту лазейку. Авторы вывели классический алгоритм моделирования выборки случайных цепей и доказали, что время его выполнения является полиномиальной функцией времени, необходимого для проведения соответствующего квантового эксперимента. Результат устанавливает тесную теоретическую связь между скоростью классического и квантового подходов к выборке случайных цепей.

Новый алгоритм работает для основного класса цепей средней глубины, но лежащие в его основе допущения не работают для некоторых более мелких цепей, оставляя небольшой пробел, в котором неизвестны эффективные классические методы моделирования. Но немногие исследователи надеются, что случайная выборка схемы окажется сложной для классического моделирования в этом остающемся узком окне. «Я ставлю на это довольно маленькие шансы», — сказал Билл Фефферман, ученый-компьютерщик из Чикагского университета и один из авторов теоретической статьи 2019 года.

Результат предполагает, что случайная выборка схемы не даст квантового преимущества по строгим стандартам теории вычислительной сложности. В то же время это иллюстрирует тот факт, что полиномиальные алгоритмы, которые теоретики сложности без разбора называют эффективными, на практике не обязательно работают быстро. Новый классический алгоритм становится все медленнее по мере уменьшения частоты ошибок, а при низкой частоте ошибок, достигнутой в экспериментах по квантовому превосходству, он слишком медленный, чтобы его можно было использовать на практике. Без ошибок он полностью ломается, поэтому этот результат не противоречит ничему, что знали исследователи о том, как сложно классически моделировать случайную выборку схемы в идеальном, безошибочном случае. Серхио Бойшу, физик, возглавляющий исследование Google в области квантового превосходства, говорит, что считает статью «больше хорошим подтверждением случайной выборки цепей, чем чем-либо еще».

В одном все исследователи согласны: новый алгоритм подчеркивает, насколько решающей будет коррекция квантовых ошибок для долгосрочного успеха квантовых вычислений. «Это решение, в конце концов», сказал Фефферман.

Примечание редактора: Скотт Ааронсон является членом Консультативного совета журнала Quanta.