Курс «Квантовые вычисления». Глава 9. Квантовая сложность: что могут и чего не могут квантовые компьютеры

Курс «Квантовые вычисления»

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

9.1. Напоминание: P, NP, BPP

P — класс задач принятия решений, решаемых детерминированно за полиномиальное время. Полиномиальность — асимптотическое понятие, а не синоним практичности: алгоритм с огромной степенью может быть бесполезен, тогда как экспоненциальный алгоритм работает на малых входах. NP состоит из задач, для положительного ответа которых существует полиномиально проверяемый сертификат; SAT, гамильтонов цикл и раскраска графа дают стандартные примеры. Гипотеза P ≠ NP утверждает отсутствие полиномиальных алгоритмов для NP-полных задач, но сама по себе не доказывает экспоненциальную нижнюю оценку. BPP допускает случайность и ошибку не более 1/3, которую можно уменьшить независимыми повторами.

Для подходящей формулировки задачи принятия решений факторизация лежит в NP ∩ coNP. Она не известна как NP-полная; если бы NP-полная задача принадлежала coNP, то получилось бы NP = coNP, что считается маловероятным. Алгоритм Шора использует специальную алгебраическую структуру факторизации, а не решает произвольную задачу NP.

9.2. Класс BQP

BQP (bounded-error quantum polynomial time) — класс задач принятия решений, решаемых равномерным семейством квантовых схем полиномиального размера с ошибкой не более 1/3. Константа 1/3 несущественна: повторение и голосование уменьшают ошибку экспоненциально. Известны включения

P ⊆ BPP ⊆ BQP ⊆ PSPACE

• BPP ⊆ BQP: обратимая квантовая схема моделирует классическое вычисление, а измерение приготовленных суперпозиций даёт случайные биты.
• BQP ⊆ PSPACE: квантовую схему можно моделировать с экспоненциальным временем, повторно вычисляя нужные амплитуды и используя лишь полиномиальную память. Следовательно, квантовая модель не решает невычислимые задачи.
• Неизвестно, строго ли BPP ⊂ BQP. Факторизация находится в BQP и не имеет известного полиномиального классического алгоритма, но это свидетельство, а не доказательство разделения классов.

9.3. BQP и NP: главный вопрос

Решают ли квантовые компьютеры NP-полные задачи за полиномиальное время? Точный ответ неизвестен.

• Доказательство NP ⊄ BQP сразу повлекло бы P ≠ NP, поскольку P ⊆ BQP. Большинство исследователей ожидает, что NP не содержится в BQP, но безусловного результата нет.
• Теорема BBBV ограничивает только доступ через неструктурированный оракул. Она исключает полиномиальное ускорение полного перебора как универсальный метод, но не исключает неизвестный алгоритм, использующий структуру явной NP-полной задачи.
• Гровер даёт O(2^n/2) проверок для SAT по n переменным. Квантовое усиление некоторых классических эвристик и алгоритмов поиска возможно при обратимой реализации, однако накладные расходы и лучшие специализированные классические алгоритмы нужно учитывать отдельно.

Обратное включение BQP ⊆ NP также не доказано и не опровергнуто. Относительно специально построенных оракулов можно разделить эти классы, что служит свидетельством их возможной несравнимости, но не решает обычный вопрос без оракула. Задачи сэмплирования из экспериментов по квантовому преимуществу относятся к классам распределительных задач, а не являются непосредственными примерами языков из BQP ∖ NP.

9.4. Каталог: где ускорение есть и где его нет

Следующие категории требуют разных уровней уверенности.

Суперполиномиальный разрыв доказан в модели запросов или ожидается при стандартных предположениях:

• задача Саймона имеет доказанное экспоненциальное разделение запросов; абелева задача скрытой подгруппы объединяет её с периодическими подпрограммами Шора;
• факторизация и дискретный логарифм решаются квантово за полиномиальное время, а лучшие известные классические алгоритмы суперполиномиальны; классическая нижняя оценка для них не доказана;
• моделирование общих локальных квантовых динамик является естественной BQP-задачей, но конкретные химические и физические экземпляры могут иметь эффективные классические приближения;
• HHL и родственные линейно-алгебраические алгоритмы дают сильные оценки при разреженности, хорошей обусловленности и оракульном доступе к данным, а на выходе обычно позволяют оценивать наблюдаемые, но не читать весь вектор решения.

Квадратичное ускорение даёт неструктурированный поиск и усиление амплитуды, если оракул и исходную процедуру можно реализовать когерентно с приемлемой стоимостью.

Общего ускорения не известно для сортировки произвольных явно загруженных данных, индексных запросов, веб-обслуживания и большинства обычных потоковых вычислений. Если само чтение или запись N элементов обязательно, оно уже стоит Ω(N). Не известно и полиномиального квантового алгоритма для общей NP-полной оптимизации. Практическая архитектура поэтому рассматривает квантовый процессор как ускоритель отдельных подзадач рядом с классическим компьютером.

9.5. «Квантовое превосходство» и «квантовая полезность»

Квантовым вычислительным преимуществом обычно называют эксперимент, в котором квантовое устройство лучше доступных классических методов по заранее определённой метрике. Демонстрации случайного сэмплирования, начиная с эксперимента Google 2019 года, показали масштабирование задач, специально выбранных для трудности классического воспроизведения. Сравнение остаётся движущейся целью: классические алгоритмы симуляции после публикаций улучшаются, а проверка распределения требует статистических тестов и вычислительных предположений.

Практическая полезность требует дополнительно значимой задачи, нужной точности, полной стоимости подготовки и проверки и сравнения с лучшим классическим рабочим процессом. К 2025–2026 годам появились полезные квантовые сервисы сертифицированной случайности и новые заявления о преимуществе в квантовой динамике, отжиге, химии и обучении. Они опираются на разные модели, метрики и допущения, а общепринятой границы «полезного квантового компьютера» пока нет. Поэтому вместо общего ярлыка нужно спрашивать: как сформулирована задача; включены ли ввод, вывод и проверка; каков лучший воспроизводимый классический базис; сохраняется ли преимущество по времени, энергии, стоимости или точности после учёта всех ресурсов.

9.6. Мифы: краткий определитель

• «Квантовый компьютер перебирает все варианты параллельно» — нет: суперпозиция не читается (глава 2), выигрыш даёт интерференция на структуре задачи (главы 5–7), а чистый перебор ускоряется лишь в корень (глава 8).
• «Квантовые компьютеры сделают обычные устаревшими» — нет: для повседневных вычислений ускорения нет (9.4); это сопроцессор.
• «Квантовые компьютеры решат NP-полные задачи за полиномиальное время» — такого алгоритма не известно; невозможность также не доказана (9.3).
• «Квантовые компьютеры вычисляют невычислимое» — нет: BQP ⊆ PSPACE (9.2).
• «Спорность текущей полезности отменяет долгосрочную угрозу» — нет: алгоритм Шора доказан, ниже-пороговое подавление логических ошибок показано экспериментально, а миграция криптографии занимает годы (главы 11–14).

Итоги главы

• BQP — «эффективно вычислимое квантово»; P ⊆ BPP ⊆ BQP ⊆ PSPACE; ничего невычислимого квантовый компьютер не вычисляет.
• Факторизация свидетельствует в пользу BPP ≠ BQP, но не доказывает его; для NP-полных задач известен квадратичный неструктурированный поиск, а полиномиальный квантовый алгоритм не найден.
• Отношение BQP и NP неизвестно; оракульные результаты поддерживают гипотезу о несравнимости, но задачи сэмплирования нельзя напрямую использовать как языки вне NP.
• Экспериментальное преимущество и практическая полезность требуют разных критериев; каждое заявление оценивают вместе с классическим базисом, вводом-выводом и проверкой.

Упражнения

1. Объясните, почему факторизация принадлежит NP и coNP одновременно. Указание: сертификат для coNP — полное разложение числа на простые множители плюс доказательства простоты.
2. Покажите, что BQP замкнут относительно композиции: полиномиальное число вызовов BQP-подпрограммы из BQP-алгоритма остаётся в BQP. Где в этом рассуждении используется усиление вероятности успеха повторами?
3. Задача Саймона (глава 5) даёт экспоненциальное разделение квантовых и классических вычислений — почему это не доказывает BPP ≠ BQP? В чём принципиальная разница между оракульным разделением и разделением классов?
4. Приведите по одному примеру задачи из каждой клетки таблицы: (а) в P; (б) в BQP, но предположительно не в BPP; (в) NP-полной; (г) вне NP и предположительно вне BQP. Указание к (г): вспомните классические неразрешимые и PSPACE-полные задачи.
5. Коллега предлагает «решать SAT Гровером»: N = 2ⁿ назначений переменных, квадратичное ускорение. Лучшие классические SAT-солверы на промышленных формулах работают несравненно быстрее перебора. Сформулируйте, какое сравнение корректно и почему «ускорение перебора» может проиграть «неускоренной» классической эвристике.
6. Разберите заявление (реальный тип пресс-релиза): «наш квантовый компьютер решил за 200 секунд задачу, требующую 10 000 лет на суперкомпьютере». Какие три вопроса из раздела 9.5 нужно задать и как на них исторически отвечалось для сэмплинговых демонстраций?

Ответы и указания. 1: для утверждения о наличии делителя сертификатом служит сам делитель; для отрицательного ответа в пороговой версии можно предъявить полное разложение и проверяемые свидетельства простоты множителей. 2: если внешняя схема делает q(n) вызовов, ошибку каждого вызова сначала уменьшают до O(1/q(n)) повторением и большинством; по объединённой границе суммарная ошибка остаётся постоянной, а накладной множитель логарифмичен. 3: задача Саймона разделяет квантовую и классическую сложность запросов относительно специально выбранного оракула. Явно заданный код функции может открыть классическому алгоритму структуру, скрытую чёрным ящиком; оракульное разделение не является разделением обычных BPP и BQP. 4: например, (а) умножение матриц; (б) факторизация — в BQP и лишь предположительно вне BPP; (в) SAT; (г) истинность полностью квантифицированных булевых формул — PSPACE-полная и предположительно вне BQP, либо проблема остановки — вообще неразрешимая. 5: нужно сравнивать полное время и ресурсы квантовой реализации с лучшим классическим SAT-алгоритмом на тех же распределениях экземпляров, а не только с 2ⁿ; обратимость, память и глубина оракула могут перекрыть корневой выигрыш. 6: выясняют точную задачу и метрику, лучший воспроизводимый классический базис и способ проверки. В сэмплинговых экспериментах задача была специально сконструирована, классические оценки затем заметно улучшались, а корректность подтверждалась статистическими тестами для доступных режимов, а не чтением полного распределения.

Литература к главе

1. M. Nielsen, I. Chuang, "Quantum Computation and Quantum Information," гл. 3.2, 4.5.5. Cambridge University Press, 2010.
2. C. Bennett, E. Bernstein, G. Brassard, U. Vazirani, "Strengths and Weaknesses of Quantum Computing," 1997. arxiv.org/abs/quant-ph/9701001
3. S. Aaronson, "Quantum Computing Since Democritus," Cambridge University Press, 2013.
4. J. Preskill, "Quantum Computing in the NISQ era and beyond," 2018. arxiv.org/abs/1801.00862
5. F. Arute et al., "Quantum Supremacy Using a Programmable Superconducting Processor," Nature 574, 2019. doi.org/10.1038/s41586-019-1666-5
6. M. Bierhorst et al., "Traceable Random Numbers from a Non-local Quantum Advantage," Nature, 2025. doi.org/10.1038/s41586-025-09054-3

Предыдущая глава || Содержание курса || Следующая глава