Чего квантовые компьютеры НЕ могут

Самый полезный навык — отличать реальные возможности от хайпа.

Квантовое превосходство касается узкого класса задач; для большинства вычислений квантовый компьютер не быстрее классического, а часто и медленнее.

Миф 1: «пробует все варианты одновременно и выдаёт правильный»

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

Миф 2: «ускоряет любую задачу»

Известных задач с квантовым преимуществом — горстка: факторизация (Шор), поиск (Гровер, лишь квадратично), симуляция квантовых систем, несколько задач линейной алгебры с оговорками. Для сортировки, сложения, рендеринга, веб-сервера, баз данных квантовый компьютер бесполезен или хуже. Сравним честно ожидаемый порядок ускорения:

tasks = [
    ('Факторизация (Шор)',        'экспоненциальное', 'огромное'),
    ('Поиск без структуры (Гровер)', 'квадратичное',  'умеренное'),
    ('Симуляция квант. химии',    'экспоненциальное', 'огромное'),
    ('Сортировка массива',        'нет',              'нет'),
    ('Сложение чисел',            'нет',              'нет'),
    ('Веб-сервер / БД',           'нет',              'нет'),
]
for name, speedup, gain in tasks:
    print('%-30s ускорение: %-15s выгода: %s' % (name, speedup, gain))

Вывод:

Факторизация (Шор)             ускорение: экспоненциальное выгода: огромное
Поиск без структуры (Гровер)   ускорение: квадратичное    выгода: умеренное
Симуляция квант. химии         ускорение: экспоненциальное выгода: огромное
Сортировка массива             ускорение: нет             выгода: нет
Сложение чисел                 ускорение: нет             выгода: нет
Веб-сервер / БД                ускорение: нет             выгода: нет

Миф 3: «бесконечная память в кубитах»

n кубитов описываются 2^n амплитудами, но записать и прочитать столько данных нельзя: на вход и выход доступно лишь n битов. Нельзя «загрузить» в кубиты гигантскую базу и мгновенно её обработать — узкое горло ввода-вывода убивает выгоду. Это разрушает мечты о «квантовом Big Data» в наивной форме.

Миф 4: «уже скоро заменят обычные компьютеры»

Нет даже в проекте. Квантовый компьютер — специализированный сопроцессор для узких задач, который вызывают из классической программы, как сегодня вызывают GPU. Управляет всем по-прежнему классический компьютер: готовит цепь, отправляет, собирает результаты, обрабатывает статистику. Ваш ноутбук останется классическим.

Как работает под капотом (теория сложности)

Строго говоря, класс задач, которые квантовый компьютер решает эффективно, называется BQP. Известно, что он содержит факторизацию, но не доказано, что он шире классического P или что он включает NP-полные задачи. Распространённое заблуждение, будто квантовый компьютер решает NP-полные задачи (коммивояжёр, SAT) «в лоб» перебором — почти наверняка неверно: Гровер даёт лишь квадратичное ускорение перебора, а не волшебное решение. Это фундаментальный, а не временный предел.

Частые ошибки

«Квантовый компьютер решит любую NP-задачу мгновенно». Нет — даже Гровер лишь квадратичен.
«В кубиты влезет вся база данных». Ввод-вывод ограничен n битами.
«Он заменит CPU». Это узкий сопроцессор под классическим управлением.

Итог

Преимущество есть лишь у узкого класса задач; для большинства его нет.
Параллелизм без интерференции и узкое горло ввода-вывода ограничивают мощь.
Это сопроцессор, а не замена классическому компьютеру; NP-полное «в лоб» он не решает.