Это база: Зачем нужна математика в повседневной жизни

Это заявление сразу же было поставлено под сомнение по двум причинам. С одной стороны, этот расчет предположительно мог быть выполнен классической машиной за более короткое время. С другой, 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.