Квантовые вычисления и автоматы

RSA-шифрование держится на том, что факторизация 2048-битного числа занимает 10^15 лет. Алгоритм Шора на квантовом компьютере сделает это за часы. NIST в 2024 году стандартизировал постквантовые алгоритмы - криптографическая миграция уже идёт.

• NIST 2024: CRYSTALS-Kyber и CRYSTALS-Dilithium - первые стандарты постквантовой криптографии
• Google Sycamore (2019): случайная выборка схемы - первая демонстрация квантового превосходства
• IBM Quantum: доступ к квантовым процессорам через облако, используется для симуляции химических реакций
• Хайп-цикл: реальная польза NISQ сейчас - симуляция молекул для фармацевтики и материаловедения

Квантовые конечные автоматы

Квантовый конечный автомат (QFA) - обобщение DFA: вместо одного состояния - суперпозиция состояний. Переходы - унитарные матрицы (обратимые преобразования амплитуд). Измерение - проекция суперпозиции на классическое состояние.

QFA строго мощнее DFA по числу состояний: язык {a^p : p - простое число} требует экспоненциальное число состояний в DFA, но O(log p) кубит в QFA. Однако QFA не мощнее DFA по распознаваемым языкам - только по эффективности.

Квантовая машина Тьюринга и BQP

Квантовая машина Тьюринга (QTM) - обобщение TM: переходная функция производит суперпозицию конфигураций. Класс BQP (Bounded-error Quantum Polynomial time) - задачи, решаемые QTM за полиномиальное время с вероятностью ошибки не более 1/3.

• P ⊆ BQP ⊆ PSPACE - квантовые вычисления между P и PSPACE
• Алгоритм Шора: факторизация за O((log N)^3) - NP не разрушает, но PKI под угрозой
• Алгоритм Гровера: квадратичное ускорение поиска - не взламывает NP-completeness
• BQP vs NP: открытая проблема. Большинство считает что BQP не содержит NP-hard
• Квантовое превосходство (Google Sycamore, 2019): задача, не имеющая практического применения

BQP и квантовые ограничения

BQP - основной класс квантовой вычислимости. Инвариант: ошибка не более 1/3 (амплифицируема повторением до 1/2^k). Соотношения с классическими классами: P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE.

Квантовое преимущество: реальность vs. хайп

Квантовое превосходство (supremacy) - демонстрация квантового компьютера на задаче, недоступной классическому за разумное время. Google Sycamore (2019): выборка из random circuit за 200 секунд, классически якобы 10000 лет. IBM оспорил: за 2.5 дня на Summit.

• Текущий NISQ (Noisy Intermediate-Scale Quantum) - 1000 физических кубит без коррекции ошибок
• Логический кубит требует ~1000 физических для fault-tolerant вычислений
• Алгоритм Шора для RSA-2048: ~4000 логических кубит = ~4 млн физических
• IBM roadmap: 100k кубит к 2033, но error correction не гарантирован
• Реальная польза сейчас: симуляция молекул (Вариационный квантовый eigenсolver)

Итоги

• QFA мощнее DFA по числу состояний, но не по классу языков
• BQP - квантовый аналог P: P ⊆ BQP ⊆ PSPACE, отношение с NP неизвестно
• Шор факторизует за O((log N)^3), Гровер ускоряет поиск до O(sqrt(N))
• NISQ-эра: нет коррекции ошибок, fault-tolerant далеко, постквантовая криптография актуальна уже

Связанные темы

Квантовые вычисления связаны с классической теорией сложности и криптографией:

• Классы P и NP — BQP добавляется к карте сложности: P ⊆ BQP ⊆ PSPACE, но BQP vs NP открыто
• Случайные алгоритмы — BPP - классический аналог BQP с монетой, BQP предположительно строго мощнее
• Конечные автоматы — QFA расширяет DFA амплитудами - экспоненциальное сжатие числа состояний
• Криптография — Алгоритм Шора взламывает RSA и ECC - постквантовые стандарты NIST 2024

Вопросы для размышления

• Если BQP содержит задачи вне P, почему это не доказывает P ≠ NP?
• Почему квадратичное ускорение Гровера не делает NP-complete задачи полиномиальными?
• Какие классические алгоритмы нужно изменить в TLS 1.3 для постквантовой безопасности?

Связанные уроки

• qc-01