Квантовые компьютеры сегодня всё ещё воспринимаются как нечто редкое и необычное, хотя новости о свежих достижениях в этой сфере появляются с завидной регулярностью. Например, в Ирландии представили шестикубитную систему RacQ, выполненную в форм-факторе стандартной 19-дюймовой серверной стойки и предназначенную для работы вместе с классическими фоннеймановскими машинами в пределах одного дата-центра. Тем временем в Китае усовершенствовали фотонный квантовый процессор из линейки Jiuzhang до версии 4.0, который вместо привычных кубитов использует 1024 сжатых световых состояния. Благодаря сложной интерферометрической схеме с 8176 модами исследователи получают возможность манипулировать более чем тремя тысячами фотонов: такая система способна выполнять вычисления особого типа — гауссову бозонную выборку (Gaussian boson sampling, GBS) — за считаные микросекунды; на много десятков порядков быстрее, чем самые мощные классические суперкомпьютеры (квантовое превосходство очевидно; правда, практической пользы от GBS пока нет, — это лишь демонстрационная задача). В лабораториях Гарвардского университета в США предсказали, что в ближайшие 5–10 лет появятся высокопроизводительные и устойчивые к ошибкам квантовые вычислители, но при этом отметили, что пока не совсем понимают, для каких конкретно прикладных задач такие устройства могут быть востребованы. И в самом деле, для каких?
Характерная массивная конструкция, изображением которой сопровождают множество заметок о квантовых вычислениях, — лишь внешняя обвязка, криостат с системами экранирования и контроля; физические кубиты в этом масштабе выглядели бы на картинке в лучшем случае точками (источник: Google)
Вот переписанный HTML-контент с сохранением всех тегов и смысла, но с изменёнными словами и структурой предложений:⇡#Шифруй не шифруй
Мы уже обсуждали фундаментальные принципы устройства и функционирования квантовых компьютеров: вместо манипуляций с фиксированными битами (где сигнал, кодирующий «0», в обычном состоянии остаётся нулём при перемещении по цепям вычислительной схемы и лишь проходя через логические вентили, может превратиться в «1») они опираются на квантовые явления — суперпозицию и запутанность. Здесь, разумеется, возникает парадокс: квантовый компьютер — это устройство, по необходимости макроскопическое, тогда как квантовые эффекты становятся незначительными, когда коллективное поведение элементарных частиц (протонов, электронов, фотонов и т. д.), из которых состоит система, усредняет присущие каждой из них на микроуровне квантовые характеристики. Инженерам приходится проявлять немалую изобретательность, либо создавая макроскопические структуры, обладающие квантовыми свойствами (главным образом колебательные контуры), либо находя способы наблюдать и управлять поведением истинно квантовых объектов — единичных ионов, фотонов и прочего — в крупных установках. Именно необходимость с высокой точностью согласовывать события на квантовом уровне с помощью управляющих сигналов из макромира, а затем возвращать в макромир результаты квантовых процессов, и делает квантовые вычислители такими громоздкими, недолговечными (в плане быстрой потери запутанности их кубитами из-за декогеренции, что сильно ограничивает время, доступное для вычислений) и сложными для дальнейшего масштабирования аппаратами. Кстати, именно по той причине, что в обычных условиях — без технических уловок — макроскопические объекты декогерируют за время, измеряемое ничтожными долями секунды (порядка 10−20 с и даже меньше), квантовые эффекты в макромире, за редкими исключениями, не наблюдаются.
Почему же учёные уже не первое десятилетие подряд непрерывно придумывают концепции для создания всё новых вариантов квантовых компьютеров, а инженеры, преодолевая колоссальные трудности, находят способы воплощать эти идеи в реальных устройствах? Ответ прост: суперпозиция и запутанность позволяют квантовым вычислителям (точнее, квантовым системам, чьё поведение особым образом настроено на получение конкретного результата по заранее заданному алгоритму) как бы выполнять множество однотипных расчётов — с разными исходными данными — одновременно. Такой подход увеличивает вычислительную мощность квантовых машин не просто в разы, а сразу на много порядков по сравнению с архитектурой фон Неймана — и даже даёт (хотя бы теоретически, когда удастся создать эффективные стабильные системы из многих сотен, а лучше тысяч логических кубитов) возможность решать задачи, непосильные для классических компьютеров. «Непосильные» — в том смысле, что время, необходимое для классических вычислений, может, если следовать принципам фон Неймана, превышать предполагаемый возраст наблюдаемой Вселенной, как в случае факторизации действительно больших чисел, например.
Старания художников изобразить процесс квантовых вычислений как эволюцию запутанной квантовой системы порой приносят довольно наглядные плоды (источник: Quanta Magazine)
Вероятно, самый яркий пример того, где квантовые компьютеры могут найти практическое применение, — это взлом традиционных криптографических систем. В основе их защиты лежит невозможность решения сложных вычислительных задач (таких, как уже упомянутая факторизация) классическими компьютерами за приемлемое время. Совсем недавно на облачном квантовом компьютере удалось взломать 15-битный шифровальный ключ — точнее, исследователь с помощью алгоритма Шора вычислил закрытый ключ из открытого. Конечно, это пока лишь демонстрация того, что такое в принципе возможно: используемые сегодня повсеместно ключи содержат как минимум 256 символов, и чтобы справиться с ними, квантовым технологиям потребуется ещё не один год развития. Однако аналитики уже пугают ИТ-индустрию появлением доступных «квантовых отмычек» (этот решающий момент образно называют Q-Day) к 2030 году, самое позднее — к 2035-му, а инженеры активно разрабатывают постквантовую криптографию: например, создают жёсткие диски, способные защитить данные от атак с отложенной расшифровкой (когда злоумышленники накапливают пока ещё не взламываемые хеши паролей в ожидании скорой возможности их расшифровать).
К счастью, и у квантовых компьютеров есть свои ограничения: далеко не все типы задач можно решать с их помощью (и тем более эффективно). Поэтому алгоритмы для надежного шифрования в постквантовую эпоху уже существуют, хорошо изучены и активно внедряются. Просто исторически сложилось так, что один из самых распространенных криптографических алгоритмов в мире — RSA, построенный именно на факторизации, — быстро стал стандартом де-факто, что в свое время замедлило развитие альтернативных методов. Теперь же для них открылась зеленая улица, и поэтому решеточная криптография, цифровые подписи на базе криптографических хеш-функций, обмен ключами через суперсингулярных изогений и другие постквантовые технологии в ближайшие годы прочно войдут в повседневное использование. Выходит, что квантовые компьютеры в области криптографии будут важны не сами по себе, а скорее как негативный фактор. Своего рода пугало, которое самим своим существованием напоминает: нельзя полагаться на RSA и другие квантово-уязвимые методы, если нужно сохранить данные в секрете. Это как-то… обескураживает, не правда ли?
Алгоритмы для решения задач различных классов сложности оцениваются в нотации «О большое» по шкале от «ужасно» до «отлично», исходя из количества необходимых операций и масштабируемости задачи (источник: Wikimedia Commons)
⇡#Давайте без классики
Разумеется, негативные аспекты — лишь часть картины: существует множество по-настоящему трудных прикладных задач, которые обычные компьютеры решить не в силах, и они ждут того момента, когда в эксплуатацию войдут надежные много-кубитные квантовые вычислители (имеются в виду логические, а не физические кубиты). Трудность в данном случае трактуется строго, с математической точки зрения: вычислительные задачи распределяются по категориям в зависимости от того, насколько затратными по времени и/или ресурсам оказывается их решение при использовании самого эффективного алгоритма. В одну и ту же категорию сложности логично включить, например, задачи, которые можно выполнить на одном и том же оборудовании, — каждую с применением оптимального именно для неё алгоритма, само собой, — за сопоставимое время. Общепринятая нотация «О большое» (Big O notation) позволяет определить, как меняется время работы алгоритма или объем памяти, необходимой для вычислений, в зависимости от размера входных данных. Последний пункт, к слову, особенно важен в контексте современной темы искусственного интеллекта: объемы входных данных там поистине гигантские, поэтому оптимизации алгоритмов для решения задач ИИ (включая привлечение квантовых компьютеров) уделяют в этом направлении особое внимание.
Вот переписанный HTML-контент на русском языке, где все теги сохранены без изменений, а смысл исходного текста полностью передан другими словами и синтаксисом:Итак, простыми — или практически разрешимыми — в математическом контексте называют задачи, которые можно решить за время, растущее полиномиально с увеличением размера входного массива, обозначаемого как n. Можно выразить это иначе, абстрагируясь от временных рамок: количество операций, необходимых машине для получения результата, прямо пропорционально объёму входных данных в некоторой фиксированной степени (то есть полиному). К классу полиномиальных задач (polynomial — P-class problems) относятся O(n), O(n2) и, в общем виде, O(nk), где k, что критически важно, является константой, причём обычно не слишком большой, иначе понятие «простоты» теряет чёткость. К простым в математическом смысле причисляют все задачи сортировки, проверку числа на делимость, установление связности графов и множество других. Компьютеры, работающие на архитектуре фон Неймана, справляются с такими задачами особенно эффективно. Квантовые вычислители, по сути, здесь не нужны: даже если удастся получить выигрыш во времени, затраты на создание многокубитной системы, способной решать многопараметрическую задачу низкополиномиального класса, заведомо превысят любые разумные рамки. Возможно, когда-нибудь, если квантовые компьютеры достигнут такого же уровня развития, как современные классические, ситуация изменится, — но пока фон Нейману остаётся фоннейманово.
Эйлерова диаграмма, демонстрирующая взаимосвязи между различными классами сложности вычислительных задач: слева — в допущении P ≠ NP, справа — P = NP (источник: Wikimedia Commons)
Класс сложности NP (от англ. non-deterministic polynomial) определяется чуть более замысловато: своё название «недетерминистский» он получил благодаря недетерминированной машине Тьюринга, ведь к NP относят те задачи, которые на таком устройстве решаются за полиномиальное время. Мы не станем подробно разбирать отличия детерминированной машины Тьюринга от недетерминированной; достаточно сказать, что недетерминированные модели расширяют границы вычислительных возможностей, позволяя одновременно перебирать разные пути решения (а это уже напрямую связано с квантовыми вычислениями). Классические примеры NP-задач, которые детерминированная машина Тьюринга в принципе способна решить, но делает это крайне медленно, — это знаменитая задача коммивояжёра или уже упомянутое разложение большого числа на простые множители. Здесь способность машины на каждом шаге переходить сразу в несколько состояний даёт огромный выигрыш во времени по сравнению с тем, сколько потребуется детерминированной машине Тьюринга для той же работы. И хотя время решения NP-задач растёт экспоненциально с увеличением объёма входных данных n (как en), проверить полученный ответ (например, перемножив найденные простые числа и получив исходное) всё ещё можно за полиномиальное время. Существуют также NP-полные задачи — их можно назвать наиболее трудными в этом классе: к ним сводится любая другая NP-задача, и это сведение также выполняется за полиномиальное время. Отдельная тема — совпадают ли классы P и NP, но мы её сейчас не будем затрагивать: неспроста это одна из семи главных загадок теоретической информатики, за строгое доказательство или обоснованное опровержение которой Математический институт Клэя (Clay Mathematics Institute) назначил награду в миллион долларов.
Стоит отметить, что квантовый компьютер — даже если говорить о пока недостижимом промежуточном идеале с тысячей логических кубитов, который окончательно лишит смысла большинство современных криптографических алгоритмов, — не станет универсальным решением для действительно сложных задач: ни для всех NP-полных, ни даже для значительной части NP. Класс задач, с которыми квантовые компьютеры в принципе способны эффективно работать, определяется как bounded-error quantum polynomial time (BQP) — то есть решаемые за полиномиальное время с ограниченной погрешностью. При этом ограничения на ошибку, прямо скажем, довольно мягкие: не более одной трети от всех выданных ответов для любого набора входных данных. И даже при таких условиях, как уверены исследователи, большинство NP-задач и все NP-полные задачи останутся для квантовых компьютеров сложными с вычислительной точки зрения. Да, существует целый ряд проблем, которые для фоннеймановских машин вычислительно сложны, а для квантовых потенциально просты (если отвлечься от ограничений современного уровня развития квантовых вычислителей), включая, возможно, даже некоторые задачи за пределами NP-класса. Это уже упоминавшаяся факторизация больших чисел с помощью алгоритма Шора, который обеспечивает экспоненциальное ускорение вычислений по сравнению с лучшими классическими алгоритмами. Это также поиск конкретного элемента по алгоритму Гровера (GSA — Grover search algorithm), который на неструктурированных данных даёт квадратичное ускорение по сравнению с классическими методами: O(√n) против O(n). И так далее: «зоопарк» квантовых алгоритмов насчитывает уже несколько десятков — правда, за исключением алгоритмов Шора и Гровера, остальные более специфичны и имеют довольно узкие области применения.
Дополнительная диаграмма Эйлера, иллюстрирующая классы сложности в теоретической информатике при условии, что P не равно NP. Класс BQP способен выходить за пределы NP — иными словами, квантовый вычислитель может решать некоторые задачи быстрее, чем классические машины смогут даже проверить правильность ответа. Несмотря на обнадёживающие перспективы квантовых систем, определённые проблемы, особенно из категории NP-полных, по-прежнему не поддаются решению за полиномиальное время (источник: Scientific American)
⇡#Вежливый отказ
Весной 2024 года корпорация Google совместно с XPrize объявили о готовности выплатить 5 миллионов долларов тем, кто предложит (разумеется, не на уровне абстрактной идеи, а хотя бы минимально проработанного проекта) сценарии использования квантовых компьютеров. Речь идёт о новых сценариях, разумеется; помимо взлома традиционной криптографии (алгоритм Шора), поиска элемента в неупорядоченном массиве (алгоритм Гровера) и нескольких других уже реализованных квантовых алгоритмов. К концу 2025 года из 133 заявок, поданных на конкурс, организаторы отобрали семь со следующими заявленными направлениями исследований:
- Calbee Quantum (США) — ускоренное квантовое моделирование новых материалов, особенно для полупроводниковой отрасли и оптоэлектроники;
- Gibbs Samplers (Венгрия) — квантовое алгоритмическое моделирование процесса термализации квантовых систем при низких температурах, что в перспективе также позволит быстрее разрабатывать новые материалы с нужными характеристиками;
- Phasecraft (Великобритания) — использование квантовых симуляций для моделирования квантово-химических процессов; и снова речь идёт о создании новых материалов, но с акцентом на экологически чистые и одновременно эффективные солнечные элементы;
- Xanadu (Канада) — моделирование временной эволюции некоторых молекулярных процессов; в центре внимания здесь также находится поиск более производительных органических солнечных панелей;
- QuMIT (США) — разработка нового алгоритма, который существенно ускорил бы выявление сообществ в гиперграфах, что, в свою очередь, даст возможность точнее моделировать
