«Многие в IT слышали, что квантовые компьютеры могут всё взломать, и на этом их познания заканчиваются. Но на самом деле квантовая сложность, это не про конкретные атаки, а про фундаментальное переопределение того, что мы считаем «вычислимым за разумное время». И самое интересное здесь — не то, что BQP ломает RSA, а его загадочные отношения с классической иерархией сложности: он где-то между P и NP, но не содержит NP и, вероятно, не содержится в ней. Это создаёт совершенно новую карту вычислительного мира, где некоторые задачи, неподъёмные для классических компьютеров, становятся тривиальными для квантовых, но не все, и это разделение — ключ к пониманию реальных перспектив технологии.»
От классической сложности к квантовым вычислениям
Чтобы понять место квантовых классов в общей картине, нужно отталкиваться от классической теории сложности. Класс P объединяет задачи, решаемые на классической машине Тьюринга за полиномиальное время. Класс NP — задачи, где проверка готового решения выполняется за полиномиальное время, но поиск решения может быть экспоненциально сложным. Принципиальный вопрос P против NP — станет ли когда-нибудь поиск решений таким же быстрым, как их проверка.
Квантовые вычисления меняют правила игры. Классический бит, это 0 или 1. Квантовый бит (кубит) может находиться в суперпозиции состояний |0⟩ и |1⟩, что формально описывается как α|0⟩ + β|1⟩, где α и β — комплексные амплитуды. Коллективное состояние n кубитов описывается суперпозицией 2ⁿ базисных состояний. Это даёт потенциальный параллелизм, но с ключевым ограничением: получить информацию можно только через измерение, которое «схлопывает» квантовое состояние в одно классическое значение с вероятностью, определяемой квадратом модуля амплитуды. Поэтому нельзя просто «прочитать» все 2ⁿ значений одновременно — нужны алгоритмы, которые через интерференцию амплитуд усиливают вероятность получить правильный ответ.
Класс BQP: квантовый аналог BPP
Класс Bounded-error Quantum Polynomial time (BQP), это краеугольный камень квантовой теории сложности. Он формализует множество задач, которые могут быть эффективно решены на квантовом компьютере. Если задача лежит в BQP, то существует квантовый алгоритм, который для любого входа длины n даёт правильный ответ с вероятностью не менее 2/3, а время его работы ограничено полиномом от n. Вероятность ошибки (1/3) не является магической константой — её можно экспоненциально уменьшить до пренебрежимо малой за счёт повторения алгоритма и мажоритарного голосования.
Важнейшие практические алгоритмы, определившие интерес к области, принадлежат BQP:
- Алгоритм Шора для факторизации чисел и решения задачи дискретного логарифма. Он решает задачу за полиномиальное время, тогда как лучшие известные классические алгоритмы — субэкспоненциальные. Именно это лежит в основе угрозы для RSA и Эль-Гамаля.
- Алгоритм Гровера для поиска в неструктурированной базе данных из N элементов. Он даёт квадратичное ускорение (O(√N) против O(N)), что полезно, но не является экспоненциальным прорывом для всех задач.
Положение BQP в классической иерархии — предмет активных исследований. Известно, что P ⊆ BPP ⊆ BQP. При этом BQP содержится в классе PSPACE (задачи, решаемые с полиномиальной памятью). Самый интригующий нерешённый вопрос — соотношение BQP и NP. Существует консенсус, что BQP не содержит весь класс NP. То есть маловероятно, что квантовый компьютер сможет за полиномиальное время решать, например, задачу выполнимости булевой формулы (SAT) для любого экземпляра. Квантовые вычисления дают мощное, но не всесильное ускорение.
Класс QMA: квантовый аналог NP
Класс Quantum Merlin-Arthur (QMA), это естественное обобщение NP на квантовый случай. В модели NP проверяющая сторона (Артур) за полиномиальное время проверяет предоставленное свидетелем (Мерлином) классическое доказательство. В QMA Мерлин может отправить Артуру квантовое состояние (набор кубитов) в качестве доказательства. Артур, обладающий квантовым компьютером, выполняет полиномиальную проверку этого состояния. Задача принадлежит QMA, если для верных утверждений существует квантовое доказательство, которое Артур примет с высокой вероятностью, а для неверных — никакое доказательство не сможет обмануть Артура с достаточной вероятностью.
Канонический полный пример задачи для QMA — задача локальной гамильтоновости. По сути, это квантовый аналог задачи выполнимости (SAT). Дана локальная гамильтонова система (описывающая, например, взаимодействие спинов в решётке), вопрос заключается в том, лежит ли её наименьшее собственное значение (энергия основного состояния) ниже определённого порога. Доказательство того, что эта задача QMA-полна, является фундаментальным результатом, аналогичным полноте SAT для NP.
Соотношение QMA с другими классами строгое: QMA содержит как NP, так и BQP. Это логично: классическое доказательство можно представить как частный случай квантового, а задачу из BQP можно проверить, просто перевычислив её на предоставленном пустом доказательстве. При этом QMA содержится в PP (класс задач, решаемых вероятностной машиной Тьюринга с вероятностью >1/2) и, следовательно, в PSPACE. Иерархия QMA, подобно классической полиномиальной иерархии, допускает расширение до QMA(2), где Мерлин предоставляет два некоррелированных квантовых свидетельства, и считается, что этот класс значительно мощнее.
Иерархия классов и вычислительная мощность
Сравнение квантовых и классических классов создаёт новую многомерную карту вычислительной сложности.
| Класс | Тип вычислений | Описание | Примерная позиция |
|---|---|---|---|
| P | Детерминированные, классические | Задачи, решаемые быстро и точно. | Внутри BQP |
| BPP | Вероятностные, классические | Задачи, решаемые быстро с малой ошибкой. | Содержится в BQP |
| BQP | Вероятностные, квантовые | Задачи, эффективно решаемые квантовым компьютером. | Между BPP и PSPACE, не содержит NP |
| NP | Детерминированные, классические (проверка) | Задачи, где решение можно быстро проверить. | Содержится в QMA |
| QCMA | Классические доказательства, квантовая проверка | Аналог NP, но проверка на квантовом компьютере. | Между NP и QMA |
| QMA | Квантовые доказательства, квантовая проверка | Квантовый аналог NP. | Содержит NP и BQP, внутри PP |
Из этой таблицы видно, что квантовые вычисления не отменяют классическую иерархию, а надстраивают над ней новую структуру. Существование промежуточных классов вроде QCMA (где доказательство классическое, а проверка квантовая) показывает, что источник мощности может быть разным: иногда он в квантовом доказательстве, иногда — только в квантовой проверке.
Что это означает на практике?
Понимание этих абстрактных классов имеет прямые последствия для прикладных областей, особенно для информационной безопасности.
Во-первых, оно задаёт границы угроз. Поскольку NP, скорее всего, не содержится в BQP, не все сложные задачи падут перед квантовым компьютером. Симметричное шифрование (AES) с увеличением ключа останется стойким — атака Гровера даёт лишь квадратичное ускорение перебора. Угроза нависла в первую очередь над асимметричной криптографией, основанной на факторизации и дискретном логарифме, так как для них существует алгоритм Шора из класса BQP.
Во-вторых, оно определяет направления постквантовой криптографии. Новые алгоритмы стремятся основываться на задачах, которые считаются сложными и для квантовых компьютеров. Многие кандидаты (например, на решётках, кодах, многомерных квадратичных уравнениях) опираются на проблемы, которые, как полагают, лежат за пределами BQP, а некоторые даже являются NP-полными в худшем случае. Хотя это не гарантирует безопасности (NP-полнота не означает сложности на средних входах), это даёт более надёжную теоретическую основу, чем факторизация.
В-третьих, для задач оптимизации и машинного обучения, часто сводимых к NP-трудным проблемам, квантовые компьютеры не станут волшебной палочкой. Алгоритмы вроде квантового приближённого оптимизационного алгоритма (QAOA) могут давать ускорение на некоторых экземплярах, но не гарантируют глобального решения за полиномиальное время для всех случаев. Это охлаждает излишне радужные ожидания.
Открытые вопросы и будущее
Теория квантовой сложности далека от завершения. Ключевые нерешённые проблемы продолжают будоражить научное сообщество.
- BQP против PH: Полиномиальная иерархия (PH) — обобщение классов P, NP, co-NP и их оракульных расширений. Доказано, что если BQP содержится в PH (что кажется правдоподобным), то эта иерархия коллапсирует до определённого уровня. Это сильный аргумент в пользу того, что BQP находится за пределами PH, то есть квантовые компьютеры способны решать некоторые задачи, недоступные для классических компьютеров даже с неограниченными ресурсами на угадывание и проверку.
- Оракульное разделение: Существуют оракулы (условные чёрные ящики), относительно которых BQP не содержится в PH, и оракулы, относительно которых P = NP, но BQP != P. Эти результаты показывают, что наши текущие методы доказательств недостаточны для разрешения этих вопросов в реальном, неоракульном мире — нужны принципиально новые идеи.
- Преимущество без структуры: Алгоритм Гровера демонстрирует, что даже для полностью неструктурированной задачи поиска квантовый компьютер даёт квадратичное ускорение. Это считается оптимальным. Но почему именно квадратичное, а не большее? Это следует из свойств унитарной эволюции и симметрии задачи — глубокий результат, показывающий фундаментальные ограничения квантовых алгоритмов на неструктурированных пространствах.
Развитие теории будет напрямую зависеть от прогресса в создании реальных квантовых устройств. Каждый новый алгоритм или протокол заставляет пересматривать границы классов. Возможно, появление квантовых компьютеров среднего масштаба (NISQ) породит новые, промежуточные классы сложности, учитывающие шум и ограниченную глубину схем. Изучение этой иерархии — не просто академическое упражнение, а инструмент для прогнозирования того, какие вычислительные барьеры падут, а какие останутся незыблемыми в квантовую эпоху.