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

Проект ЦИТадель

Термины сгруппированы по темам: основы, схемы, алгоритмы, сложность, аппаратура, коррекция ошибок и криптография. Английские эквиваленты помогут искать первоисточники и документацию. Определения намеренно кратки; оговорки и вывод формул даны в курсе.

Основы

Кубит (qubit, quantum bit)

Двухуровневая квантовая система — элементарный носитель квантовой информации. Чистое состояние записывается как α|0⟩ + β|1⟩, где комплексные амплитуды нормированы.

Нотация Дирака (bra–ket notation)

Запись векторов состояния как кетов |ψ⟩, элементов двойственного пространства как бра ⟨ψ|, а скалярного произведения как ⟨φ|ψ⟩.

Вычислительный базис (computational basis)

Стандартный ортонормированный базис кубита {|0⟩, |1⟩}; для n кубитов — все 2ⁿ битовые строки. Обычное измерение схемы выполняется в этом базисе.

Чистое и смешанное состояние (pure and mixed state)

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

Суперпозиция (superposition)

Линейная комбинация базисных состояний, например |ψ⟩ = α|0⟩ + β|1⟩. При проективном измерении система переходит в состояние, согласованное с полученным исходом.

Глобальная и относительная фаза (global and relative phase)

Общий множитель e^iγ у всего вектора состояния ненаблюдаем; это глобальная фаза. Фазы между отдельными амплитудами относительны, влияют на интерференцию и измеримы после подходящей смены базиса.

Амплитуда (amplitude)

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

Правило Борна (Born rule)

Вероятность исхода, заданного нормированным вектором |u⟩, для состояния |ψ⟩ равна |⟨u|ψ⟩|². Правило связывает комплексные амплитуды с наблюдаемой статистикой.

Интерференция (interference)

Усиление и гашение комплексных амплитуд при сложении путей вычисления. Алгоритм управляет фазами так, чтобы повысить вероятность полезных исходов; одно наличие суперпозиции ускорения не даёт.

Тензорное произведение (tensor product)

Операция, объединяющая пространства состояний подсистем. Пространство n кубитов имеет размерность 2ⁿ, а его вычислительный базис состоит из всех n-битовых строк.

Запутанность (entanglement)

Состояние составной системы, которое нельзя представить тензорным произведением состояний подсистем. Даёт неклассические корреляции, но не позволяет передавать сигнал быстрее света и само по себе не гарантирует ускорения.

Сепарабельное состояние (separable state)

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

Состояние Белла (Bell state)

Одно из четырёх максимально запутанных состояний двух кубитов, например (|00⟩ + |11⟩)/√2. Простейший пример запутанности.

Неравенство Белла (Bell inequality)

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

Измерение (measurement)

Физическая операция с классическим исходом, вероятности которого задаёт правило Борна. Проективное измерение обычно меняет состояние; один экземпляр не раскрывает его амплитуды.

Квантовая томография (quantum state tomography)

Статистическое восстановление состояния по измерениям многих одинаково подготовленных экземпляров в нескольких базисах. Число необходимых параметров в общем случае экспоненциально растёт с числом кубитов.

Декогеренция (decoherence)

Утрата наблюдаемой когерентности из-за неконтролируемого взаимодействия системы с окружением. Проявляется как дефазировка, релаксация и другие шумовые процессы.

Время когерентности (coherence time)

Характерная временная шкала релаксации или потери фазы. Обычно различают T₁ для обмена энергией с окружением и T₂ для затухания относительной фазы; одной этой метрики недостаточно для оценки процессора.

Теорема о запрете клонирования (no-cloning theorem)

Не существует физической операции, идеально копирующей произвольное неизвестное квантовое состояние. Известные или взаимно ортогональные состояния можно повторно приготовить или копировать в выбранном базисе.

Сфера Блоха (Bloch sphere)

Геометрическое представление чистого состояния одного кубита точкой на единичной сфере; смешанные состояния лежат внутри шара. С точностью до глобальной фазы однокубитные унитарные операции соответствуют поворотам.

Квантовая телепортация (quantum teleportation)

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

Кудит (qudit)

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

Вентили и схемы

Квантовый вентиль (quantum gate)

Когерентная операция над одним или несколькими кубитами, математически описываемая унитарным оператором. В отличие от общего квантового канала, вентиль обратим.

Квантовая схема (quantum circuit)

Стандартная модель записи квантового алгоритма: провода кубитов, вентили, измерения, сброс и при необходимости классическое управление.

Вентиль Адамара (Hadamard gate, H)

Переводит вычислительный базис в базис {|+⟩, |−⟩}: H|0⟩ = |+⟩, H|1⟩ = |−⟩. Используется для подготовки и интерференции суперпозиций.

Вентили Паули (Pauli gates, X/Y/Z)

Три однокубитных вентиля: X меняет |0⟩ и |1⟩ местами, Z меняет относительную фазу, а Y сочетает оба действия с фазовыми множителями.

CNOT (controlled-NOT)

Двухкубитный управляемый вентиль: на базисном входе применяет X к целевому кубиту, если управляющий равен |1⟩; на суперпозициях действует линейно. Может создавать запутанность.

Вентиль Тоффоли (Toffoli gate, CCNOT)

Трёхкубитный управляемый-управляемый-NOT. Универсален для обратимого классического вычисления и часто используется при построении квантовой арифметики.

Универсальный набор вентилей (universal gate set)

Конечный набор, схемами из которого любую нужную унитарную операцию можно приблизить с заданной точностью. Пример — H, T и CNOT.

Клиффордовские вентили (Clifford gates)

Вентили, переводящие операторы Паули друг в друга при сопряжении; порождаются, например, H, S и CNOT. Клиффордовские схемы важны для коррекции ошибок, но без дополнительного неклиффордовского ресурса эффективно моделируются классически.

T-вентиль и T-count (T gate, T-count)

T — неклиффордовский фазовый вентиль, дополняющий клиффордовские операции до универсальности. В отказоустойчивой схеме он часто дорог, поэтому отдельно считают число T-вентилей и их последовательных слоёв.

Глубина схемы (circuit depth)

Минимальное число последовательных слоёв после параллельного размещения совместимых операций. Физическая длительность зависит также от типов вентилей, измерений, связности и расписания.

Транспиляция (transpilation)

Компиляция абстрактной схемы под конкретный процессор: разложение в его родной набор вентилей с учётом физической связности кубитов.

Оракул (oracle)

Чёрный ящик в формулировке алгоритма — подсхема, вычисляющая заданную функцию. Используется в анализе алгоритмов Гровера, Дойча–Йожи и других.

Фазовый откат (phase kickback)

Перенос фазы с целевого собственного состояния управляемой операции на управляющий регистр. Позволяет записать значение функции или собственную фазу в относительные фазы амплитуд.

Анцилла (ancilla)

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

Развычисление (uncomputation)

Обратный запуск части схемы для очистки временных регистров после того, как нужный результат перенесён дальше. Удаляет «мусорную» запутанность и возвращает анциллы в известное состояние.

Алгоритмы

Алгоритм Шора (Shor's algorithm)

Квантовые алгоритмы полиномиального времени для факторизации и дискретного логарифма. На достаточно большом отказоустойчивом компьютере угрожают RSA, классическим DH/DSA, ECDH и ECDSA, но не автоматически всем асимметричным схемам.

Алгоритм Гровера (Grover's algorithm)

Поиск отмеченного элемента среди N вариантов за O(√N) обращений к оракулу. Квадратичное ускорение оптимально в этой модели, но реальная стоимость включает обратимую реализацию оракула, глубину и коррекцию ошибок.

Квантовое преобразование Фурье (Quantum Fourier Transform, QFT)

Унитарное преобразование амплитуд, родственное дискретному преобразованию Фурье и реализуемое компактной квантовой схемой. Само по себе не выдаёт классический список коэффициентов быстрее FFT; полезно внутри оценки фазы и алгоритма Шора.

Оценка фазы (quantum phase estimation)

Алгоритм оценки φ из собственного значения e^2πiφ унитарного оператора при наличии собственного состояния и управляемых степеней оператора. Строительный блок поиска порядка и многих алгоритмов моделирования.

Усиление амплитуды (amplitude amplification)

Обобщение геометрической идеи Гровера: чередование отражений повышает вероятность целевого подпространства и даёт квадратичное уменьшение числа повторов для ряда вероятностных процедур.

VQE (Variational Quantum Eigensolver)

Гибридный вариационный метод оценки низших собственных значений: квантовая схема готовит параметризованное состояние, измерения оценивают целевую функцию, а классический оптимизатор обновляет параметры.

QAOA (Quantum Approximate Optimization Algorithm)

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

Квантовый отжиг (quantum annealing)

Эвристический поиск низкоэнергетического состояния путём медленного изменения гамильтониана. Коммерческие отжигатели ориентированы на модели Ising/QUBO и не являются обычными универсальными вентильными процессорами для запуска алгоритма Шора.

Квантовое машинное обучение (quantum machine learning, QML)

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

qRAM (quantum random access memory)

Модель памяти, когерентно возвращающая данные по суперпозиции адресов. Некоторые заявленные ускорения для классических данных предполагают дешёвую qRAM, хотя её построение, загрузка и коррекция ошибок сами требуют ресурсов.

Сложность и границы

P, NP и BPP

P — задачи, решаемые детерминированно за полиномиальное время; NP — задачи с полиномиально проверяемым свидетельством; BPP — задачи, решаемые вероятностным классическим алгоритмом за полиномиальное время с ограниченной ошибкой.

BQP (Bounded-Error Quantum Polynomial Time)

Класс задач, решаемых равномерным семейством квантовых схем полиномиального размера с вероятностью ошибки, ограниченной константой меньше 1/2. Не известно, содержит ли BQP NP-полные задачи.

Сложность запросов (query complexity)

Число обращений алгоритма к оракулу. Эта модель изолирует информационную трудность, но не учитывает цену построения самого оракула, память, маршрутизацию и коррекцию ошибок.

Квантовое преимущество (quantum advantage / supremacy)

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

Квантовая полезность (quantum utility)

Получение практически или научно ценного результата с помощью квантового устройства. Полезность и преимущество — разные оси: результат может быть полезен без доказанного превосходства или превосходить классику в искусственной задаче без прикладной ценности.

Аппаратура и коррекция ошибок

Сверхпроводящие кубиты (superconducting qubits)

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

Ионы в ловушках (trapped ions)

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

Нейтральные атомы (neutral atoms)

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

Фотонные вычисления (photonic quantum computing)

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

Топологический кубит (topological qubit)

Предлагаемый способ нелокального кодирования информации в топологических степенях свободы, например связанных с майорановскими нулевыми модами. Предварительные эксперименты не равнозначны демонстрации зрелого топологического логического кубита.

Достоверность (fidelity)

Мера близости реального состояния или канала к идеальному. Зависит от определения и метода усреднения; величина 1−F не всегда является простой вероятностью независимой ошибки.

NISQ (Noisy Intermediate-Scale Quantum)

Шумные квантовые устройства промежуточного масштаба без полноценной отказоустойчивости (термин Дж. Прескилла, 2018). Определение относится к возможностям и шуму, а не к фиксированному числу кубитов.

Физический кубит (physical qubit)

Непосредственно управляемая аппаратная двухуровневая система. Её ошибки, утечка, измерение и связи образуют физический шум, из которого код строит более защищённые логические степени свободы.

Логический кубит (logical qubit)

Закодированная степень свободы, распределённая по нескольким физическим кубитам. Она становится полезнее физической только при достаточно низкой логической ошибке и наличии отказоустойчивых операций.

Логическая ошибка (logical error)

Ошибка, которая после декодирования действует на закодированную информацию как нетривиальная логическая операция. Её вероятность на цикл или операцию — ключевая метрика масштабирования QEC.

Квантовая коррекция ошибок (quantum error correction, QEC)

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

Смягчение ошибок (quantum error mitigation)

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

Стабилизаторный код (stabilizer code)

Квантовый код, пространство которого задаётся общим собственным подпространством набора коммутирующих операторов Паули. Измерение стабилизаторов даёт синдромы, не раскрывая логическое состояние.

Поверхностный код (surface code)

Ведущее семейство топологических стабилизаторных кодов на двумерной решётке с локальными проверками. Обладает сравнительно высоким порогом, но требует значительной пространственно-временной избыточности.

Кодовое расстояние (code distance)

Минимальный вес физического оператора, реализующего нетривиальную логическую операцию и не обнаруживаемого стабилизаторами. Идеальный код расстояния d исправляет до ⌊(d−1)/2⌋ произвольных ошибок.

Порог отказоустойчивости (fault-tolerance threshold)

Граница для заданных кода, схемы извлечения синдромов, декодера и модели шума: ниже неё увеличение кода может подавлять логическую ошибку. Это не одна универсальная константа для всех устройств.

Синдром ошибки (error syndrome)

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

Декодер (decoder)

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

Рамка Паули (Pauli frame)

Классическая запись накопленных логических поправок X и Z. Часто ошибку не исправляют физическим вентилем немедленно, а учитывают эту рамку при следующих операциях и интерпретации измерения.

Дистилляция магических состояний (magic-state distillation)

Получение высококачественных вспомогательных состояний из множества шумных для выполнения отказоустойчивых неклиффордовских операций. Часто составляет значительную часть ресурсов большого алгоритма.

Отказоустойчивые квантовые вычисления (fault-tolerant quantum computing, FTQC)

Организация кодированных операций так, чтобы малое число физических отказов не распространялось в некорректируемую логическую ошибку. Пороговая теорема допускает сколь угодно длинные вычисления с растущей избыточностью при выполнении её предпосылок; даты появления крупной FTQC неизвестны.

Криптография

Постквантовая криптография (post-quantum cryptography, PQC)

Классические криптографические алгоритмы для обычных компьютеров, для которых при выбранных параметрах не известно эффективных классических или квантовых атак. Это не доказательство вечной стойкости и не то же самое, что QKD.

HNDL (harvest now, decrypt later — «собрать сейчас, расшифровать потом»)

Сценарий пассивного перехвата и хранения квантово-уязвимого шифротекста с расчётом расшифровать его после появления подходящей атаки. Ускоряет миграцию каналов с долгоживущими секретами уже до появления CRQC.

Механизм инкапсуляции ключей (Key-Encapsulation Mechanism, KEM)

Пара алгоритмов: инкапсуляция по открытому ключу создаёт шифртекст и общий секрет, а декапсуляция секретным ключом восстанавливает тот же секрет. KEM используют внутри протокола установления ключей, а не для прямого шифрования произвольного сообщения.

ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism; FIPS 203; бывший CRYSTALS-Kyber)

Стандартизованный NIST в 2024 году модульно-решёточный KEM. Используется для постквантового установления общего секрета; FIPS 203 задаёт наборы ML-KEM-512/768/1024.

ML-DSA (Module-Lattice-Based Digital Signature Algorithm; FIPS 204; бывший CRYSTALS-Dilithium)

Стандартизованная NIST в 2024 году модульно-решёточная цифровая подпись. FIPS 204 задаёт ML-DSA-44/65/87 с разными размерами и категориями стойкости.

SLH-DSA (Stateless Hash-Based Digital Signature Algorithm; FIPS 205; бывший SPHINCS+)

Стандартизованная NIST бесстатусная хеш-подпись на основе SPHINCS+. Даёт альтернативное решёткам основание, но подписи и вычислительная цена заметно выше и зависят от выбранного набора.

Кодовая криптография (code-based cryptography)

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

HQC (Hamming Quasi-Cyclic)

Кодовый KEM, выбранный NIST в 2025 году для будущей стандартизации как альтернатива ML-KEM с иным математическим основанием. По состоянию на август 2026 года отдельный FIPS для HQC ещё не опубликован.

Решёточная криптография (lattice-based cryptography)

Семейство схем на задачах в многомерных решётках. Практические ML-KEM и ML-DSA используют структурированные модульные варианты; их параметры оценивают против конкретных известных атак, а не по лозунгу «SVP трудна».

LWE (Learning With Errors — обучение с ошибками)

Задача восстановления секрета из линейных соотношений с малым шумом. Для некоторых параметров и вариантов известны строгие связи с решёточными задачами; ML-KEM использует структурированный Module-LWE, а ML-DSA — родственные модульно-решёточные предположения.

Гибридная схема (hybrid key exchange)

Совместное применение классического и постквантового механизма с проанализированным комбинатором. Цель — сохранить секретность при стойкости хотя бы одной компоненты; самодельная конкатенация, ошибки протокола или downgrade могут лишить гибрид этого свойства.

X25519MLKEM768

Стандартизованная в RFC 10024 гибридная группа TLS 1.3, объединяющая ECDHE X25519 и ML-KEM-768. Увеличивает key_share примерно на 1184 байта у клиента и на 1088 байт у сервера относительно одного X25519.

Криптогибкость (crypto-agility)

Способность системы обнаружить используемую криптографию и безопасно заменить алгоритмы, параметры, ключи и форматы без полного перепроектирования. Требует не только конфигурационного переключателя, но и обновляемых протоколов, устройств и зависимостей.

Криптографическая опись (Cryptography Bill of Materials, CBOM)

Реестр криптографических зависимостей: алгоритмов, протоколов, библиотек, сертификатов, ключей, оборудования, целей применения, владельцев и сроков данных. Формат CBOM ещё не универсален; ценность определяется полнотой и актуальностью.

Неравенство Моски (Mosca's inequality)

Проверка срочности миграции: если x + y > z, где x — требуемый срок секретности, y — длительность перехода, а z — сценарный срок до квантового взлома, ждать опасно. Это инструмент анализа риска, а не прогноз даты CRQC.

Квантовое распределение ключей (quantum key distribution, QKD)

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

BB84

Первый протокол QKD (Беннет и Брассар, 1984): биты кодируются неортогональными состояниями в случайно выбранных базисах. Реальный протокол включает просеивание, оценку параметров, исправление ошибок, усиление секретности и аутентификацию.

Криптографически значимый квантовый компьютер (cryptographically relevant quantum computer, CRQC)

Отказоустойчивая машина, способная выполнить квантовую атаку на практически используемый криптографический параметр, например факторизацию RSA-2048 или дискретный логарифм P-256. Дата появления неизвестна, а ресурсные оценки зависят от архитектуры и допущений.