Дискретная математика
Основы квантовой теории информации
Как информация ведёт себя в квантовом мире - и почему алгоритм Шора угрожает безопасности всего интернета?
- **Google Quantum AI:** Sycamore (53 кубита, 2019) - 200 секунд vs. 10 000 лет на классическом Summit
- **Квантовое распределение ключей:** BB84 коммерчески используется Toshiba и ID Quantique
- **Квантовые сети:** спутник Micius - квантовая телепортация на 1200 км (2017), основа квантового интернета
- **Угроза RSA:** алгоритм Шора факторизует RSA-2048 при 4000+ логических кубитах - двигатель пост-квантовой криптографии
Предварительные знания
- Линейная алгебра над C (комплексные пространства)
- Унитарные матрицы и операторы
- Энтропия Шеннона
- Дискретное преобразование Фурье
Кубиты и запутанность
В 2019 году Google Sycamore за 200 секунд выполнил вычисление, которое заняло бы 10 000 лет на классическом суперкомпьютере Summit. Секрет - суперпозиция: 50 кубитов кодируют одновременно 2^50 = 10^15 состояний. Кубит - это не просто 'бит 0 или 1', а единичный вектор в гильбертовом пространстве C^2, и линейная структура открывает экспоненциальный параллелизм.
BB84 (Беннетт-Брассард, 1984) - первый протокол квантового распределения ключей. Перехват квантового канала неизбежно вносит ошибки (теорема о запрете клонирования), обнаруживаемые Алисой и Бобом. Toshiba и ID Quantique коммерчески применяют BB84 в банковской криптографии.
Что означает '1 ebit' запутанности для состояния Белла |Phi+>?
Квантовые вентили
Квантовый вентиль - унитарный оператор на n кубитах. Аналог классических AND/OR/NOT, но обратимый: U^dagger U = I. Любое квантовое вычисление - последовательность вентилей и измерений. Универсальный набор {H, T, CNOT} достаточен для аппроксимации любого унитарного оператора с произвольной точностью - аналог теоремы Поста о функциональной полноте.
Квантовая телепортация (Беннетт и др., 1993): передача состояния кубита с помощью 1 ebit запутанности и 2 классических битов. Не нарушает СТО: классический канал необходим, скорость ограничена световой. В 2017 году спутник Micius продемонстрировал телепортацию на 1200 км.
Почему {H, T, CNOT} - универсальный набор квантовых вентилей?
Квантовые алгоритмы: Шор и Гровер
В 1994 году Питер Шор показал: квантовый компьютер факторизует n-битное число за O(n^3) вместо exp(n^{1/3}) классических операций. Это угроза всей криптографии RSA, защищающей банкинг и TLS. В 1996 году Лов Гровер дал квадратичное ускорение для перебора: O(sqrt(N)) вместо O(N). Эти два алгоритма - демонстрация того, что квантовые компьютеры превосходят классические не количественно, а качественно.
Квантовая информация в математике и физике
Квантовая теория информации связывает дискретную математику, анализ и фундаментальную физику.
- Теория кодирования — Квантовые коды исправления ошибок (CSS-коды) строятся из пар классических линейных кодов над GF(2)
- Теория сложности — Класс BQP включает факторизацию (Шор) и дискретный логарифм - вне BPP при стандартных предположениях
- Криптография — Угроза RSA при 4000+ логических кубитах; пост-квантовая криптография (lattice-based, code-based) - ответ на эту угрозу
- Линейная алгебра над C — Квантовые состояния - векторы в C^{2^n}; операции - унитарные матрицы; измерения - проекторы
Итоги
- **Кубит:** |psi> = alpha|0> + beta|1> с |alpha|^2 + |beta|^2 = 1; единичный вектор в C^2
- **Запутанность:** состояния Белла; S(rho_A) = 1 ebit - максимальная для двух кубитов
- **Запрет клонирования:** невозможность копирования произвольного |psi> - следствие линейности
- **Универсальные вентили:** {H, T, CNOT} - аппроксимация любого унитарного оператора (Соловей-Китаев)
- **Сверхплотное кодирование:** 1 ebit + 1 квантовый канал = 2 классических бита
- **Алгоритм Шора:** факторизация за O(n^3); угроза RSA
- **Алгоритм Гровера:** поиск в N элементах за O(sqrt(N)); квадратичное ускорение
Какое ускорение даёт алгоритм Гровера для неструктурированного поиска?