Ответ на вопрос
Какие задачи потенциально выигрывают от квантового ускорения
- Факторизация целых чисел. Шор показал полиномиальный алгоритм для факторизации и дискретного логарифма вместо субэкспоненциальных классических алгоритмов: квантовая сложность примерно \(O(\mathrm{poly}(\log N))\), тогда как лучший классический алгоритм — решето числового поля — имеет сложность типа \(\displaystyle \exp\!\left((c+o(1))(\log N)^{1/3}(\log\log N)^{2/3}\right)\). Практический вывод: при наличии достаточно большого и исправно работающего квантового компьютера — прямая угроза современным схемам асимметричного шифрования.
- Симуляция квантовых систем. Квантовые компьютеры естественно моделируют эволюцию квантовых гамильтонианов. Классические ресурсы растут экспоненциально с размером системы (примерно \(O(2^n)\) для \(n\) кубитов), тогда как квантовые алгоритмы для цифровой симуляции могут работать за полиномиальное время по \(n\) и времени эволюции: примерно \(\mathrm{poly}(n,t,1/\varepsilon)\). Это даёт реальную перспективу ускорения в квантовой химии, материаловедении и моделях многих тел.
- Поисковые и неопределённые задачи (квази-структурированные). Для неструктурного поиска Гровер даёт квадратичное ускорение: \(O(\sqrt{N})\) против классического \(O(N)\). Квадратичный выигрыш полезен, но далеко не экспоненциален.
- Оптимизация и приближённые алгоритмы. Гибридные NISQ-алгоритмы (QAOA, квантовый отжиг) и квантовые схемы отжигания могут давать эмпирические преимущества для некоторых комбинаторных задач и задач оптимизации, но строгих общих теорем о выигрыше пока нет — преимущество зависит от структуры задач и качества аппаратуры.
- Линейные уравнения и некоторые задачи анализа данных. Алгоритм HHL даёт потенциально экспоненциальную зависимость от размерности в идеализированном случае (выход — квантовое состояние решения), но реальная сложность зависит от обусловленности матрицы \(\kappa\), разреженности \(s\) и затрат на подготовку/чтение данных: типично \(\mathrm{poly}(\log N,\kappa,s)\).
- Специальные задачи выборки/симуляции. Задачи типа boson sampling, задачи генерации квантовых распределений и некоторые выборочные задачи могут демонстрировать ускорение, служа демонстрацией квантового превосходства в узкой области.
Ограничения квантовых алгоритмов
- Не универсальный экспоненциальный выигрыш. Большинство задач не получают экспоненциального ускорения; требуются специфическая структура данных или задачи (например, периодичность для Шора). Для неструктурированного поиска Гровер — оптимален по сложности.
- Ввод/вывод и представление данных. Многие квантовые алгоритмы работают с квантовыми состояниями, а не с явным классическим вектором. Подготовка входных данных и чтение выходных результатов могут требовать \(O(N)\) классических ресурсов, что нивелирует выигрыш.
- Зависимость от параметров и точности. Сложность часто растёт с ухудшением обусловленности \(\kappa\) и требуемой точности \(\varepsilon\) (например, полиномиально или даже линейно/квазиэкспоненциально), что снижает практический выигрыш.
- Алгоритмические предположения и де-квантование. Часто после появления квантового алгоритма появляются классические «квантово-вдохновлённые» методы, которые сокращают разрыв. Не все заявленные ускорения устойчивы к таким улучшениям.
- Ограниченность NISQ-эпохи. На шумных недокорректированных устройствах (NISQ) можно запускать только неглубокие цепочки гейтов и небольшие числа кубитов; многие полезные алгоритмы требуют глубокой и длинной последовательности операций.
Основные инженерные препятствия для практического применения
- Шум и декогеренция. Время когерентности \(T_2\) и ошибки гейтов ограничивают длину допустимого алгоритма. Для полезных алгоритмов требуются либо намного лучшие времена когерентности, либо масштабная коррекция ошибок.
- Коррекция ошибок и оверхед. Практически полезная исправляемость ошибок (например, поверхность-код) требует большого множества физических кубитов на одну логическую: оценки варьируются, типично \( \sim 10^3\!-\!10^5 \) физических кубитов на одну логическую в зависимости от целевой скорости ошибок и алгоритма. Это делает нужны миллионы физических кубитов для сложных задач (напр., факторизация длинных чисел).
- Масштабирование и связность. Нужны плотная интеграция множества кубитов, высокая однородность качества, контроллеры и межсоединения — всё это трудно промышленно масштабировать.
- Криогеника и электроника. Многие реализации требуют милликенновых температур и сложной аппаратуры для управления и чтения, а интеграция классической электроники с квантовой в криоусловиях остаётся инженерным вызовом.
- Точность и калибровка. Высокие требования к точности гейтов (\(
Еще