Из блога Скотта Джоэла Аронсона, специалиста в области теории вычислительных машин и систем, преподавателя факультета компьютерных наук Техасского университета в Остине

Вы читали эти истории – в Financial Times, Technology Review, CNET, Facebook, Reddit, Twitter, [на Хабре / прим. перев.] или где-то ещё – о том, что группа исследователей в Google достигла квантового вычислительного превосходства со своим сверхпроводящим устройством из 53 кубитов. Их легко найти, но ссылок на них я давать не буду – просто потому, что они пока не должны существовать.

Миру известно, что Google действительно готовит большой анонс квантового превосходства, который должен выйти одновременно с публикацией исследовательской работы в одном из уважаемых научных журналов. И это, скорее всего, произойдёт в течение месяца.

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

Судя по всему, у нашего мира отняли возможность чётко объявить о новом моменте «выхода человека в космос», в котором в рамках пресс-конференции будет экспериментально опровергнут сильный тезис Чёрча — Тьюринга. Это больше будет похоже на полёт братьев Райт, отрывочные слухи о котором всплывали в промежутке начиная с 1903 и заканчивая 1908 годом, в котором Уилбур и Орвилл, наконец, согласились на демонстрационные полёты (только в нашем случае, к счастью, на разъяснение вопроса уйдёт куда как меньше времени!)

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

Эта запись – официальный анонс, подтверждающий данные факты. И если молния уже видна нам, то право озвучить гром принадлежит группе исследователей из Google, как и время и место для этого.

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

Ну, не будем тянуть кота за хвост:

Вопрос 1: что такое квантовое вычислительное превосходство?

Этот термин часто сокращают просто до квантового превосходства (КП). Он обозначает использование квантового компьютера (КК) для решения некоего чётко определённого набора задач, решение которых при помощи известных сегодня алгоритмов на существующих сегодня классических компьютеров займёт на порядки больше времени – и не просто так, а по причине асимптотической квантовой сложности. Упор здесь делается на то, чтобы быть на 100% уверенным в том, что задача решается на КК, и к ней реально нельзя подступиться при помощи классических компьютеров; в идеале, задача должна быть такой, чтобы её уже можно было решить в ближайшее время (при помощи зашумлённых, не универсальных КК, которые уже есть или появятся в скором времени). А если ещё эта задача окажется полезной, тем лучше – но это не обязательно. Самолёт братьев Райт или чикагская поленница сами по себе не были полезными.

В2: Если исследователи из Google и правда достигли КВ, значит ли это, что «любой код можно взломать», как недавно написал у себя в твиттере кандидат в президенты от демократической партии США Эндрю Янг?



Неправда (хотя как кандидат, Янг мне симпатичен).

Тут есть две проблемы. Во-первых, устройства, которые сегодня создают Google, IBM и другие, состоят из 50-100 кубитов и не имеют системы исправления ошибок. Для запуска алгоритма Шора для взлома RSA-шифрования потребуется несколько тысяч логических кубитов. А с известными на сегодня методами коррекции ошибок это легко может потребовать миллионов физических кубитов, причём качеством лучше существующих. Не думаю, что кто-либо приблизился к этому, и мы не знаем, сколько времени уйдёт на это.

Во-вторых, даже в гипотетическом будущем, масштабируемые КК с коррекцией ошибок смогут, как нам сегодня кажется, взламывать некоторые коды, но не все. По неудачному совпадению, к тем публичным ключам, что они способны взломать, относятся большая часть ключей, используемых нами сегодня для безопасности в интернете: RSA, протокол Диффи — Хеллмана, эллиптические кривые, и т.д. На шифрование с приватным ключом это окажет минимальное влияние. А ещё есть кандидаты на системы с открытыми ключами (к примеру, на основе решёток), способ взлома которых и за 20 лет попыток на КК никому не известен; кроме того, уже предпринимаются попытки по переходу на такие системы. Подробности – в моём письме к Ребекке Гольдштейн.

В3: Какие вычисления, считающиеся классически сложными, Google планирует проводить, или уже провёл?

Могу сказать, хотя и стесняюсь. Вычисления следующие: «испытатель» генерирует случайный квантовый контур С (случайную последовательность вентилей из 1 кубита и ближайшего к нему второго кубита, глубины около 20, на двумерной решётке из 50-60 кубитов). Затем испытатель отправляет C в квантовый компьютер и даёт ему задание применить контур к изначальному состоянию все-0, измерить результат по базе {0,1}, отправить наблюдаемую строку из n бит, и повторить это несколько тысяч или миллионов раз. Наконец, используя своё знание С, классический испытатель применяет статистический тест, чтобы проверить, что выходные данные подтверждают, что вычисления проводил КК.

То есть, то не задача вроде разложения на множители, имеющая один правильный ответ. Контур С выдаёт распределение вероятности, назовём его D_C, по строкам из n бит, а задача состоит в выдаче выборок из этого распределения. На самом деле, в поддержку D_C будет говорить 2 ⁿ строк — и их будет так много, что если КК работает, как надо, то одни и те же выходные данные мы никогда не увидим. Важно то, что распределение D_C неоднородно. Некоторые строки будут испытывать конструктивную интерференцию амплитуд, и их вероятности будут больше, а другие будут страдать от деструктивной интерференции, и их вероятности будут меньше. И хотя мы увидим лишь несколько выборок, количество которых по сравнению с 2 ⁿ будет крохотным, мы можем проверить, тяготеют ли они к строкам, вероятность которых мы считаем большей, и в итоге это будет повышать нашу уверенность в том, что происходит нечто классически недостижимое.

Проще говоря, КК просто попросят выполнить случайную (но известную) последовательность операций – не потому, что нам нужен конкретный результат, а потому, что мы пытаемся доказать, что он может опередить классический компьютер в некоей чётко определённой задаче.

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

Нет. Как я уже писал, это не бутерброд со всем сразу, но определённо бутерброд с чем-то!

Отнеситесь с уважением к необъятности обсуждаемой темы, и к ужасно сложным инженерным достижениям, необходимым для её реализации. До наступления КП скептики могут вовсю веселиться вместе над тем, что после всех потраченных миллиардов за 20 с лишним лет ни один КК ни разу не использовали для решения задачи, с которой он справился бы быстрее вашего ноутбука, или, по крайней мере, задача не решалась способом, зависящим от квантовости этого компьютера. Но в мире наступившего КП это уже неверно. Суперпозицию из 2⁵⁰ или 2⁶⁰ комплексных чисел осилили вычислительно, причём используя время и ресурсы, крохотные по сравнению с 2⁵⁰ или 2⁶⁰.

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

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

В5: Много лет назад вы стыдили народные массы за то, что они чрезмерно превозносят D-Wave и её заявления по поводу огромного квантового ускорения решения задач оптимизации через квантовый отжиг. Теперь вы стыдите народные массы за то, что они недостаточно сильно восторгаются КП. Почему бы вам не определиться?

Потому что моя цель – не вести «уровень восторженности» в каком-то определённом направлении, а в том, чтобы он был правильным! Разве нельзя сказать, оглядываясь назад, что я в целом был прав по поводу D-Wave, даже когда моя критика этой темы сделала меня непопулярным в некоторых кругах? Вот и по поводу КП я тоже стараюсь оказаться правым.

В6: Если расчёты, связанные с КП, учитывают только выборки из вероятностного распределения, как проверить, что расчёты верны?

Хорошо, что вы спросили! Это вопрос теории, которую мы с другими учёными разрабатываем последнее десятилетие. Я уже объяснил её вкратце в В3: расчёты можно проверить статистически по выборкам, возвращаемым КК, и убедиться, что они предпочитают складываться в «пики» вероятностного распределения D_C. Один из удобных способов сделать это Google называет «линейной проверкой перекрёстной энтропии»: это суммировать Pr[C выход s_i] по всем выборкам s₁,.., s_k, которые выдаёт КК, а потом объявить проверкеу успешной, если эта сумма выходит за некоторую границу – допустим, bk/2ⁿ для постоянной 1 < b < 2.

Конечно, для проведения этого испытания нужно подсчитать вероятности Pr[C выход s_i] на классическом компьютере – и единственным способом это сделать будет полный перебор, занимающий 2 ⁿ времени. Есть ли в этом проблема? Нет, если n=50, а вы – Google, и можете обрабатывать такие числа, как 2⁵⁰ (хотя и не справитесь с 2¹⁰⁰⁰, числом, превышающим гугол – ха, ха). Запустив кластер классических ядер где-нибудь на месяц, в итоге у вас получится подтвердить правильность выхода вашего КК, который он выдал за пару секунд – и заодно что КК работает на много порядков быстрее. Однако это также означает, что эксперименты с КП на основе выборок разработаны для устройств с 50 кубитами, которые создают сегодня. А уже с сотней кубитов мы бы не смогли подтвердить результаты работы КК, даже задействовав все вычислительные мощности планеты.

Подчеркну, что эта проблема характерна для экспериментов с выборками, похожих на тот, что мы проводим сейчас. Если бы алгоритм Шора разложил на множители число из 2000 цифр, мы бы легко проверили это, просто перемножив полученные множители и проверив их на принадлежность к простым числам. Или, если бы КК использовался для симуляции сложной биомолекулы, мы бы могли проверить его работу в эксперименте.

В7: Погодите-ка. Если классические компьютеры могут проверить результаты эксперимента по КП только в режиме симуляции эксперимента (пусть и медленной), то как это может быть «квантовым превосходством»?

Да ладно вам. С чипом из 53 кубитов вполне логично ожидать ускорения в несколько миллионов раз в режиме, в котором вы всё ещё можете напрямую проверить результат работы, а также увидеть, что ускорение растёт экспоненциально при росте количества кубитов – точно так, как предсказывал асимптотический анализ.

В8: Есть ли математическое доказательство того, что не существует быстрого классического алгоритма, который бы перегнал эксперимент по КП с выборкой?

На сегодня нет. Но в этом нет вины исследователей КП! Специалисты по теоретической информатике неспособны даже доказать простейшие гипотезы, типа P?NP или P?PSPACE, поэтому не стоит и надеяться на то, что можно будет однозначно исключить наличие быстрой классической симуляции. Мы можем надеяться только на условную сложность. И мы действительно доказали какие-то из подобных результатов. Самая крупная теоретическая проблема в этой области – доказательство лучших результатов условной сложности.

В9: Имеет ли КП с выборкой само по себе какие-то полезные применения?

Впервые задумавшись об этой теме, люди обычно считали, что очевидный ответ на этот вопрос – «нет» (и я был одним из них). Но в последнее время ситуация поменялась – к примеру, благодаря моему протоколу подтверждённой случайности, который демонстрирует, как эксперимент с КП с выборкой можно очень быстро превратить в генератор битов, случайность которых можно доказать скептически настроенному стороннему наблюдателю (при некоторых вычислительных предположениях). А это может, потенциально, применяться к созданию PoS-криптовалют и других криптографических протоколов. Надеюсь, что в недалёком будущем будет открыто больше подобных применений.

В10: Если эксперименты с КП просто генерируют случайные биты, так ли это интересно? Разве это не тривиальная задача – превратить кубиты в случайные биты, просто измеряя их?

Суть в том, что эксперимент с КП не генерирует однородные случайные биты. Он делает выборку из некоей сложнго коррелирующего распределения вероятности по 50-битным или 60-битным строкам. В моём протоколе подтверждённой случайности отклонения от однородности играют центральную роль в том, как КП может убедить классического скептика в том, что биты в самом деле случайны, и не имеют тайной системы (как генератор псевдослучайных чисел).

В11: А разве десятилетия квантовомеханических экспериментов – к примеру тех, что нарушают неравенства Белла – уже не продемонстрировали КП?

Это просто путаница в терминах. Те эксперименты продемонстрировали другие виды «квантового превосходства». К примеру, в случае нарушения неравенств Белла это было «квантово-корреляционное превосходство». Там не было показано вычислительного превосходства, то есть чего-то, что невозможно симулировать на классическом компьютере (при том, что у классической симуляции не было бы ограничений по пространственной локальности или чего-то подобного). Сегодня люди обычно имеют в виду под КП квантовое вычислительное превосходство.

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

По некоторым определениям они могут считаться примерами КП! Ключевое отличие работы исследователей из Google в том, что их устройство полностью программируемое – его можно запрограммировать на произвольную последовательность 2-кубитных вентилей с ближайшим соседом, просто отправляя нужные сигналы с квантового компьютера.

Иначе говоря, КП-скептики уже не могут хмыкать, что, дескать если и существуют квантовые системы, которые сложно симулировать классически, то только потому, что природу тяжело симулировать, и мы не можем произвольным образом изменить то, какое случайное химическое соединение мы найдём в природе, поэтому эти системы нельзя считать «компьютерами, симулирующими самих себя». По любому разумному определению, сверхпроводящие устройства, которые сегодня создают в Google, IBM и других компаниях, являются настоящими компьютерами.

В13: Изобрели ли вы концепцию квантового превосходства?

Нет. Я сыграл некую роль в его определении, из-за чего Сабина Хоссенфелдер и другие приписали мне слишком большую роль в этой идее. Термин «квантовое превосходства» придумал Джон Прескилл в 2012 году, хотя в некоторым смысле ключевая концепция датируется началом самих квантовых вычислений в начале 1980-х. В 1994 году использование алгоритма Шора для разложения на множители больших чисел стала по-настоящему экспериментом в области КП – хотя эту задачу и сегодня слишком сложно решить.

Суть идеи, заключавшейся в том, чтобы вместо этого продемонстрировать КП при помощи задачи выборки, насколько мне известно, впервые предложили Барбара Терал и Дэвид Дивинченцо в дальновидной работе 2002 года. «Современные» попытки организации экспериментов начались в 2011 году, когда мы с Алексом Архиповым опубликовали нашу работу по BosonSampling, а Бремнер, Йоза и Шеперд опубликовали свою работу по коммутируемым гамильтонианам. Эти работы показали не только, что «простые», не универсальные квантовые системы могут решать кажущиеся сложными задачи с выборкой, но и что эффективный классический алгоритм для этих задач приведёт к коллапсу полиномиальной иерархии. Мы с Архиповым также сделали первые шаги к доказательству того, что даже приблизительные версии задач с квантовой выборкой могут быть сложными классически.

Насколько мне известно, идея «случайной выборки контуров» – то есть, генерации сложной проблемы выборок через выбор случайных последовательностей вентилей из 2 кубитов в сверхпроводящей архитектуре – появилась в емейл-переписке, которую я начал в декабре 2015 года, и в которой также участвовали Джон Мартинис, Хартмут Нивен, Серджио Бойксо, Эшли Монтанаро, Майкл Бремнер, Ричард Йоза, Арам Хэрроу, Грег Куперберг и др. Переписка называлась «сложная проблема выборки с 40 кубитами», и моё письмо начиналось словами «извините за спам». Я обсудил некоторые преимущества и недостатки трёх вариантов демонстрации КП с выборкой: (1) случайные контуры, (2) коммутируемые гамильтонианы, (3) BosonSampling. После того, как Куперберг встал на защиту первого варианта, среди участников быстро сформировался консенсус, что первый вариант действительно был лучшим с инженерной точки зрения – и что, если существующего теоретического анализа для (1) недостаточно, то мы сможем что-нибудь придумать.

После этого группа из Google провела огромное количество анализов выборок случайных контуров, как теоретических, так и численных, а мы с Лицзе Чэнем, а также Буланд с коллегами представляли доказательства различного вида для классической сложности задачи.

В14: Если КП достигнуто, что это будет означать для скептиков?

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

В15: Что дальше?

Достижение КП означает, что у группы Google уже есть оборудование, необходимое для демонстрации моего протокола генерации подтверждённых случайных битов. И это действительно одна из первых вещей, которые мы планируем сделать.

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

После публикации статьи Стив Гирвин напомнил мне, что группа из Йеля уже достигла квантовой коррекции ошибок, хотя и в бозонной системе, а не в системе сверхпрвоодящих кубитов. Так что, возможно, следующую веху лучше сформулировать так: достижение квантового вычислительного превосходства и полезной квантовой коррекции ошибок в одной системе.