Превосходный FAQ о квантовом превосходстве от Скотта Ааронсона

От переводчика. Я совсем не специалист по алгоритмической сложности и квантовым алгоритмам в частности. Но мне пост показался слишком интересным, чтобы не обсудить его на Хабре, а за любые ошибки в терминах или непривычном их использовании прошу пинать меня в личку.

Scott’s Supreme Quantum Supremacy FAQ!

Вы уже видели истории — в Financial Times, Technology Review, CNET, Facebook, Reddit, Twitter, или где-то еще — в которых рассказывается о группе из Google, которая достигла квантового превосходства с 53-кубитным сверхпроводящим компьютером. Эти истории просто найти, я не буду прикреплять их здесь, так как ни одной из них не должно еще было существовать.

Как теперь известно всему миру, Google в самом деле готовит большое заявление о квантовом превосходстве, которое планируется совместно с научной статьей в крутом журнале (каком? выбор невелик — один из двух). Надеюсь, это случится в течение месяца.
Тем временем NASA, где работает часть авторов статьи, ненароком опубликовала старую версию статьи на публичном сайте. Она там находилась совсем недолго, но достаточно долго чтобы оказаться в Financial Times, моей почте и миллионе других мест. Спекуляции без фактов о ее значении ожидаемо множатся.

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

Скорее я хочу остановить поток дезинформации и предложить тут, будучи в роли блоггера и «публичного интеллектуала», свой Scott’s Supreme Quantum Supremacy FAQ. Знаете, на случай если вы вдруг случайно любопытствуете о квантовом превосходстве или всегда хотели знать, что случится, если вдруг какая-нибудь поисковая компания из Маунтин-Вью или еще откуда гипотетически заявит о достижении квантового превосходства.

Без дальнейших церемоний, вот он:

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

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

В2. Если Google в самом деле достиг квантового превосходства, значит ли это, что теперь нет невзламываемого кода, как недавно затвитил кандидат в президенты США от демократов Эндрю Янг?

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

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

Я могу, конечно, вам сказать, но чувствую себя при этом глуповато. Вычисление такое: экспериментатор генерирует случайную квантовую схему С (т.е. Случайную последовательность 1-кубитных и 2-кубитных — между ближайшими соседями — вентилей, с глубиной к примеру в 20, действующую на 2D сеть n=50-60 кубитов). После этого экспериментатор посылает С на квантовый компьютер, и просит его применить С к начальному состоянию из 0, измерить результат в базисе {0,1}, послать обратно n-битную наблюдаемую последовательность (строку) и повторить несколько тысяч или миллионов раз. Наконец, используя свое знание о С, экспериментатор проводит статистическую проверку на соответствие результата с ожидаемым выходом от квантового компьютера.

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

TL;DR, квантовый компьютер просят применить случайную (но известную) последовательность квантовых операций — не потому, что нас интересует результат, а потому что мы пытаемся доказать, что КК может выполнить эту четко поставленную задачу лучше, чем классический компьютер.

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

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

Я все говорю о самолете Райт только потому, что пропасть между тем, о чем мы сейчас говорим, и отрицанием, кое я наблюдаю в разных уголках интернета, совершенно непостижима. Это как если бы вы верили, что летать в принципе невозможно, а потом увидели хлипкий деревянный самолетик — это может быть и не пошатнет вашу веру, но уж точно не должно ее укрепить.
Был ли я прав, беспокоясь много лет назад, что постоянный хайп о гораздо меньших достижения КК утомит людей, и им будет до фени когда что-то действительно стоящее наконец случится? В5. Много лет назад ты попрекал массы за их восторги по поводу D-Wave и их заявлений о потрясающем квантовом преимуществе в проблемах оптимизации с помощью квантового отжига. Теперь ты попрекаешь их же за отсутствие восторгов о квантовом превосходстве. Почему ты так непостоянен?

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

В6. Если вычисления квантового превосходства основываются просто на сэмплах из распределения вероятностей, как можно проверить, что они сделаны верно?

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

Честно говоря, чтобы применить этот тест, вам нужно рассчитать все вероятности Pr[С выдает s_i] на классическом компьютере — и единственный известный способ сделать это это перебор за время ~2ⁿ. Но разве это кого-то смущает? Нет, если n=50, а вы гугл и можете посчитать числа типа 2⁵⁰ (хотя не получится 2¹⁰⁰⁰, которое превосходит гугол, кхе-кхе). Прогнав большой кластер классических ядер на протяжении, скажем, месяца, вы получите в конечном итоге результат, который КК выдал за пару секунд — заодно убедитесь, что КК на пару порядков быстрее. Тем не менее, это значит, что эксперименты, основанные на сэмплировании, практически специально созданы для девайсов с ~50 кубитов. Ибо даже с 100 кубитами мы понятия не имеем как заверить результат даже используя всю вычислительную мощность, доступную на Земле. (Замечу отдельно, что эта проблема специфична только для экспериментов с сэмплированием, по типу того, что проводятся сейчас. Если вы использовали алгоритм Шора для факторизации 2000-значного числа, вы запросто можете проверить результат просто умножив все факторы и проверяя их простоту. Ровно так же если КК используется для симуляции сложной биомолекулы, вы можете проверить результат произведя эксперимент над молекулой.)
В7. Погоди. Если классические компьютеры могут только проверить результаты эксперимента по квантовому превосходству только в режиме, где классические компьютеры все еще могут симулировать эксперимент (пусть и очень медленно), как вообще можно говорить о «квантовом превосходстве»?

Ну ладно вам. С 53-кубитным чипом вы видите ускорение в несколько миллионов раз, и пока все еще можете верифицировать результат, а также проверить что ускорение растет экспоненциально с количеством кубитов, точно как предсказывает асимптотический анализ. Это не незначительно.

B8. Есть ли математическое доказательство того, что никакой быстрый классический компьютер не сможет побить результаты эксперимента по КП, основанного на сэмплировании?

На настоящий момент нет. Но это не вина исследователей квантового превосходства! Покуда теоретики не могут доказать даже базовые гипотезы, типа P?NP или P?PSPACE, а без этого мы не можем безусловно исключить возможность быстрой классической симуляции. Лучшее, на что мы можем надеяться это условная сложность. И у нас есть некоторые результаты про это, например статья про сэмплирование бозонов или статья Bouldand et al. про среднюю #P-сложность расчета амплитуд случайных схем, или моя статья с Lijie Chen(«Complexity-Theoretic Foundations of Quantum Supremacy Experiments»). Самый главный открытый вопрос в этой области на мой взгляд это доказательство лучших условных сложностей. В9. Есть ли какое-то применение у квантового превосходства на основе сэмплирования?

До недавнего времени ответ был очевидно «нет»! (А я знаю, потому что был сам одним из таких людей). Недавно, однако, ситуация изменилась — например, благодаря моему протоколу по сертифицированной случайности, который показывает как КП основанное на сэмплировании может быть независимо использовано для генерации битов, которые могут быть доказанно случайными даже для скептически настроенного третьего лица (при предположениях на вычисления). Это в свою очередь имеет приложение в криптовалюте и других криптографических протоколах. Я надеюсь, что скоро появится больше таких применений. В10. Если эксперименты по квантовому превосходству всего ли генерируют случайные биты, почему это вообще интересно? Разве нельзя тривиально конвертировать кубиты в случайные биты просто измерив их?

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

В11. Разве десятки лет квантовомеханических экспериментов, например, с нарушением неравенства Белла, не продемострировали квантовое превосходство?

Это чисто лексический вопрос. Те эксперименты продемонстрировали другие типы квантового превосходства: например, в случае с неравенством Белла, их можно назвать «квантовым корреляционным превосходством». Они не показали квантового вычислительного превосходства, т.е. возможность посчитать нечто малодоступное классическому компьютеру (где классическая симуляция не имеет никаких ограничений на пространственную локально и т.п.). В настоящее время, когда люди используют фразу «квантовое превосходство», они имеют в виду квантовое вычислительное превосходство.

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

В определениях некоторых людей, они считаются! Главная разница с компьютером гугла в том, что у них полностью программируемый компьютер — вы можете ввести любую произвольную последовательность 2-кубитных вентилей (для соседних кубитов), просто вводя команды с классического компьютера.

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

B13. Это ты (Скотт Ааронсон) изобрел концепцию квантового превосходства?

Нет. Я сыграл некоторую роль в ее разработке, и поэтому, например, Сабина Хозенфельдер в числе других ошибочно приписала мне авторство всей идеи. Термин «квантовое превосходство» был предложен Джоном Прескиллом в 2012, хотя в каком-то смысле основная идея появилась еще на заре квантовых вчислений в начале 80х. В 1994 использование алгоритма Шора для факторизации большого числа стало основным экспериментом для проверки квантового превосходства, хотя на настоящий момент это все еще слишком сложно произвести. Ключевая идея о том, что вместо этого можно использовать сэмплирование была, насколько я знаю, впервые предложена Barbara Terhal и David DiVincenzo, в статье 2002 года. Нынешние усилия по сэмплированному КП начались в районе 2011 года, когда Алекс Архипов и я опубликовали нашу статью по бозонному сэмплированию, а Bremner, Jozsa, и Shepherd независимо опубликовали статью о моделях коммутирующих гамильтонианов. Эти статьи показали не только что «простые», не универсальные квантовые системы могут решить очевидно сложные задачи сэмплирования, но и что существование эффективного классического алгоритма означало бы падение полиномиальной иерархии. Архипов и я также положили начало аргументам о том, что даже приблизительные версии квантового сэмплирования могут быть классически сложными. Насколько я знаю, идея «случайного сэмплирования схем» — то есть, генерации сложной задачи сэмплирования путем выбора случайно последовательности 2-кубитных вентилей в, скажем, сверхпроводящей архитектуре — возникла их переписки, которую я начал в декабре 2015, включавшей John Martinis, Hartmut Neven, Sergio Boixo, Ashley Montanaro, Michael Bremner, Richard Jozsa, Aram Harrow, Greg Kuperberg, и других. Тред был озаглавлен «Сложные проблемы сэмплирования с 40 кубитами», а письмо начиналось с «Прошу прощения за спам». В нем я обсудил разные преимущества и недостатки трех вариантов демонстрации квантового преимущества с помощью сэмплирования: (1) случайные схемы, (2) коммутирующие гамильтонианы, (3) бозонное сэмплирование. После того, как Грег Куперберг вступился за вариант (1), быстро сформировался консенсус, что (1) будет действительно лучшим вариантом с инженерной точки зрения, и что если у нас пока нет удовлетворительного теоретического обоснования для (1), мы можем как-то это обойти.

После этого группа в Google провела большую работу по анализу случайного сэмплирования схем, с теоретической и численной стороны, в то время как Lijie Chen и я и Bouland et al. предоставили разные свидетельства классической сложности этой задачи с точки зрения теории сложности. В14. Если квантовое превосходство достигнуто, что это значит для скептиков?

Ух, не хотел бы я оказаться сейчас на их месте! Они могут, откатиться на позиции, что, мол, ну конечно квантовое превосходство возможно (а кто говорил иначе? ну конечно не они!), а вся сложность всегда была в квантовой коррекции ошибок. И в самом деле, некоторые говорили так с самого начале. А другие, мой добрый друг Gil Kalai в их числе, под запись, прямо в этом блоге, предсказывали, что квантовое превосходство никогда не будет достигнуто по фундаментальным причинам. Теперь они не отвертятся.

В15. И что дальше?

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