Кратко и по существу.
1) Основные понятия (с формулами)
- Кубит: двухуровневый квантовый регистр с состоянием в гильбертовом пространстве размерности 2:
$|\psi ⟩=\alpha |0⟩+\beta |1⟩,|\alpha {|}^2+|\beta {|}^2=1.$ - Суперпозиция: линейная комбинация базисных состояний; для $n$ кубитов общий вектор имеет размер $2^n$, что даёт экспоненциально большую конфигурационную пространство по сравнению с классическим битом.
$|\Psi ⟩=\sum _{x\in \{0,1{\}}^n}{c}_x|x⟩.$ - Запутанность: состояние нескольких кубитов, которое не раскладывается в тензорное произведение отдельных состояний; пример Белловского состояния
$|{\Phi }^{+}⟩=\frac{1}{\sqrt{2}}(|00⟩+|11⟩).$ Запутанность даёт неклассические корреляции и позволяет организовать интерференцию амплитуд между различными путями вычислений.
Механизм преимущества: операции над суперпозициями и запутанными состояниями позволяют осуществлять интерференцию амплитуд так, чтобы усилить вероятности правильных ответов и подавить неправильные; это не «параллельное вычисление» в классическом смысле — требуется аккуратно построить алгоритм и измерение.
2) Классы задач с потенциальным реальным преимуществом и почему
- Крипто- и число-теоретические задачи (факторизация, дискретный логарифм)
- Алгоритм Шора даёт экспоненциальное ускорение: факторизация $N$ за время полиномиальное в $\log N$.
- Причина: квантовый алгоритм использует квантовое преобразование Фурье и периодо-нахождение, эффективно реализуемые на квантовом компьютере.
- Практичность: требует больших, исправлено-работающих (FT) устройств; если появятся такие — реальное и существенное преимущество.
- Квантовое моделирование (молекулярная химия, материалы, квантовые поля)
- Эффективное моделирование квантовых систем может дать экспоненциальное сокращение ресурсов по сравнению с классикой в ряде задач (многие-частицы, коррелированные состояния).
- Причина: прямое отображение исследуемой квантовой системы в аппаратные кубиты без классического экспоненциального роста описания.
- Практичность: одно из наиболее убедительных и ближайших применений — ожидание реального выигрыша в химии/материалах для проблем, недоступных классическим методам.
- Поисковые/переборные задачи (негустая, неструктурированная выдача)
- Гровер даёт квадратичное ускорение: поиск в несортированной базе размера $N$ за $O(\sqrt{N})$ вместо $O(N)$.
- Причина: амплитудная инверсии/интерференция.
- Практичность: полезно при огромных $N$, но не даёт экспоненциального выигрыша; часто недостаточно, чтобы полностью заменить классические методы.
- Линейная алгебра для крупных разреженных матриц (HHL)
- HHL теоретически даёт экспоненциальную скорость при решении $Ax=b$ при условиях: матрица разрежена, хорошо обусловлена, можно быстро подготовить состояния $|b⟩$ и эффективно считывать нужные характеристики $x$.
- Практичность: сильные предпосылки и расходы на подготовку/чтение часто ограничивают реальное преимущество; применимо в узких задачах.
- Сэмплирование и «квантовое превосходство» (BosonSampling, random circuit sampling)
- Доказывают сложность классического моделирования конкретных распределений (орекуларные/сложностные результаты), что даёт основу для демонстраций квантового превосходства.
- Практичность: эти задачи демонстрируют скоростное превосходство, но имеют ограничённые практические приложения (они полезны как тесты аппаратуры и в статистических задачах, но не решают общеприменимые задачи).
- Комбинаторная оптимизация (QAOA, квантовый отжиг/annealing)
- Предлагают эвристические ускорения или лучшие приближения для некоторых класс-экземпляров задач (MaxCut, расписания).
- Причина: квантовые вараиионные схемы и мутации состояния через эволюцию могут находить хорошие решения быстрее в некоторых распределениях задач.
- Практичность: пока эмпирические и не дают доказанных общих скоростей; наиболее перспективны для NISQ-устройств как гибридные методы.
3) Ограничения и критерии «реального» преимущества
- Требования к аппаратуре: для многих алгоритмов (Шор, крупные симуляции) нужны масштабируемые, малошумные, исправляющие ошибки квантовые компьютеры.
- Предпосылки алгоритмов: HHL и др. требуют удобной подготовки входа/чтения выхода; без них теоретический выигрыш теряется.
- Сложностные пределы: нет доказательств, что BQP содержит NP-полные задачи; для многих NP-полных проблем ожидаются лишь полиномиальные/квазиполиномиальные улучшения (если есть).
- Практическая важность: экспоненциальный выигрыш в теории может быть незначительным на практике из‑за констант и накладных расходов.
Короткое резюме:
- Фундаментальные ресурсы: суперпозиция даёт пространство состояний $2^n$, запутанность обеспечивает неклассические корреляции и интерференцию амплитуд — это основа преимуществ.
- Реально выигрышны и наиболее убедительны: факторизация/крипто (при наличии FT-машин) и квантовое моделирование химии/материалов. Квадратичное ускорение Гровера полезно, но ограниченно. HHL/оптимизация/сэмплирование дают локальные/узкоспецифичные выигрыши при строгих условиях или как эвристики на NISQ.