Чистую, подтверждаемую случайность тяжело найти. Два новых предложения показывают, как сделать из квантовых компьютеров фабрики случайных чисел.
Скажите на любом собрании специалистов по информатике «квантовое превосходство», и вы, вероятно, увидите, как они закатывают глаза. Эта фраза относится к идее о том, что квантовые компьютеры скоро перейдут рубеж, за которым они станут с относительной лёгкостью выполнять задачи, чрезвычайно сложные для классических компьютеров. И до недавнего времени эти задачи считались малополезными для реального применения – отсюда и закатывание глаз.
Но теперь, когда, как говорят, процессор от Google близок к этой цели, у неизбежного квантового превосходства может появиться важное применение: генерирование чистой случайности.
Случайность важна практически для всего, что происходит в инфраструктуре вычислений и коммуникаций. В частности, её используют для шифрования данных, защищающей всё, от обычных разговоров до финансовых транзакций и государственных секретов.
Настоящую, подтверждаемую случайность – представьте её себе как свойство, имеющееся у последовательности чисел, и делающее невозможным предсказать следующее число в последовательности – чрезвычайно сложно найти.
Но эта ситуация может поменяться, когда квантовые компьютеры продемонстрируют их превосходство. Эти первые задачи, которые изначально просто должны были продемонстрировать превосходство технологии, могут также выдать настоящую сертифицированную случайность. «Мы с радостью приветствуем это, — сказал Джон Мартинис, физик из Калифорнийского университета в Санта-Барбаре, руководящий проектом квантовых вычислений в Google. – Мы надеемся, что это будет первым применением квантового компьютера».
Случайность и энтропия
Случайность и квантовая теория идут рука об руку, как гром и молния. В обоих случаях первое является неизбежным последствием второго. В квантовом мире системы, как часто говорят, находятся в комбинации из нескольких состояний – в т.н. «суперпозиции». Когда вы измеряете систему, она «коллапсирует» в одно из этих состояний. И хотя квантовая теория позволяет вам рассчитать вероятности того, что вы обнаружите при измерении, точный результат всегда будет фундаментально случайным.
Физики изучали эту связь с целью создания генераторов случайных чисел. Все они полагаются на измерения какой-либо квантовой суперпозиции. И хотя для большинства способов генерации случайных чисел, нужных людям, этих систем достаточно, с ними бывает тяжело работать. Кроме того, очень тяжело доказать скептику истинную случайность этих генераторов случайных чисел. Наконец, некоторые из наиболее эффективных методов генерирования подтверждаемой случайности требуют изощрённых конструкций из множества устройств, разделённых огромными расстояниями.
В 2018 году лаборатория ИИ Google представила 72-кубитный квантовый процессор Bristlecone
Одно недавнее предложение по поводу извлечения случайности всего из одного устройства – квантового компьютера – использует т.н. задачу сэмплирования [sampling task], которая будет одной из первых проверок квантового превосходства. Чтобы понять её, представьте, что вам дали коробку с плитками. На каждой плитке написано несколько единичек и несколько нулей — 000, 010, 101 и так далее.
Если битов всего три, то возможных вариантов восемь. Однако в коробке может быть несколько копий каждой плитки. Там может быть 50 плиток с надписью 010 и 25 плиток с надписью 001. Распределение плиток определяет вероятность того, что вы случайно вытащите определённую плитку. В нашем случае вы можете вытащить плитку 010 с вероятностью в два раза большей, чем плитку 001.
Задача сэмплирования включает компьютерный алгоритм, эквивалентный случайному вытаскиванию плитки из коробки с определённым распределением плиток. Чем выше вероятность, определённая для любой плитки в распределении, тем более вероятно, что алгоритм вытащит эту плитку.
Конечно, алгоритм не вытаскивает настоящие плитки из настоящей коробки. Он просто случайно выдаёт двоичное число длиной 50 битов, получив распределение, определяющее желаемую вероятность для каждой из возможных строк длиной 50 битов.
Для классического компьютера сложность этой задачи растёт экспоненциально с увеличением количества битов в строке. Но для квантового компьютера задача, как ожидается, будет оставаться примерно одинаковой, как для 5 битов, так и для 50.
Квантовый компьютер начинает с того, что все его квантовые биты – кубиты – находятся в определённом состоянии. Допустим, все они начинают с 0. Как классические компьютеры могут работать с классическими битами с использованием т.н. логических вентилей, так и квантовые компьютеры манипулируют кубитами с использованием их квантового эквивалента, квантовых вентилей.
Однако квантовые вентили могут помещать кубиты в странные состояния. К примеру, один вид вентилей может поместить кубит, начавший со значения 0, в суперпозицию 0 и 1. Если вы затем измерите состояние кубита, он случайным образом коллапсирует в 0 или 1 с равной вероятностью.
Что ещё более странно, квантовые вентили, способные работать с двумя или более кубитами одновременно, могут привести к тому, что кубиты «запутываются» друг с другом. В данном случае состояния кубитов переплетаются так, что теперь все эти кубиты можно описать при помощи только одного квантового состояния.
Если свести в одно место кучку квантовых вентилей, а потом заставить их работать с набором кубитов в определённой последовательности, это и будет квантовый контур. В нашем случае, чтобы вывести случайную строку из 50 бит, можно построить квантовый контур, помещающий 50 кубитов в суперпозицию состояний, описывающую нужное вам распределение.
При измерении кубитов вся суперпозиция случайным образом коллапсирует в одну 50-битовую строку. Вероятность того, что она схлопнется в какую-то определённую строку, определяется распределением, определённым квантовым контуром. Измерение кубитов похоже на то, как человек с завязанными глазами протягивает руку в мешок и случайно достаёт оттуда одну строку с распределением.
Скотт Ааронсон, специалист по информатике из Техасского университета в Остине
И каким образом всё это связано со случайными числами? Важно, что в 50-битной строке, выбранной квантовым компьютером, будет содержаться много энтропии, меры беспорядка или непредсказуемости, и, следовательно, случайности. «И это, на самом деле, может иметь очень серьёзные последствия, — сказал Скотт Ааронсон, специалист по информатике из Техасского университета в Остине, придумавший новый протокол. – Не потому, что это наиболее важное применение квантовых компьютеров – думаю, это далеко не так – а потому, что это похоже на, возможно, первое применение квантовых компьютеров, которое можно будет реализовать на практике».
Протокол Ааронсона для генерации случайных чисел довольно прост. Классический компьютер сначала собирает несколько случайных битов из некоего доверенного источника, а потом использует это «семя случайности» для генерации описания квантового контура. Случайные биты определяют типа квантовых вентилей и последовательность, в которой они должны воздействовать на кубиты. Классический компьютер отправляет описание квантовому компьютеру, который реализует квантовый контур, измеряет кубиты и отправляет назад 50-битную строку. Таким образом она оказывается выбранной случайным образом из распределения, определённого контуром.
Затем повторите этот процесс несколько раз – допустим, по 10 раз для каждого квантового контура. Классический компьютер использует статистические тесты, чтобы гарантировать, что в выходных строках содержится достаточно много энтропии. Ааронсон показал (частью в опубликованной работе, написанной совместно с Лицзе Чэнь, и частью в работе, которую ещё предстоит опубликовать), что при определённых разумных допущениях о том, что такие задачи являются вычислительно сложными, никакой классический компьютер не в состоянии сгенерировать такую энтропию за время, сравнимое с тем, за которое квантовый компьютер создаст такую случайную выборку из распределения. После проверок классический компьютер собирает все 50-битные строки и скармливает их хорошо известному классическому алгоритму. «Он выдаёт длинную, почти идеально случайную строку», — сказал Ааронсон.
Квантовая ловушка
Протокол Ааронсона лучше всего подходит к квантовым компьютерам с количеством кубитов от 50 до 100. При выходе количества кубитов за эти пределы вычислительная сложность не позволяет использовать этот протокол даже классическим суперкомпьютерам. В таком случае на сцену выходит другая схема генерации проверяемо случайных чисел при помощи квантовых компьютеров. Она использует существующую математическую технику со сложным именем «функция ловушки без клешней» [trapdoor claw-free function]. «Звучит это хуже, чем обстоит дело в реальности», — сказал Умеш Вазирани, специалист по информатике из Калифорнийского университета в Беркли, разработавший новую стратегию, в чём ему помогали Звика Бракерский, Пол Кристиано, Урмила Махадев и Томас Видик.
Представьте нашу коробку. Вместо того, чтобы залезать в неё и вытаскивать строку, мы кидаем в неё строку из n бит, назовём её x, а потом вынимаем другую строку из n бит. Коробка каким-то образом сопоставляет входящую строку и выходящую. Но у неё есть особое свойство: для каждой x существует ещё одна входящая строка y, выдающая точно такую же выходную строку.
Иначе говоря, существуют две уникальных входных строки – x и y – для которых коробка возвращает одну и ту же выходную строку z. Эта тройка, x, y и z, называется клешнёй. Коробка на языке информатики – функция. Эту функцию легко вычислить, то есть, для любых x и y легко подсчитать z. Но если взять только x и z, то найти y – и всю клешню – невозможно даже для квантового компьютера.
Урмила Махадев, Умеш Вазирани и Томас Видик
Единственный способ получить всю клешню – найти некую дополнительную информацию, т.н. ловушку.
Вазирани с коллегами хотят использовать такие функции, чтобы не только заставить квантовые компьютеры генерировать случайные числа, но и проверять, что квантовые компьютеры на самом деле работают по квантовым законам – что необходимо для построения доверия случайным последовательностям.
Протокол начинается с того, что квантовый компьютер помещает n кубитов в суперпозицию всех n-битных строк. Затем классический компьютер отправляет описание квантового контура, определяя функцию, которую нужно применить к суперпозиции — функцию ловушки без клешней. Квантовый компьютер реализует контур, не зная ничего о ловушке.
На этом этапе квантовый компьютер входит в состояние, в котором один набор его кубитов находится в суперпозиции всех n-битных строк, а другой содержит результат применения функции к этой суперпозиции. Два набора кубитов запутаны друг с другом.
Квантовый компьютер, измеряющий второй набор кубитов, случайным образом схлопывает суперпозицию в некий результат z. Первый же набор кубитов схлопывается в аналогичную суперпозицию из двух n-битных строк, x и y, поскольку любая из них может служить входом для функции, выдающей z.
Классический компьютер получает выходное значение z, а потом делает одно из двух действий. В большинстве случаев он просит квантовый компьютер измерить оставшиеся кубиты. Это схлопывает суперпозицию в x или в y, с 50% вероятностью. Это эквивалентно случайному получению 0 или 1.
Иногда, чтобы проверить квантовый компьютер на квантовость, классический компьютер просит провести особое измерение. Измерение и его результат разработаны так, чтобы классический компьютер при помощи ловушки, доступ к которой есть только у него, мог гарантировать, что устройство, отвечающее на его запросы, действительно квантовое. Вазирани с коллегами показали, что если устройство даст правильный ответ на особое измерение, не используя коллапс кубитов, это будет эквивалентно тому, что он найдёт клешню без ловушки. А это невозможно. Поэтому в устройстве должен происходить коллапс хотя бы одного кубита (дающий 0 или 1 случайным образом). «Протокол создаёт проверенный кубит внутри квантового компьютера, которому мы не доверяем», — сказал Вазирани.
Этот проверенный кубит даёт один истинно случайный бит информации при каждом опросе; последовательность таких запросов можно использовать для создания длинных случайных строк.
Эта схема, возможно, будет работать быстрее, чем протокол Ааронсона, но у неё есть явный недостаток. «С количеством кубитов равным 50 или 70 она не будет практичной», — сказал Ааронсон.
Ааронсон пока ждёт появления системы от Google. «Окажется ли качество того, что они нам покажут, достаточным для того, чтобы реально достичь квантового превосходства – это ещё большой вопрос», — сказал он.
Если у компании всё получится, то гарантированная квантовая случайность уже у нас на пороге. «Мы думаем, что это будет полезный и многообещающий рынок, и это то, что мы хотели бы предложить людям», — сказал Мартинис.
