Как превратить квантовый компьютер в идеальный генератор случайных чисел

Автор оригинала: Anil Ananthaswamy
  • Перевод

Чистую, подтверждаемую случайность тяжело найти. Два новых предложения показывают, как сделать из квантовых компьютеров фабрики случайных чисел.




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

Но теперь, когда, как говорят, процессор от 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. «Окажется ли качество того, что они нам покажут, достаточным для того, чтобы реально достичь квантового превосходства – это ещё большой вопрос», — сказал он.

Если у компании всё получится, то гарантированная квантовая случайность уже у нас на пороге. «Мы думаем, что это будет полезный и многообещающий рынок, и это то, что мы хотели бы предложить людям», — сказал Мартинис.
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 14

    0

    Несложно написать простейшую программу, которая проверяет системный random, собственно что я когда-то и сделал. Чем больше запусков, тем ближе количество решек к количеству орлов. Но если к примеру взять не только количество комбинаций из одного символа, но и из нескольких, то есть:
    Однобуквенные:
    1) а
    2) б
    Двубуквенные:
    1) аа
    2) аб
    3) ба
    4) бб
    И так далее, то по каждой из таких категорий у меня получилось верно следующее:
    пусть для n-буквенной категории А — количество выпавших аааа… аааа (всего n букв), а С — среднее количество выпадений каждой из 2^n комбинаций. Тогда чем выше количество запусков, тем меньше по модулю (A — C) / C, но тем выше A — C само по себе. Иначе говоря, точность увеличивается вовсе нелинейно, а куда медленнее. И это конечно грустно, что сейчас ваш смартфон и компьютер неспособен давать более менее случайные числа.
    Быть может, квантовый компьютер не только сможет это делать более "рандомно", но и личные компьютеры смогут скачивать следующую случайную последовательность с некоторого централизованного сервера.

      0
      Системный рандом, как ты его проверял можно поподробнее? dev/random читал?
        0

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

          0
          Как именно ты обращался к системному рандому? dev/random?
        +1
        истинный рандом — это непредсказуемость __следующего__ результата.
        Если в ваш алгоритм вбить «aa,ab,ba,bb,aa,ab,ba,bb,...» — ваша проверка даст ответ — случайный, хотя совершенно не случайный
          0
          И это конечно грустно, что сейчас ваш смартфон и компьютер неспособен давать более менее случайные числа.

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

          Собственно, всё симметричное шифрование на этом построено — есть ключ (который используется для получения начального состояния), есть меняющееся состояние, есть генератор псевдослучайных байт которые xor'ятся с открытым текстом — и многие из нормальных алгоритмов даже квантовым компутерам будут не по зубам (например, AES-256), по крайней мере в более-менее обозримом (и даже слегка необозримом) будущем.

            0
            В вычислительной физике есть квантовый метод Монте Карло. Известны случаи, когда он выдавал неправильные ответы из-за недостаточно качественного генератора (псевдо)случайных чисел. Статистический анализ — вещь неисчерпаемая. :)
          0
          Интересно. Как я понял механизм следующий.
          Задается одна часть клешни в виде n-битного числа, в которой мы знаем какая позиция относится к «зубу/выемки», так как клешня должна цеплять. Например
          х = 10000010001
          И алгоритм, для квантового компьютера, который в суперпозицию ставит другую часть клешни:
          у = 10000000001
          После того как приходит запрос на получение Z, то исходные части клешни свертываются до одной из частей. И мы эту часть можем получить.
          И определяя какое значение стоит на позиции «зуб/выемка» определяем случайное число.
          Тогда высказывание:
          «С количеством кубитов равным 50 или 70 она не будет практичной», — сказал Ааронсон

          Можно интерпретировать, что у них нет рабочего алгоритма по которому определяется номер позиции «зуб/выемка» для количества кубитов более 50.
          Вот это уже интересно почему
            0
            У нас попроще делают квантовые датчики
              0
              Я так понял, задача в том, как строго доказать, что на выходе именно квантовая случайность при условии, что квантовый ДСЧ или ГСЧ на КК для нас «черный ящик»
                0
                Предполагаю не это они хотят определить. Числа сопряженные на клешнях могут, на той позиции, которую они взяли за базу иметь одинаковые значения. И когда они обратно, через энтропию прогоняют, то пытаются отследить были ли разные значения на этой позиции.
                  0
                  Как одно другому противоречит?
                    0
                    В принципе не противоречит. Просто Ваш аспект глобальней
              0
              Квантовые генераторы случайных чисел уже используются в квантовой криптографии.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое