Йэн Стюарт – Это база: Зачем нужна математика в повседневной жизни (страница 26)

Первой реакцией на заявления D-Wave было недоверие. Архитектура устройства была необычной, и у некоторых возникли вопросы: действительно ли это настоящий квантовый компьютер, а не навороченный классический компьютер, использующий околоквантовое оборудование. Во время испытаний он превосходил стандартные классические компьютеры на полезных задачах, но при этом был специально сконструирован для таких задач, тогда как классические компьютеры, с которыми он состязался, – нет. Его преимущества, казалось, исчезали, если классические компьютеры специально конструировались для соответствующих задач. Споры продолжаются до сих пор, но машины D-Wave используются и неплохо работают.

Ключевой целью исследований является квантовое превосходство: создание квантового устройства, которое превосходит по производительности лучшие классические компьютеры по крайней мере на одном расчете. В 2019 году команда Google AI опубликовала статью в Nature под заголовком «Квантовое превосходство с использованием программируемого сверхпроводящего процессора»{45}. Она объявила, что создала квантовый процессор под названием Sycamore с 54 кубитами, но один из них отказал, что снизило их количество до 53. С его помощью за 200 секунд решили задачу, на решение которой у классического компьютера ушло бы 10 000 лет.

Архитектура квантового процессора Sycamore

Это заявление сразу же было поставлено под сомнение по двум причинам. С одной стороны, этот расчет предположительно мог быть выполнен классической машиной за более короткое время. С другой, Sycamore решал довольно надуманную задачу: получение выборки выходных последовательностей псевдослучайной квантовой схемы. Устройство соединяет компоненты схемы случайным образом, а цель всего этого – рассчитать распределение вероятностей выборки возможных выходных последовательностей. Одни выходные последовательности оказываются гораздо более вероятными, чем другие, так что это распределение получается очень сложным и неоднородным. Время классического расчета с ростом числа кубитов увеличивается экспоненциально. Тем не менее команде ученых удалось достичь своей главной цели: показать, что не существует практических препятствий для создания квантового компьютера, способного превзойти классический в чем-нибудь.

Сразу возникает вопрос: как удостовериться в том, что ответ верен? Ведь невозможно ждать 10 000 лет, пока классический компьютер решит задачу, и нельзя просто верить результату без всякой проверки. Исследователи справились с этой проблемой при помощи метода, известного как сравнительный анализ с перекрестной энтропией. Он предполагает сравнение вероятностей конкретных битовых строк с теоретическими вероятностями, рассчитанными на классическом компьютере. Это позволяет оценить, насколько велика вероятность того, что полученный результат верен. Исследователи пришли к выводу, что результат точен с погрешностью до 0,2 % с очень высокой («пять сигм») вероятностью.

Несмотря на прогресс, большинство экспертов уверены, что до практической реализации идеи квантового компьютера нам еще далеко. Некоторые сомневаются даже, что его вообще можно создать. Физик Михаил Дьяконов написал:

Число непрерывных параметров, описывающих состояние столь полезного квантового компьютера в любой момент, должно быть… около 10³⁰⁰. ‹…› Можем ли мы когда-нибудь научиться контролировать эти более чем 10³⁰⁰ непрерывно меняющихся параметров, определяющих квантовое состояние такой системы? Мой ответ прост. Нет, никогда.

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

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

Теоретически неминуемое наступление квантовых компьютеров породило волну исследований, нацеленных на создание методов шифрования, которые не могут быть взломаны квантовым компьютером. Не так давно Национальный институт стандартов и технологии США запустил программу постквантовой криптографии с целью идентификации классических криптосистем, находящихся в зоне риска, и поиска новых способов борьбы с их уязвимостями. В 2003 году Джон Прус и Кристоф Залка{46} оценили уязвимость системы RSA и криптографии на основе эллиптических кривых для квантового компьютера, работающего по алгоритму Шора. В 2017 году Мартин Реттелер с коллегами{47} дополнил их результаты. Исследователи доказали, что в случае эллиптической кривой над конечным полем с q элементами, где q примерно равно 2ⁿ, RSA уязвима для квантового компьютера с числом кубитов 9n + 2 log₂n +10 и схемы из не более чем 448n³ log₂n +4090n³ вентилей Тоффоли. Вентиль Тоффоли – особый тип логической схемы. Из вентилей Тоффоли можно строить схемы, выполняющие любую логическую функцию. Более того, эта схема обратима: зная выходные данные, можно, пройдя по ней в обратном направлении, вычислить вход. В настоящее время стандартом для RSA является использование числа из 2048 бит, то есть около 616 десятичных знаков. По оценке этой команды исследователей, 2048-битная RSA будет уязвима для квантового компьютера с n = 256, а шифрование на основе эллиптической кривой – для квантового компьютера с n = 384.

Распознавать уязвимости – это, конечно, замечательно, но главный вопрос в том, что следует делать для защиты. Решение этой задачи требует совершенно новых криптографических методов. Общая идея их та же, что всегда: метод шифрования должен основываться на трудных математических задачах с возможностью какого-нибудь простого обхода. Но теперь «трудный» означает «трудный для квантового компьютера». В настоящий момент обнаружено четыре основных класса задач такого рода:

• Случайные линейные шифры с коррекцией ошибок.

• Решение систем нелинейных уравнений над большими конечными полями.

• Нахождение коротких векторов в многомерных решетках.

• Нахождение маршрутов между случайными вершинами псевдослучайного графа.

Рассмотрим кратко четвертый из этих вариантов, где задействованы новейшие идеи и очень продвинутая математика.

Для практических целей возьмем граф, который имеет около 10⁷⁵ вершин и соответственно большое число ребер. Шифр зависит от нахождения пути через этот граф между двумя конкретными вершинами. Это одна из разновидностей задачи коммивояжера, имеющая сопоставимую с ней трудность. Чтобы создать в решении этой задачи обходной путь, граф должен иметь скрытую структуру, которая делает решение простым. Центральная идея состоит в использовании так называемых суперсингулярных изогенных графов, или SIG. Они образуются с использованием эллиптических кривых, которые называют суперсингулярными. Вершины такого графа соответствуют всем суперсингулярным эллиптическим кривым над алгебраическим замыканием конечного поля с p элементами. Существует примерно p/12 таких кривых.

Изогения между двумя эллиптическими кривыми – это полиномиальное отображение одной из них на другую, сохраняющее структуру группы Морделла – Вейля. Мы используем изогении для определения ребер графа. Для этого следует взять второе простое число q. Ребра этого графа соответствуют изогениям q-й степени между двумя эллиптическими кривыми, соответствующими концам данного ребра. Из каждой вершины исходит ровно q + 1 ребер. Такие графы называются экспандерами, или расширяющими, это означает, что случайные пути, начинающиеся в любой вершине, быстро расходятся после их начала, по крайней мере на протяжении большого числа шагов.

Граф-экспандер может быть использован для создания функции хеширования – булевой функции, формирующей из n-битных строк m-битные, где m много меньше n. Алиса может использовать хеш-функцию, чтобы убедить Боба, что она знает конкретную n-битную строку, известную также и Бобу, не раскрывая самой строки. Для этого она формирует намного более короткую хеш-функцию этой строки и отправляет ее Бобу. Боб вычисляет хеш-функцию своей строки и сравнивает.

Для того чтобы этот метод надежно работал, необходимо выполнить два условия. Одно из них – это условие потайного входа, известное как стойкость к восстановлению прообраза: с вычислительной точки зрения невозможно обратить хеш-функцию и найти n-битную строку, которая дает данный хеш. В общем случае таких строк существует множество, но дело в том, что на практике невозможно найти ни одной. Второе условие – стойкость функции хеширования к коллизиям. Это означает, что с вычислительной точки зрения невозможно найти две разные n-битные строки с одним и тем же m-битным хешем. Раз так, то даже если Ева – любительница подслушивать (или устройство перехвата сообщений) – сумеет подслушать разговор, то хеш, который Алиса пересылает Бобу, не поможет ей разобраться, что представляла собой первоначальная n-битная строка.