Это база: Зачем нужна математика в повседневной жизни - Йэн Стюарт
Шрифт:
Интервал:
Закладка:
Первой реакцией на заявления D-Wave было недоверие. Архитектура устройства была необычной, и у некоторых возникли вопросы: действительно ли это настоящий квантовый компьютер, а не навороченный классический компьютер, использующий околоквантовое оборудование. Во время испытаний он превосходил стандартные классические компьютеры на полезных задачах, но при этом был специально сконструирован для таких задач, тогда как классические компьютеры, с которыми он состязался, – нет. Его преимущества, казалось, исчезали, если классические компьютеры специально конструировались для соответствующих задач. Споры продолжаются до сих пор, но машины D-Wave используются и неплохо работают.
Ключевой целью исследований является квантовое превосходство: создание квантового устройства, которое превосходит по производительности лучшие классические компьютеры по крайней мере на одном расчете. В 2019 году команда Google AI опубликовала статью в Nature под заголовком «Квантовое превосходство с использованием программируемого сверхпроводящего процессора»{45}. Она объявила, что создала квантовый процессор под названием Sycamore с 54 кубитами, но один из них отказал, что снизило их количество до 53. С его помощью за 200 секунд решили задачу, на решение которой у классического компьютера ушло бы 10 000 лет.
Архитектура квантового процессора Sycamore
Это заявление сразу же было поставлено под сомнение по двум причинам. С одной стороны, этот расчет предположительно мог быть выполнен классической машиной за более короткое время. С другой, Sycamore решал довольно надуманную задачу: получение выборки выходных последовательностей псевдослучайной квантовой схемы. Устройство соединяет компоненты схемы случайным образом, а цель всего этого – рассчитать распределение вероятностей выборки возможных выходных последовательностей. Одни выходные последовательности оказываются гораздо более вероятными, чем другие, так что это распределение получается очень сложным и неоднородным. Время классического расчета с ростом числа кубитов увеличивается экспоненциально. Тем не менее команде ученых удалось достичь своей главной цели: показать, что не существует практических препятствий для создания квантового компьютера, способного превзойти классический в чем-нибудь.
Сразу возникает вопрос: как удостовериться в том, что ответ верен? Ведь невозможно ждать 10 000 лет, пока классический компьютер решит задачу, и нельзя просто верить результату без всякой проверки. Исследователи справились с этой проблемой при помощи метода, известного как сравнительный анализ с перекрестной энтропией. Он предполагает сравнение вероятностей конкретных битовых строк с теоретическими вероятностями, рассчитанными на классическом компьютере. Это позволяет оценить, насколько велика вероятность того, что полученный результат верен. Исследователи пришли к выводу, что результат точен с погрешностью до 0,2 % с очень высокой («пять сигм») вероятностью.
Несмотря на прогресс, большинство экспертов уверены, что до практической реализации идеи квантового компьютера нам еще далеко. Некоторые сомневаются даже, что его вообще можно создать. Физик Михаил Дьяконов написал:
Число непрерывных параметров, описывающих состояние столь полезного квантового компьютера в любой момент, должно быть… около 10300. ‹…› Можем ли мы когда-нибудь научиться контролировать эти более чем 10300 непрерывно меняющихся параметров, определяющих квантовое состояние такой системы? Мой ответ прост. Нет, никогда.
* * *
Возможно, Дьяконов и прав, но другие с ним не согласны. Так или иначе, даже призрачная возможность того, что кто-то – скорее всего, многочисленная группа исследователей, финансируемая правительством или крупной корпорацией, – справится с созданием квантового компьютера, заставляет службы безопасности многих стран и финансовых институтов видеть ночные кошмары. Недруги тогда смогут расшифровать секретные сообщения, а преступники – разрушить систему интернет-торговли и банкинга. Поэтому теоретики ломают головы над тем, как могла бы выглядеть криптография в постквантовом мире, и пытаются сыграть на опережение и обеспечить безопасность коммуникаций.
К счастью, то, что квантовый компьютер может взломать, он же может сделать нераскрываемым. Для этого потребуются новые криптографические методы, использующие квантовые расчеты для создания шифров, которые не сможет взломать даже квантовый компьютер. Это потребует нового взгляда на математику, лежащую в основе вычислений. Как ни странно, в значительной мере это все та же теория чисел, хотя и более современная, чем у Ферма.
Теоретически неминуемое наступление квантовых компьютеров породило волну исследований, нацеленных на создание методов шифрования, которые не могут быть взломаны квантовым компьютером. Не так давно Национальный институт стандартов и технологии США запустил программу постквантовой криптографии с целью идентификации классических криптосистем, находящихся в зоне риска, и поиска новых способов борьбы с их уязвимостями. В 2003 году Джон Прус и Кристоф Залка{46} оценили уязвимость системы RSA и криптографии на основе эллиптических кривых для квантового компьютера, работающего по алгоритму Шора. В 2017 году Мартин Реттелер с коллегами{47} дополнил их результаты. Исследователи доказали, что в случае эллиптической кривой над конечным полем с q элементами, где q примерно равно 2n, RSA уязвима для квантового компьютера с числом кубитов 9n + 2 log2n +10 и схемы из не более чем 448n3 log2n +4090n3 вентилей Тоффоли. Вентиль Тоффоли – особый тип логической схемы. Из вентилей Тоффоли можно строить схемы, выполняющие любую логическую функцию. Более того, эта схема обратима: зная выходные данные, можно, пройдя по ней в обратном направлении, вычислить вход. В настоящее время стандартом для RSA является использование числа из 2048 бит, то есть около 616 десятичных знаков. По оценке этой команды исследователей, 2048-битная RSA будет уязвима для квантового компьютера с n = 256, а шифрование на основе эллиптической кривой – для квантового компьютера с n = 384.
Распознавать уязвимости – это, конечно, замечательно, но главный вопрос в том, что следует делать для защиты. Решение этой задачи требует совершенно новых криптографических методов. Общая идея их та же, что всегда: метод шифрования должен основываться на трудных математических задачах с возможностью какого-нибудь простого обхода. Но теперь «трудный» означает «трудный для квантового компьютера». В настоящий момент обнаружено четыре основных класса задач такого рода:
• Случайные линейные шифры с коррекцией ошибок.
• Решение систем нелинейных уравнений над большими конечными полями.
• Нахождение коротких векторов в многомерных решетках.
• Нахождение маршрутов между случайными вершинами псевдослучайного графа.
Рассмотрим кратко четвертый из этих вариантов, где задействованы новейшие идеи и очень продвинутая математика.
Для практических целей возьмем граф, который имеет около 1075 вершин и соответственно большое число ребер. Шифр зависит от нахождения пути через этот граф между двумя конкретными вершинами. Это одна из разновидностей задачи коммивояжера, имеющая сопоставимую с ней трудность. Чтобы создать в решении этой задачи обходной путь, граф должен иметь скрытую структуру, которая делает решение простым. Центральная идея состоит в
