Почему квантовые компьютеры могут сделать бесполезными пароли и шифрование
В октябре 2019 года 53-кубитный процессор Sycamore от Google смог за 200 секунд решить задачу, на которую лучшему на тот момент суперкомпьютеру Summit потребовалось бы 2,5 дня. Разберёмся, как устроены эти машины, какие из них уже работают, какую пользу могут принести и какую несут угрозу кибербезопасности.
Путь к квантовым вычислениям
Основы квантовых вычислений лежат в квантовой механике — разделе физики, описывающем мир на уровне атомов и элементарных частиц. Идея использовать законы микромира для вычислений возникла еще в 1980-х годах. Именно тогда профессор Калифорнийского университета в Беркли Пол Бениофф представил теоретическую модель квантового компьютера, а знаменитый физик Ричард Фейнман указал на потенциал таких машин для моделирования сложных квантовых систем.
Настоящий прорыв произошел в 1994 году, когда математик Питер Шор разработал квантовый алгоритм, способный быстро разлагать большие числа на простые множители. Это стало сенсацией, ведь именно на сложности этой задачи основана безопасность многих современных криптографических систем, защищающих банковские карты и переписку. Алгоритм Шора показал: достаточно мощный квантовый компьютер сможет взломать эту защиту. Вскоре, в 1996 году, Лов Гровер представил ещё один важный квантовый алгоритм, ускоряющий поиск в больших базах данных.
С конца 1990-х начались эксперименты по созданию реальных квантовых процессоров на основе разных технологий. Первый квантовый компьютер заработал в 1998 году, а в 2001 году исследователи из IBM и Стэнфорда смогли с помощью более продвинутой модели разложить на множители число 15, впервые экспериментально реализовав алгоритм Шора. Это были первые шаги, но они положили начало новому витку развития квантовых технологий.
Как работают квантовые компьютеры
Квантовые компьютеры отличаются от привычных ПК и даже традиционных суперкомпьютеров на фундаментальном уровне.
Биты против кубитов
Классические компьютеры, от смартфона до суперкомпьютера, работают с битами.
Бит — это базовая единица информации, которая может принимать только одно из двух значений: 0 или 1 — в этом они похожи на обычный выключатель света: он либо включен (1), либо выключен (0). Вся информация в классическом компьютере кодируется последовательностями таких нулей и единиц.
Квантовые компьютеры используют кубиты (квантовые биты). Кубит, как и бит, может принимать значения 0 или 1. Но у него есть и третье состояние — суперпозиция, в которой он одновременно принимает значение и 0, и 1. Это похоже не на выключатель, а на диммер (регулятор яркости света), который может находиться в промежуточном положении между «полностью выключено» и «полностью включено».
Кубит существует в «размытом» состоянии, содержащем информацию об обеих возможностях сразу, пока кто-то не попытается измерить его значение. В момент измерения суперпозиция «схлопывается», и кубит принимает одно конкретное значение — либо 0, либо 1, с определённой вероятностью.
Суперпозиция
Способность кубитов находиться в суперпозиции позволяет квантовому компьютеру обрабатывать намного больше информации относительно традиционных компьютеров. Например, 3 классических бита могут представлять только одно из 8 возможных чисел (от 000 до 111) в каждый момент времени. А вот 3 кубита в состоянии суперпозиции могут представлять все 8 комбинаций одновременно. С увеличением числа кубитов N количество одновременно обрабатываемых состояний растёт экспоненциально — 2N. Уже для нескольких десятков кубитов это число превышает возможности самых мощных классических суперкомпьютеров. Это свойство даёт квантовым компьютерам потенциал для решения задач, требующих перебора огромного числа вариантов.
Запутанность
Ещё одно квантовое явление, используемое в вычислениях, — квантовая запутанность. Два или более кубита можно «запутать» так, что их состояния станут неразрывно связанными, даже если их разнести на большое расстояние. Они ведут себя как единая система. Если измерить состояние одного запутанного кубита, мы мгновенно узнаем состояние другого, независимо от того, как далеко они находятся. Альберт Эйнштейн называл это «жутким действием на расстоянии». Запутанность позволяет кубитам координировать свои действия и выполнять сложные вычисления более эффективно.
Суперпозиция и запутанность — это два главных «кита», на которых стоят квантовые компьютеры. Именно благодаря этим свойствам такие вычислительные системы имеют большое преимущество перед традиционными машинами.
Работающие квантовые компьютеры
Хотя полномасштабные, отказоустойчивые квантовые компьютеры — дело будущего, квантовые процессоры уже существуют и работают. Разные компании и исследовательские группы по всему миру создают всё более мощные системы, используя различные физические подходы к реализации кубитов.
Среди лидеров — такие гиганты, как IBM, которая последовательно наращивает число кубитов в своих сверхпроводящих процессорах: от Eagle (127 кубитов) и Osprey (433 кубита) до Condor (1121 кубит). Google Quantum AI также использует сверхпроводящие кубиты — их процессор Sycamore (53 кубита) в 2019 году продемонстрировал так называемое квантовое превосходство, смоделировав случайную квантовую схему для 53 кубитов быстрее самого мощного на тот момент суперкомпьютера. Сейчас Google развивает чип Willow (105 кубитов) с улучшенной коррекцией ошибок.
Квантовый компьютер IBM Q System One
Microsoft делает ставку на экзотические топологические кубиты, которые теоретически должны быть более устойчивы к ошибкам, и недавно представила свой первый процессор Majorana 1.
Канадская компания D-Wave Systems пошла другим путём — она создаёт системы для «квантового отжига», специфического типа квантовых вычислений, хорошо подходящего для решения задач оптимизации. Процессоры компании уже содержат тысячи кубитов и находят применение в логистике и оптимизации сетей. Компания IonQ успешно развивает технологию кубитов на захваченных ионах, известную долгим временем жизни кубитов и высокой точностью операций; их система H2-1 насчитывает 56 кубитов.
Количество кубитов — не единственный показатель мощности квантового компьютера. Не менее важны стабильность, точность операций, время когерентности и связность — то, как кубиты взаимодействуют друг с другом. Современные системы, несмотря на прогресс, всё ещё относятся к классу «шумных» квантовых компьютеров (Noisy Intermediate-Scale Quantum, NISQ).
Сравнение различных типов кубитов.
Трудности квантовых вычислений
Главными препятствиями на пути создания мощных и надёжных квантовых компьютеров являются шум и декогеренция. Квантовые состояния кубитов чрезвычайно хрупки. Любое взаимодействие с окружающей средой — случайные колебания температуры, электромагнитные поля, даже космические лучи — вносит помехи, которые называют «шумом» в систему, приводя к ошибкам в вычислениях.
Декогеренция — это процесс потери кубитом своих квантовых свойств (суперпозиции и запутанности) из-за нежелательного взаимодействия со средой. Время, в течение которого кубит может сохранять когерентное квантовое состояние, пока очень мало — от микросекунд до миллисекунд для большинства современных технологий. Этого времени недостаточно для выполнения по-настоящему сложных и долгих квантовых алгоритмов.
Чтобы минимизировать шум и продлить время когерентности, кубиты приходится изолировать от внешнего мира в экстремальных условиях: сверхпроводящие кубиты охлаждают до температур, близких к абсолютному нулю (–273,15ºC), а кубиты на ионах или атомах удерживают в сверхвысоком вакууме с помощью лазеров и магнитных полей. Это делает квантовые компьютеры очень громоздкими, энергозатратными и дорогими. Разработка методов квантовой коррекции ошибок, которые позволили бы строить надежные «логические кубиты» из множества физических шумных кубитов, — одна из самых актуальных задач в этой области.
Постквантовая криптография — безопасность под угрозой
Алгоритм Шора представляет прямую угрозу для асимметричной криптографии (RSA, ECC), на которой держится безопасность значительной части современного интернета и цифровых коммуникаций. Как только появятся достаточно большие и стабильные квантовые компьютеры, вся информация, зашифрованная этими методами, окажется под угрозой. Например, по оценкам, для взлома алгоритма RSA-2048 может потребоваться машина с тысячами или миллионами логических кубитов. Причём злоумышленники могут записывать зашифрованный трафик уже сейчас, чтобы расшифровать его позже, когда появятся нужные вычислительные мощности.
Схема развития криптографии в постквантовую эпоху
Поэтому мировое криптографическое сообщество активно работает над созданием и стандартизацией постквантовой криптографии (PQC) — новых криптографических алгоритмов, которые были бы устойчивы к атакам как классических, так и квантовых компьютеров. Идея PQC в том, чтобы шифрование и цифровая подпись были основаны на математических задачах, которые считаются сложными даже для квантовых алгоритмов. Основные направления исследований включают криптографию на основе:
- Решёток (Lattice-based). Использует сложность определённых задач в многомерных решётках. Считается одним из самых перспективных направлений.
- Кодов (Code-based). Основана на сложности расшифровки случайных кодов, исправляющих ошибки.
- Хэш-функций (Hash-based). Использует свойства криптографических хэш-функций для построения цифровых подписей.
Переход на PQC потребует обновления программного и аппаратного обеспечения, протоколов и стандартов по всему миру. Банки, государственные учреждения, технологические компании уже начинают этот процесс — они проводят инвентаризацию своих криптосистем, тестируют новые алгоритмы и разрабатывают планы миграции. Правительства начинают разрабатывать законы, чтобы стимулировать этот переход.
Защитят ли квантовые компьютеры ваши пароли
Квантовые технологии могут не только угрожать безопасности, но и усиливать её. Квантовое распределение ключей (QKD) использует законы квантовой физики (в частности, невозможность измерить квантовое состояние без его измерения) для создания абсолютно защищённого канала передачи криптографических ключей. Любая попытка перехвата ключа неизбежно внесёт обнаруживаемые ошибки. Системы QKD уже существуют и начинают внедряться для защиты особо важных коммуникаций.
Кроме того, квантовые компьютеры могут генерировать истинно случайные числа, которые необходимы для создания надёжных криптографических ключей, в отличие от псевдослучайных чисел, генерируемых классическими компьютерами.
До создания универсального, отказоустойчивого квантового компьютера ещё далеко. Но, как показала сфера искусственного интеллекта, востребованная технология при достаточном спросе со стороны общества может развиваться очень быстро.