Квантовые компьютеры по-прежнему остаются редкостью в наши дни, хотя новости о новых достижениях в этой области появляются регулярно. Например, в Ирландии был представлен шестикубитный вычислитель RacQ в формате стандартной 19-дюймовой серверной стойки, предназначенный для совместной работы с машинами фон Неймана в рамках единого дата-центра. А в Китае была усовершенствована до версии 4.0 фотонная квантовая система семейства Jiuzhang, которая вместо привычных кубитов использует 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) позволяет определить, как меняется время выполнения алгоритма или объём памяти, необходимой для вычислений по нему, в зависимости от размера входных данных. Последний аспект, кстати, особенно значим в контексте актуальной сегодня темы искусственного интеллекта: объёмы входных данных там поистине гигантские, поэтому оптимизации алгоритмов для решения ИИ-задач (включая привлечение квантовых компьютеров) в этой области уделяется особенно пристальное внимание.
Итак, в математике простыми — или, иначе говоря, практически разрешимыми — называют задачи, которые можно решить за время, возрастающее как полином от размера входного массива данных, обозначаемого символом n. Другими словами, если отвлечься от временных рамок: количество операций, которые машина должна выполнить для получения результата, прямо пропорционально объёму входных данных, возведённому в некоторую фиксированную степень (то есть тому самому полиному). К классу полиномиальных задач (polynomial — P-class problems) относятся, например, O(n), O(n2) и, в более общем виде, O(nk), где k — константа, причём, что критически важно, обычно не слишком большая, иначе само понятие «простоты» теряет чёткость. К числу простых в математическом смысле задач относятся все алгоритмы сортировки, проверка числа на делимость, определение связности графов и множество других. Компьютеры, работающие по архитектуре фон Неймана, справляются с такими задачами особенно успешно. Квантовые вычислители здесь, строго говоря, излишни: даже если и удастся выиграть во времени, затраты на создание многокубитной системы, способной решать многопараметрическую задачу низкополиномиального класса, заведомо превысят все допустимые границы. Возможно, когда-нибудь, если квантовые компьютеры достигнут такого же уровня развития, как современные классические, ситуация изменится, — но пока что фон Нейману остаётся фоннейманово.
Эйлерова диаграмма, демонстрирующая взаимосвязи между различными классами сложности вычислительных задач: слева — в допущении P ≠ NP, справа — P = NP (источник: Wikimedia Commons)
Класс сложности NP (недетерминированный полиномиальный) определяется несколько более замысловато: название «недетерминированный» он получил благодаря недетерминированной машине Тьюринга, ведь к NP относят именно те задачи, которые на таком устройстве решаются за полиномиальное время. Мы не будем углубляться в отличия детерминированной и недетерминированной машин Тьюринга; достаточно отметить, что недетерминированные модели расширяют вычислительные возможности, позволяя одновременно исследовать несколько путей решения (а это уже напрямую связано с квантовыми вычислениями). Классический пример NP-задачи, которая в принципе решается на детерминированной машине Тьюринга, но крайне медленно, — это известная задача коммивояжёра или уже упомянутое разложение большого числа на простые множители. В таких случаях способность машины на каждом шаге переходить сразу в несколько состояний значительно экономит время по сравнению с тем, что потребовалось бы детерминированной машине Тьюринга для той же задачи. Хотя время решения NP-задач растёт экспоненциально с увеличением объёма входных данных, как en, проверить полученный ответ (например, перемножив найденные простые числа и получив исходное) всё ещё можно за полиномиальное время. Существуют и NP-полные задачи — по сути, наиболее трудные в этом классе: к ним можно свести любую другую NP-задачу, опять же за полиномиальное время. Отдельный вопрос — совпадают ли классы сложности P и NP, но сейчас мы его не будем обсуждать: не зря это одна из семи важнейших проблем теоретической информатики, за строгое доказательство или обоснованное опровержение которых Математический институт Клэя назначил награду в миллион долларов.
Примечательно, что квантовый компьютер — даже тот пока недосягаемый промежуточный эталон с тысячей логических кубитов, который сделает бессмысленными большинство современных криптографических методов, — не станет универсальным решением для действительно трудных задач: ни для всех 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 (США) — разработка нового алгоритма, который значительно ускорил бы выявление сообществ в гиперграфах, что, в свою очередь, позволит точнее моделировать белок-белковые взаимодействия.
