Квантовому компьютеру недостаточно просто использовать необычные свойства квантовой физики, чтобы обойти обычную вычислительную машину. Новая теоретическая работа показала, что даже специальные состояния кубитов, которые физики называют магическими, не всегда дают вычислительное преимущество. Часть операций с такими состояниями удаётся эффективно воспроизвести на обычном компьютере. Исследование расширяет круг квантовых вычислений, доступных классическому моделированию, и одновременно уточняет условия, при которых квантовый процессор действительно способен получить преимущество.
Квантовые компьютеры работают с кубитами. В отличие от обычного бита, который принимает значение ноль или единица, кубит может находиться в суперпозиции нескольких состояний. Однако суперпозиции и других квантовых свойств недостаточно для автоматического ускорения вычислений. Существуют квантовые схемы, поведение которых классический компьютер способен моделировать без экспоненциального роста затрат. Поэтому физикам нужен более точный способ отделить вычисления, доступные обычной технике, от задач, для которых квантовый процессор действительно даёт преимущество.
Одна из важных границ проходит между стабилизаторными и магическими состояниями. Стабилизаторные состояния используют квантовые эффекты, включая суперпозицию и запутанность, но вычисления из определённого набора стабилизаторных операций можно эффективно моделировать классическими методами. Для универсальных квантовых вычислений к таким схемам добавляют магические состояния . В теории квантовых вычислений магические состояния служат дополнительным ресурсом, который позволяет выйти за пределы эффективно моделируемого стабилизаторного режима.
Из-за этой роли магию долго рассматривали как один из главных признаков вычислительного ресурса квантовой системы. Новая работа проводит внутри магических состояний ещё одну границу. Исследователи нашли состояния, которые формально относятся к магическим, но не дают квантового преимущества в изученной модели. Классический компьютер по-прежнему способен эффективно воспроизводить соответствующие вычисления.
Разобраться в различии помогло распределение Кирквуда-Дирака, один из видов квантовых квазивероятностных распределений. Джон Кирквуд предложил соответствующую конструкцию в 1933 году, а Поль Дирак независимо разработал близкий математический аппарат в 1945 году. Такая форма записи применяется для описания квантовых состояний и процессов, в том числе при работе с несовместимыми наблюдаемыми.
Главное отличие квазивероятности от обычной вероятности связано с допустимыми значениями. Вероятность выпадения орла при броске монеты не может быть меньше нуля. В квантовых квазивероятностных описаниях отдельные элементы распределения могут принимать отрицательные, а в некоторых вариантах и комплексные значения. Отрицательное число не означает отрицательную вероятность реального события. Математический знак показывает, что квантовое состояние нельзя полностью описать обычной классической вероятностной моделью. Для распределения Кирквуда-Дирака отрицательные или невещественные значения уже связывали с неклассическими свойствами квантовых систем и преимуществами в отдельных квантовых задачах.
Авторы новой работы применили отрицательность распределения Кирквуда-Дирака к вопросу о вычислительном преимуществе. Если при заданном входном состоянии распределение на протяжении вычисления остаётся неотрицательным, квантовый процесс можно эффективно смоделировать классическим способом. Наличие магического состояния в такой схеме не меняет результата. Формальная магия сохраняется, но дополнительной вычислительной силы, недоступной обычному компьютеру, не появляется.
Появление отрицательных значений меняет ситуацию. Классическая симуляция для рассматриваемого класса вычислений теряет эффективный способ воспроизводить квантовый процесс, а необходимые вычислительные ресурсы могут расти экспоненциально. Поэтому отрицательность распределения Кирквуда-Дирака служит дополнительным необходимым условием квантового преимущества наряду с магией.
Отрицательные значения при этом не гарантируют автоматической победы квантового процессора над любым классическим алгоритмом. Новая теория работает в обратную сторону: отсутствие отрицательности позволяет определить класс состояний, для которых преимущества точно не возникает в рассматриваемой вычислительной модели. Такое условие отсекает часть магических состояний, которые раньше могли считать перспективными только из-за принадлежности к нестабилизаторному классу.
Получается более строгая иерархия вычислительных ресурсов. Стабилизаторных состояний недостаточно для получения рассматриваемого квантового преимущества. Магические состояния позволяют выйти за пределы стабилизаторной схемы, но часть из них классический компьютер всё равно обрабатывает эффективно. Дополнительную границу задаёт отрицательность распределения Кирквуда-Дирака.
Теоретический вывод исследователи проверили с помощью программы классического моделирования. Программа работает на обычном ноутбуке и выполняет вычисления с состояниями, которые обладают магией, но сохраняют неотрицательное распределение Кирквуда-Дирака. Компьютер справился без квантового процессора, подтвердив, что область эффективного классического моделирования шире, чем следует из одного деления состояний на стабилизаторные и магические.
Результат не означает, что ноутбук способен заменить квантовый компьютер в перспективных квантовых алгоритмах. Эксперимент показывает более конкретную вещь: принадлежность состояния к магическим ещё не доказывает недоступность вычисления для классической машины. При проверке квантового преимущества приходится учитывать лучшие известные методы классического моделирования, иначе преимущество можно ошибочно приписать процессу, который обычный компьютер способен воспроизвести достаточно эффективно.
Уточнение особенно важно для разработки отказоустойчивых квантовых компьютеров. Подготовка магических состояний относится к трудным и ресурсоёмким операциям в архитектурах, основанных на коррекции квантовых ошибок . Разработчикам приходится получать состояния высокой точности, очищая их от ошибок с помощью специальных процедур. Если часть магических состояний не обеспечивает нужного вычислительного ресурса, одного факта успешной подготовки недостаточно. Инженерам и разработчикам алгоритмов важно понимать, какие состояния действительно выводят вычисление за пределы эффективной классической симуляции.
Работа также повышает требования к экспериментальным заявлениям о квантовом преимуществе. Квантовое устройство должно решать задачу, для которой не существует эффективного классического способа воспроизвести вычисление. Новая теория переносит часть ранее подозрительных с этой точки зрения состояний обратно в классически моделируемую область. Граница между двумя типами вычислений проходит дальше, чем показывал один критерий магии.
Полного ответа на вопрос, какие физические ресурсы обеспечивают всю вычислительную мощность квантовых компьютеров, у теории пока нет. Новое исследование уточняет один важный участок этой границы: магия необходима для рассматриваемого вида квантового преимущества, но одной магии недостаточно. Распределение Кирквуда-Дирака даёт дополнительный критерий. Если распределение остаётся неотрицательным на протяжении вычисления, классическая машина сохраняет эффективный способ симуляции. Работа опубликована в Physical Review Letters.