Хабрахабр

Как квантовый компьютер может взломать современные системы шифрования и снизить стоимость выработки аммиака?

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

В этом посте мы приводим расшифровку его лекции о квантовых технологиях с дополнениями, чтобы поделиться полезными и интересными данными с подписчиками Acronis на Habrahabr.
Крупномасштабные проекты реализуются в США, Европе, Китае и России. С рассказом о событиях в “Квантовой отрасли” перед сотрудниками Acronis выступил научный руководитель группы «Квантовые информационные технологии» РКЦ Алексей Федоров. Прогнозируется, что квантовые компьютеры могут совершить революцию в целом ряде направлений, например, в защите информации, искусственном интеллекте и моделировании новых материалов. Наибольший интерес представляет собой квантовый компьютер — в гонку за его построением вовлечены не только университеты, но также и крупные корпорации среди которых Google, IBM, Microsoft и Intel.

В отличие от классических систем, находящихся всегда в одном из возможных состояний, квантовые системы могут быть в состоянии квантовой суперпозиции: находиться одновременно во всех допустимых состояниях. В современном контексте квантовые технологии — это методы управления индивидуальными квантовыми объектами, такими как атомы, фотоны, электроны, ионы и так далее. У монетки можно определить два состояния — орел или решка — и закодировать их как 0 и 1. Примером различия между классическим миром и квантовым может быть монетка. Две монетки — в одном из 4 возможных состояний в один момент времени. Тогда классическая монетка может находиться либо в состоянии 0, либо в состоянии 1. Десять монеток — в одном из 1024 состояний. Четыре монетки — в одном из 16 состояний.

Точнее будет сказать, что квантовая монетка может находиться в состоянии орла и решки одновременно. Принцип суперпозиции позволяет одной “квантовой монетке” быть не только строго орлом или решкой, но и находиться в одном из бесконечного числа «промежуточных» состояний между орлом и решкой. Это то, что ученые называют квантовой суперпозицией, и то, что наш мозг, выросший в классическом мире, даже не способен представить — к этому можно только привыкнуть. При этом две несовместимые с классической точки зрения альтернативы (выпавшая орлом монетка и выпавшая решкой монетка) как бы накладываются друг на друга внутри единого квантовом состояния. Две “квантовые монетки” могут находиться в суперпозиции из 4 состояний. При этом, чтобы полностью описать такое квантовое наложение требуются два комплексных числа, соответствующих каждой из классически различимых альтернатив. Такие “квантовые монетки” называют кубитами — квантовыми аналогами битов информации. А 10 “квантовых монеток” — в суперпозиции из из 1024 состояниях. Для описания системы из n кубит требуется 2^n комплексных числа.

При наличии даже 50 кубитов количество комплексных чисел, необходимых для описания их состояния — 2^50 — будет настолько большим, что точно промоделировать такую систему будет невозможно даже на самом мощном суперкомпьютере. Основная фишка квантовых вычислений состоят именно в этом: с ростом числа кубитов количество параметров, которым мы оперируем при вычислениях, растет экспоненциально. Такой порог является одним из возможных объяснений для явления, называемого квантовым превосходством (quantum supremacy или quantum advantage): возможности при помощи квантового компьютера решать те задачи, на которые не способны существующие классические компьютеры.

Квантовый квест и квантовая гонка

Для этого нужно решить целый “квест” по управлению квантовой материей. Однако построить такой компьютер непросто. Квантовая гонка идет одновременно и среди корпораций, и в научном сообществе. В данный момент множество лабораторий в мире разрабатывают новые методы управления квантовыми объектами. Но квантовая гонка имеет важное фундаментальное значение — за порогом квантового превосходства нас ждут новые открытия в совершенно различных областях физики: от физики низких температур до физики высоких энергий. Ведущие разработчики представляют все новые и новые решения. К тому же у квантовых компьютеров также большой потенциал для решения практических задач, поэтому в его разработку включились корпорации.

С одной стороны необходимо иметь достаточно большое число кубит, чтобы обеспечить большое пространство состояний, но, с другой стороны, необходимо контролировать каждый кубит в отдельности. В чем же заключается квест по управлению квантовой материей? Эта особенно важно для квантовой физики, но, если задуматься, то касается и других сфер деятельности человека. Ясно, что чем больше система, тем сложнее она поддается управлению на уровне отдельных индивидуальных компонентов. Но чем больше будет этих людей, тем сложнее окажутся их взаимодействия, и тем сложнее будет их контролировать 🙂 Например, если вы хотите создать огромную и крутую компанию, вам придется нанять много талантливых людей.

Но, преодолев его, мы сможем разрабатывать мощные квантовые компьютеры, способные решать интересные задачи. В квантовом мире поиск баланса между масштабом и предсказуемостью — самый большой челлендж на сегодня. Это очень наглядная мера, она показывает, что недостаточно просто сказать сколько в системе кубитов, важна еще и степень контроля над ними, которая позволяет избежать ошибок. Например, в IBM используют термин квантовый объем — это количество кубит на количество ошибок при совершении операции. Для роста квантового объема необходим рост и количества, и “качества” кубитов.

Поэтому говоря о кубитах нужно разделять физические кубиты и логические кубиты. Следует всегда учитывать, что вероятность ошибок — неотъемлемое свойство квантового“ железа”. Логические кубиты — те объекты, над которыми есть реальный контроль, и к ним можно обращаться с фиксированными параметрами без ошибок. Физические кубиты — это реальные атомы или сверхпроводящие цепочки, так сказать “наштампованные” элементы. В терминах квантового объема можно понимать это так: если уровень ошибок нулевой, то дальше вычислительные возможности (квантовые объем) растет за счет увеличения числа логических кубитов. Вычислительные возможности квантового компьютера определяются, в конечном счете, именно количеством логических кубитов, которые работают безупречно.

Он стал одним из первых квантовых компьютеров такого масштаба. Если говорить о достижениях в области работающих квантовых компьютеров, нельзя не упомянуть компьютер IBM на 50 кубитах. В квантовом процессоре IBM не реализован индивидуальный контроль над каждым кубитом и достаточно высок уровень ошибок, но сам чип уже существует. “Рабочая лошадка” квантовых компьютеров компании IBM — сверхпроводящие кубиты, которые для своей работы должны быть охлаждены до очень низких температур. Кроме того, через несколько лет корпорация планирует сделать систему на 100 кубитов. Также у IBM есть открытый 5-кубитный и 16-кубитные квантовые компьютеры, которым может воспользоваться каждый человек через Интернет. Недавно IBM анонсировала интегрированный квантовый компьютер IBM System One, который является законченным устройством, не требующим, по словам разработчиков, каких либо специальных условий для работы — это существенно приближает такую систему к пользователям, однако о решении практически важных и востребованных задач с помощью подобного компьютера пока говорить сложно.

И это хорошо, ведь если одна из корпораций столкнется с проблемами при реализации своего подхода, вторая продолжит движение к прогрессу. Компания Intel находится на пороге того же рубежа в 50 кубит, но использует другую технологию для создания кубитов.

Базовая технология у Google такая же как у IBM — сверхпроводящие кубиты. Лидером квантовой гонки сегодня можно считать компанию Google, которой был продемонстрирован квантовый компьютер из 72 кубитов. Так что в ближайшее время от компании можно ожидать демонстрации квантового превосходства с помощью разработанного ими квантового процессора. Группой ученых и разработчиков Google также был опубликован ряд научных статей, описывающих подходы к достижению квантового превосходства.

Кстати, IonQ — не единственный пример стартапа в сфере квантовых вычислений — их сейчас больше десятка. В академическом сообществе тоже была создана система из 51 кубита — это удалось группе Михаила Лукина (выпускника Физтеха и главы Международного консультативного совета Российского квантового центра) на основе ультрахолодных нейтральных атомов, а также система из 53 кубитов от группы Кристофера Монро из Университета Мэрилэнда, который также является основателем компании IonQ, разрабатывающей коммерческий квантовый компьютер на ионах.

“Поднебесная” вынашивает грандиозные планы, планируя сконструировать самый большой квантовый компьютер, и на это у разработчиков уже есть 12 миллиардов долларов для создания Национальной квантовой лаборатории. Очевидно, что большой потенциал в квантовой сфере есть у Китая.

В процессоре D-Wave тысячи кубитов, но работают они в другом режиме — режиме квантового отжига. Несколько особняком стоит компания D-Wave. Несмотря на то, что с D-Wave уже работают компании, например, Google и Volkswagen, насчет преимуществ подобного квантового компьютера компании ведутся горячие споры. Это позволяет решить при помощи такого компьютера, фактически, лишь одну задачу.

Прикладная сторона вопроса

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

  • Специализированные квантовые компьютеры, которые направлены на решение одной конкретной специфической задачи, например, задачи оптимизации. Примером продукта являются квантовые компьютеры D-Wave.
  • Универсальные квантовые компьютеры — которые способны реализовать произвольные квантовые алгоритмы. На сегодняшний день существуют только небольшие прототипы универсальных квантовых компьютеров — в этом направлении работают Google, IBM и Intel. Они закладывают основу, но пока не позволяют делать что-то масштабное и не умеют справляться с ошибками.

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

Например, для поиска по неупорядоченной базе данных квантовый алгоритм имеет квадратичное преимущество. Благодаря тому, что IBM предлагает всем желающим воспользоваться квантовым компьютером, современные квантовые программисты уже тренируются в сборке задач и запуске их на небольших квантовых компьютерах. Представим, что в некоторой базе данных адрес каждого из элементов состоит из n бит, и в этой базе данных есть лишь один элемент, удовлетворяющий некоторым условиям. В такой задаче неупорядоченная база данных может быть представлена как некоторый “черный ящик”, на вход которого подаются запросы (адреса элементов в этой базе данных), а черный ящик на них отвечает “да” или “нет” (подходит ли элемент, расположенный по данному адресу, требованиям запроса). из-за неупорядоченности базы данных все, что нам остается это последовательно перебирать все возможные адреса (которых 2^n штук) до тех пор пока нам наконец не повезет и мы не попадем на нужный элемент. Чтобы найти этот элемент нам в среднем потребуется порядка 2^n запросов (более точно 2^(n-1)), т.к. Преимущество «алгоритма квантового перебора», названного в честь Л. В случае же, если у нас есть квантовый аналог подобного черного ящика (его еще называют «квантовым оракулом») для того, чтобы получить ответ нам потребуется порядка 2^(n/2) запросов. Гровера, обусловлено возможностью задавать множество вопросов квантовому ящику одновременно — формировать суперпозицию запросов.

Однако для её решения потребуется количество запросов, растущее экспоненциально с ростом сложности задачи (в рассмотренном примере, ей соответствовал параметр n). Важно отметить, что задача поиска в неупорядоченной базе данных носит универсальный характер — к ней можно свести практически любую другую задачу (в том числе и NP-полную). В ряде случаев его возможности будут значительно скромнее. Таким образом, не стоит относиться к квантовому компьютеру как к всемогущему инструменту, способному решать произвольные вычислительные задачи с экспоненциальным ускорением.

Например, в промышленности востребован расчет параметров химических соединений и моделировании химических реакций. Тем не менее, большой потенциал уже сегодня очевиден для задач из сферы квантовой химии. Квантовые компьютеры могут помочь детально определить цепочки реакций, динамику процессов, найти катализаторы для нужных реакций — все это очень полезно! При использовании классических компьютеров, нам не хватает возможностей и приходится, зачастую, идти на компромисс с точностью. Это соединение активно используется в удобрениях для растений, и на его производство тратится 1-2% всей энергии на земле (данные Quantum Computing Report и BP). Одна из наиболее обсуждаемых сегодня задач — производство аммиака. Если бы при помощи квантового компьютера можно было бы оптимизировать процесс производства аммиака за счет точного знаниях всех параметров, то он уже окупил бы все вложения, которые совершены в разработки технологий (помните, 1-2% мировой энергии).

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

Дело не только в железе

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

Пока их все еще лишь несколько десятков, а для полноценного развития сферы квантовых вычислений, алгоритмов должно стать намного больше. Однако квантовых алгоритмов пока все еще недостаточно.

Страхи и технологии ИБ

Квантовой компьютер имеет две стороны: темную и светлую. До сих пор мы говорили о светлой стороне — решении им практически востребованных задач, которые не могут быть решены при помощи классических компьютеров. Но и есть и темная сторона: квантовый компьютер намного лучше классического решает задачу факторизации. Сложность этой задачи, как известно, является одной из основ обеспечения стойкости распространенных алгоритмов криптографии с открытым ключом. Задача факторизации чрезвычайно сложна для классического компьютера, а на квантовом может быть эффективно решена при помощи алгоритма Шора. Например, взлом RSA-ключа, состоящего из 1024 бит, займет миллионы лет непрерывных вычислений на классических компьютерах, тогда как на квантовом компьютере эта задача будет решена за 10 часов (если предположить, что каждая квантовая операция выполняется 10 нс и что в распоряжении имеется компьютер из достаточного количества логических кубитов). Пока квантовые компьютеры не позволяют ничего взломать — ведь для криптоанализа RSA нужно несколько тысяч управляемых кубитов. И хотя потенциально опасного компьютера еще не существует, сообщество уже сегодня задумывается о защите от возможных проблем в будущем.

Как известно, одиночный фотон нельзя разделить, а квантовое состояние нельзя скопировать — это фундаментальное ограничение квантовой механики. Один вариант решения — использование технологии квантовой распределение ключей, которая позволяет двум сторонам обмениваться криптографическими ключами для симметричного шифрования. В этой сфере на мировой арене лидирует Китай. На таком принципе — защите передаваемых данных фундаментальными физическими законами — строятся новые приборы. М.В. В России технология квантового распределения ключей развиваются несколькими группами, например, в РКЦ, МГУ им. Прибор, разработанный в РКЦ уже проходил испытания в Сбербанке и Газпромбанке. Ломоносова и ИТМО.

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

Насколько известно, в самых критически важных системах Китая реализуется именно такая система. Центральная идея заключается в том, чтобы использовать квантово-распределенные ключи в шифре Вернама — одноразовом блокноте.

Она включает в себя новый класс алгоритмов с открытым ключом, которые основаны на задачах, являющихся вычислительно сложными как для классического компьютера, так и для квантового. Второй принцип защиты — это постквантовая криптография.

Да, это возможно. Многих интересует вопрос о том, навредит ли квантовый компьютер блокчейну. Однако и защитить блокчейны можно также квантовым распределением ключей или постквантовой криптографией. За счет атак на цифровые подписи, а также за счет использования квантового алгоритма Шора и воздействия на алгоритмы консенсуса со стороны квантового алгоритма Гровера.

В ожидании чуда

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть