От переводчика. Я совсем не специалист по алгоритмической сложности и квантовым алгоритмам в частности. Но мне пост показался слишком интересным, чтобы не обсудить его на Хабре, а за любые ошибки в терминах или непривычном их использовании прошу пинать меня в личку.
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-битную наблюдаемую последовательность (строку) и повторить несколько тысяч или миллионов раз. Наконец, используя свое знание о С, экспериментатор проводит статистическую проверку на соответствие результата с ожидаемым выходом от квантового компьютера.
Это задача не из разряда задач с единственно верным ответом, в отличие от факторизации чисел. Результат работы схемы С оказывает статистическим распределением (назовем его DC) по n-битным строкам, из которого нужно выбрать сэмплы. На самом деле, обычно DC может соответствовать 2n строк — настолько много, что если КК работает как ожидается, он никогда не выдаст одну и ту же строку на выходе дважды. Важно, что распределение DC не является равномерным. Некоторые строки возникли в результате конструктивной интерференции амплитуд и потому имеют большую вероятность, а другие — в результате деструктивной, и имеют меньшую вероятность. И хотя мы получаем только малую часть из всех возможных 2n сэмплов, мы можем проверить распределение этих сэмплов статистически на соответствие ожидаемому неравномерному распределению, и убедиться, что мы получили нечто с трудом воспроизводимое классически.
TL;DR, квантовый компьютер просят применить случайную (но известную) последовательность квантовых операций — не потому, что нас интересует результат, а потому что мы пытаемся доказать, что КК может выполнить эту четко поставленную задачу лучше, чем классический компьютер.
В4. Но если квантовый компьютер просто выполняет какой-то мусорный код, чья единственное предназначение быть сложным для классической симуляции, кому до этого дело? Разве это не большой перехайпенный пирожок с… ничем?
Нет. Это, конечно, не пирожок со всем вкусным, но по крайней мере пирожок с чем-то.
Имейте хоть капельку уважения к необъятности того, о чем мы тут говорим, и какой инженерный гений потребовался, чтобы воплотить это в реальность. До квантового превосходства (КП) КП-скептики просто посмеивались, что все даже после миллиардов долларов и 20+ лет работы квантовой компьютер все еще не может сделать чего-то быстрее, чем ваш ноутбук. По крайней мере не используя квантовость. В мире после достижения квантового превосходства, они больше не посмеются. Суперпозиция 250 или 260 комплексных чисел была посчитана, используя значительно меньший ресурс времени и объема данных, нежели 250 или 260
Я все говорю о самолете Райт только потому, что пропасть между тем, о чем мы сейчас говорим, и отрицанием, кое я наблюдаю в разных уголках интернета, совершенно непостижима. Это как если бы вы верили, что летать в принципе невозможно, а потом увидели хлипкий деревянный самолетик — это может быть и не пошатнет вашу веру, но уж точно не должно ее укрепить.
Был ли я прав, беспокоясь много лет назад, что постоянный хайп о гораздо меньших достижения КК утомит людей, и им будет до фени когда что-то действительно стоящее наконец случится?
В5. Много лет назад ты попрекал массы за их восторги по поводу D-Wave и их заявлений о потрясающем квантовом преимуществе в проблемах оптимизации с помощью квантового отжига. Теперь ты попрекаешь их же за отсутствие восторгов о квантовом превосходства. Почему ты так непостоянен?
Потому что моя цель не смещать уровень восторга в однозначно выбранном направлении, а быть правым. Задним числом, разве не был я прав в основном о D-Wave, даже когда мои заявления сделали меня очень непопулярным в некоторых кругах? Ну вот, а теперь я пытаюсь быть правым о квантовом превосходстве тоже.
В6. Если вычисления квантового превосходства основываются просто на сэмплах из распределения вероятностей, как можно проверить, что они сделаны верно?
Спасибо, что спросили! Это как раз тема, по которой я и другие разработали много теоретических оснований в последний десяток лет. Я уже рассказал короткую версию в моем ответе В3: вы проверяете это прогоняя статистические тесты на сэмплах, которые выдает квантовый компьютер, чтобы проверить, что они концентрируются вокруг пиков хаотического распределения вероятности DC. Один удобный способ делать это, который Google называет «линейный кросс-энтропийный тест», это просто суммировать все Pr[С выдает si] по всем сэмплам s1,…,sk, которые вернул КК, а потом объявить тест успешным, если и только если сумма превосходит некоторый уровень — скажем, bk/2n, где b — константа между 1 и 2.
Честно говоря, чтобы применить этот тест, вам нужно рассчитать все вероятности Pr[С выдает si] на классическом компьютере — и единственный известный способ сделать это это перебор за время ~2n. Но разве это кого-то смущает? Нет, если n=50, а вы гугл и можете посчитать числа типа 250 (хотя не получится 21000, которое превосходит гугол, кхе-кхе). Прогнав большой кластер классических ядер на протяжении, скажем, месяца, вы получите в конечном итоге результат, который КК выдал за пару секунд — заодно убедитесь, что КК на пару порядков быстрее. Тем не менее, это значит, что эксперименты, основанный на сэмплировании, практически специально созданы для девайсов с ~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. Это ты (Скотт Ааронсон) изобрел концепцию квантового превосходства?
The key idea of instead demonstrating quantum supremacy using a sampling problem was, as far as I know, first suggested by Barbara Terhal and David DiVincenzo, in a farsighted paper from 2002. The «modern» push for sampling-based supremacy experiments started around 2011, when Alex Arkhipov and I published our paper on BosonSampling, and (independently of us) Bremner, Jozsa, and Shepherd published their paper on the commuting Hamiltonians model. These papers showed, not only that «simple,» non-universal quantum systems can solve apparently-hard sampling problems, but also that an efficient classical algorithm for the same sampling problems would imply a collapse of the polynomial hierarchy. Arkhipov and I also made a start toward arguing that even the approximate versions of quantum sampling problems can be classically hard.
As far as I know, the idea of «Random Circuit Sampling»—that is, generating your hard sampling problem by just picking a random sequence of 2-qubit gates in (say) a superconducting architecture—originated in an email thread that I started in December 2015, which also included John Martinis, Hartmut Neven, Sergio Boixo, Ashley Montanaro, Michael Bremner, Richard Jozsa, Aram Harrow, Greg Kuperberg, and others. The thread was entitled «Hard sampling problems with 40 qubits,» and my email began «Sorry for the spam.» I then discussed some advantages and disadvantages of three options for demonstrating sampling-based quantum supremacy: (1) random circuits, (2) commuting Hamiltonians, and (3) BosonSampling. After Greg Kuperberg chimed in to support option (1), a consensus quickly formed among the participants that (1) was indeed the best option from an engineering standpoint—and that, if the theoretical analysis wasn’t yet satisfactory for (1), then that was something we could remedy.
After that, the Google group did a huge amount of analysis of random circuit sampling, both theoretical and numerical, while Lijie Chen and I and Bouland et al. supplied different forms of complexity-theoretic evidence for the problem’s classical hardness.
В14. Если квантовое превосходство достигнуто, что это значит для скептиков?
Ух, не хотел бы я оказаться сейчас на их месте! Они могут, откатиться на позиции, что, мол, ну конечно квантовое превосходство возможно (а кто говорил иначе? ну конечно не они!), а вся сложность всегда была в квантовой коррекции ошибок. И в самом деле, некоторые говорили так с самого начале. А другие, мой добрый друг Gil Kalai в их числе, под запись, прямо в этом блоге, предсказывали, что квантовое превосходство никогда не будет достигнуто по фундаментальным причинам. Теперь они не отвертятся.
В15. И что дальше?
Если это действительно достигнутое квантовое превосходство, то, я думаю, группа Google имеет все железо для демонстрации моего протокола по сертифицированной генерации случайных битов. И это на самом деле одна из следующих вещей в их плане.
А помимо этого, следующий очевидный шаг это использовать программируемый КК, с 50-100 кубитами для какой-то полезной квантовой симуляции (например, системы с конденсированным состоянием вещества) гораздо быстрее, чем любой классический метод. А второй очевидный шаг это демонстрация использования коррекции ошибок, чтобы продержать логический кубит в живых дольше, чем время жизни физических кубитов, на которых он основан. Нет сомнений, что IBM, Google и остальные игроки будут гнаться друг с другом за первенство в этих шагах.
Источник
