Алгоритм Шора
Квантовый алгоритм разложения целых чисел на простые множители за время, полиномиально зависящее от длины записи числа. На достаточно мощном квантовом компьютере позволяет взламывать криптосистемы, безопасность которых основана на сложности такого разложения, например RSA.
проверено по: arxiv.org ↗
См. также
- RSARSA — криптографический алгоритм с открытым ключом для шифрования данных и цифровой подписи. Открытый ключ используют для шифрования и проверки подписи, а закрытый — для расшифрования и создания подписи. Разложение большого числа, входящего в открытый ключ, на простые множители позволяет вычислить закрытый ключ.
- Постквантовая криптографияРаздел криптографии, который создаёт алгоритмы шифрования и электронной подписи, устойчивые к атакам с помощью квантовых компьютеров. Такие компьютеры смогут взломать распространённые сегодня схемы с открытым ключом, например RSA. Постквантовые алгоритмы работают на обычных компьютерах, и этим они отличаются от квантовой криптографии, которая защищает связь с помощью квантовых физических эффектов.
- Квантовая коррекция ошибокНабор методов защиты квантовой информации от ошибок, вызванных шумом и декогеренцией (quantum error correction). Состояние одного логического кубита кодируют сразу во многих физических кубитах, периодически измеряют проверочные величины (синдромы) и по ним находят и исправляют ошибки, не разрушая само квантовое состояние. Считается необходимым условием для создания больших отказоустойчивых квантовых компьютеров; в отличие от классических корректирующих кодов, ей приходится обходиться без прямого копирования и измерения данных.
- КубитКвантовый бит (qubit) — наименьшая единица информации в квантовом компьютере. Обычный бит равен либо 0, либо 1, а кубит может находиться в суперпозиции этих состояний; несколько кубитов могут быть запутаны между собой. Физически кубиты реализуют, например, на сверхпроводящих цепях, ионах, атомах или фотонах.
- Квантовое превосходствоСпособность квантового вычислительного устройства выполнять конкретную задачу, которая практически недоступна классическим компьютерам из-за необходимых затрат времени или других вычислительных ресурсов.
В новостях
ИИ-система на модели Anthropic доказала гипотезу о квантовом ускорении
Квантовый алгоритм, который раскладывает большие числа на простые множители экспоненциально быстрее известных методов для обычных компьютеров. Из-за него квантовые компьютеры считают угрозой для распространённого шифрования.