Недавно я прочитал пару лекций о квантовом преимуществе: одну на ежегодном собрании CIQC, другую — на программе KITP. Начал я с опроса аудитории: кто считает, что квантовое преимущество было достигнуто?
Аудитория состояла в основном из физиков-экспериментаторов и теоретиков, а также нескольких специалистов по теории компьютерных наук. Я был уверен, что большинство из них убеждены в успешной демонстрации квантового преимущества. В конце концов, более чем полдесятилетия прошло с момента первого экспериментального заявления (G1) о «квантовом превосходстве».
Идея «квантового превосходства» заключается в том, чтобы выполнять задачи с помощью управляемых квантовых систем, выходящие за рамки того, что можно достичь с помощью обычных цифровых компьютеров.
Однако оказалось, что менее половины присутствующих считали, что квантовое преимущество было достигнуто.
В обсуждениях, которые последовали, я понял, что именно критикуют в экспериментах, которые были проведены, и даже в самой концепции квантового преимущества. Но об этом позже.
В мини-серии из трёх постов я хочу исправить это и убедить вас, что существующие квантовые компьютеры могут выполнять задачи, которые не под силу классическим компьютерам.
Часть 1: что такое квантовое преимущество и что было сделано?
Мы достаточно убеждены, что бесшумные квантовые компьютеры смогут эффективно решать задачи, которые не под силу классическим компьютерам. Это стало ясно ещё в середине 90-х, когда Ллойд и Шор обнаружили два основных квантовых алгоритма: моделирование квантовых систем и разложение больших чисел на множители. Оба эти алгоритма — задачи, в которых мы уверены, что классические компьютеры не могут их решить.
Так зачем говорить о квантовом преимуществе 20 и 30 лет спустя?
Идея демонстрации квантового преимущества возникла как веха для этой области в 2010-х годах. Достижение квантового преимущества должно было наконец продемонстрировать, что квантовые вычисления — это не просто случайная идея кучки учёных, которые слишком серьёзно относятся к квантовой механике.
Что такое квантовое преимущество?
Квантовое устройство должно решать предварительно заданную вычислительную задачу. Это означает, что должен быть вход в квантовый компьютер. Учитывая вход, квантовый компьютер должен быть запрограммирован на решение задачи для данного входа.
Разница во времени, которое требуется квантовому компьютеру для решения задачи и времени, которое требуется классическому компьютеру, должна увеличиваться непропорционально, в идеале экспоненциально.
И, наконец, задача, решённая квантовым компьютером, не должна быть решаема ни одним классическим компьютером (на тот момент).
Достижение этого последнего критерия с помощью несовершенных, зашумлённых квантовых устройств — вот задача, которую идея квантового превосходства поставила перед этой областью.
Случайные схемы действительно сложно симулировать!
Идея проста: мы просто запускаем случайный вычислительный процесс, сконструированный таким образом, чтобы он был максимально благоприятным для квантового устройства, но при этом максимально сложным для классического компьютера.
Это может показаться довольно несправедливым способом придумать вычислительную задачу — она просто создана для того, чтобы быть сложной для классических компьютеров без какой-либо другой цели. Но это вполне вычислительная задача.
Есть вход: описание квантовой схемы, нарисованной случайным образом. Устройство должно быть запрограммировано для запуска этой точной схемы. И есть задача: просто вернуть всё, что вернёт этот квантовый вычислительный процесс.
Эта задача, получившая название «случайное выборка схем», может быть решена как на классическом, так и на квантовом компьютере, но для квантового компьютера есть (предположительно) экспоненциальное преимущество.
Более подробно об этом во второй части.
А пока позвольте мне рассказать вам об экспериментальных демонстрациях случайной выборки схем.
Задача, решаемая при случайной выборке схем, состоит в том, чтобы произвести битовые строки x∈{0,1}nx \in \{0,1\}^n, распределённые в соответствии с распределением исходов по правилу Борна pC(x)=|⟨x|C|0⟩|2p_C(x) = | \bra x C \ket {0}|^2.
Эта схема CC применяется к эталонному состоянию |0⟩\ket 0 на квантовом компьютере, а затем измеряется, давая строку xx в качестве результата.
Прорыв: сложно программируемые квантовые вычисления в реальном мире
В первом эксперименте по демонстрации квантового превосходства (G1) команда Google создала квантовый компьютер из 53 сверхпроводящих кубитов, расположенных в двумерной сетке.
Операции были выбраны случайным образом: простые однокубитные вентили (X,Y,X+Y\sqrt X, \sqrt Y, \sqrt{X+Y}) и детерминированные двухкубитные вентили, называемые fSim, применяемые в двумерном порядке и повторяемые определённое количество раз (глубина схемы).
Ограничивающим фактором в этих экспериментах было качество двухкубитных вентилей и измерений с вероятностями ошибок около 0,6 % и 4 % соответственно.
Очень похожий эксперимент был проведён командой USTC на 56 кубитах (U1), и оба эксперимента были повторены с лучшей точностью (0,4 % и 1 % для двухкубитных вентилей и измерений) и немного большими размерами системы (70 и 83 кубита соответственно) в последние два года (G2,U2).
Используя архитектуру с захватом ионов, команда Quantinuum также продемонстрировала случайную выборку схем на 56 кубитах, но со случайными регулярными графами (Q).
Все эксперименты запускали случайные схемы на разных размерах систем и глубинах схем и собирали от тысяч до миллионов образцов из нескольких случайных схем заданного размера.
Для оценки качества образцов широко принятым эталоном является линейная кросс-энтропийная (XEB) оценка, определённая как χ=2n𝔼C𝔼xpC(x)−1,\chi = 2^n \mathbb EC \mathbb E{x} p_C(x) -1.
Для вычисления XEB, учитывая список образцов, вам «просто» нужно вычислить идеальную вероятность получения этого образца из схемы CC и усреднить результаты.
XEB хорош тем, что даёт 1 для идеальных образцов из достаточно случайных схем и 0 для равномерно случайных образцов, и его можно точно оценить по нескольким выборкам.
При правильных условиях оказывается, что это хороший прокси для многочастичной точности квантового состояния, подготовленного непосредственно перед измерением.
Это говорит нам о том, что мы должны ожидать оценку XEB (1−error per gate)# gates ∼ c−nd (1-\text{error per gate})^{\text{\# gates}} \sim c^{- n d } для некоторой константы cc, зависящей от шума и архитектуры.
Все эксперименты достигли значения XEB, которое было значительно (в статистическом смысле) далеко от 0. Это показывает, что в экспериментах происходит нечто нетривиальное.
Сложность моделирования этих экспериментов примерно определяется экспонентой либо от количества кубитов, либо от максимального двудольного запутывания.
Насколько велик выигрыш от XEB, значительно меньшего единицы, для классического спуфера, сказать сложно. Но можно, конечно, использовать его для обоснованного изменения схемы, чтобы упростить её моделирование.
Даже в этом случае воспроизвести низкие оценки от 0,05 % до 0,2 % для экспериментов крайне сложно на классических компьютерах.
Насколько мне известно, получение образцов, соответствующих экспериментальной оценке XEB, удалось только для первого эксперимента 2019 года (PCZ).
Если есть более совершенные методы, компьютеры или больше желания тратить деньги на моделирование случайных схем сегодня, я был бы очень рад услышать об этом!
Прокси-прокси-бенчмарк
Теперь вы можете задаться вопросом: «Как вообще можно вычислить XEB или точность в эксперименте по квантовому преимуществу? Разве для этого не требуется вычисление вероятностей исходов для предположительно сложных квантовых схем?»
И это действительно очень хороший вопрос. Ведь квантовое преимущество случайной выборки схем основано на сложности вычисления этих вероятностей.
Для оценки XEB в режиме преимущества эксперименты должны были использовать прокси и экстраполяцию из классически поддающихся вычислению режимов.
Чтобы экстраполировать, можно просто запустить меньшие схемы увеличивающихся размеров и экстраполировать до размера в режиме преимущества.
В конце концов, утверждения о преимуществе основаны на прокси-прокси квантовой точности. Это не значит, что утверждения о преимуществе не имеют под собой оснований.
В следующем посте я расскажу вам больше о доказательствах того, что эксперименты, которые я описал здесь, действительно демонстрируют квантовое преимущество, и обсужу некоторые скептические аргументы.
Позвольте мне завершить этот первый пост несколькими замечаниями.
Описывая эксперименты по демонстрации квантового превосходства, я сосредоточился на случайной выборке схем, которая выполняется на программируемых цифровых квантовых компьютерах.
Я не стал говорить о бозонной выборке и гауссовской бозонной выборке, которые выполняются на фотонных устройствах и также были экспериментально продемонстрированы.
Причина этого в том, что я считаю, что случайные схемы концептуально чище, поскольку они выполняются на процессорах, которые в принципе способны выполнять произвольные квантовые вычисления, в то время как фотонные устройства, используемые в бозонной выборке, гораздо более ограничены и больше похожи на аналоговые симуляторы.
Пожалуйста, напишите в комментариях, считаете ли вы, что квантовое преимущество было продемонстрировано (этими экспериментами), и если нет, то почему.