Можно ли использовать квантовые алгоритмы для шифрования?

Question

Могут ли быть полезны квантовые алгоритмы?

Удалось ли кому-нибудь успешно применить квантовые алгоритмы?

Answer 1

«Квантовые алгоритмы» - это алгоритмы, запускаемые на квантовых компьютерах.

Есть вещи, которые можно быстро сделать в модели квантовых вычислений, которые не известны (или не считаются) возможными при классических вычислениях: Дискретный логарифм и Целочисленная факторизация (см. алгоритм Шора ) находится в BQP , но, как полагают, не в P (или BPP ). Таким образом, когда / если построен квантовый компьютер, известно, что он может взломать RSA и большинство современных криптографий.

Однако,

• квантовые компьютеры не могут (я имею в виду, я не имею в виду) решать NP-полные задачи за полиномиальное время и, что более важно,
• никто еще не построил квантовый компьютер, и даже неясно, удастся ли его создать - избегая декогеренции и т. Д. (Были заявления о квантовых компьютерах с ограниченным числом кубитов - 5 до 10, но они явно ни на что не годятся.)

"Ну, есть квантовый компьютер, который может в 15 раз больше, так что те из вас, кто использует 4-битный RSA должен волновать. "- Брюс Шнайер

[Существует также идея квантовой криптографии , которая является криптографией по квантовому каналу и сильно отличается от квантовых вычислений.]

Answer 2

Единственный логичный ответ - они оба полезны и бесполезны. ; -)

Answer 3

Насколько я знаю о квантовых вычислениях и алгоритмах. Я видел довольно широкое применение квантовых алгоритмов в криптографии. Если вы действительно интересуетесь криптографией, пожалуйста, проверьте эти вещи. В основном все зависит от того, насколько хорошо вы знаете основы квантовой механики. и дискретная математика. Например: вы должны видеть сложные алгоритмы, такие как алгоритм Шора, это в основном целочисленная факторизация. Фактически, целочисленная факторизация - это легко, используя обычные алгоритмы Алгебраический алгоритм факторизации, метод факторизации Ферма ... и т. Д., Но когда дело доходит до квантовых вычислений, это совершенно другое все работает на компьютерах Quantum, поэтому алгоритм меняется, и мы должны использовать алгоритмы, подобные Шору и т. д.

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

Answer 4

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

Answer 5

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

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

Answer 6

Stackoverflow работает на своего рода квантовом компьютере.

Фейнман подразумевал возможность того, что квантовая вероятность является источником человеческого творчества.

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

Так что, возможно, Stackoverflow является примером успешной реализации квантового алгоритма.

Что ты думаешь?

Answer 7

Существует также некоторое исследование того, могут ли квантовые вычисления использоваться для решения сложных задач, таких как факторинг больших чисел (если это было бы возможно, это нарушило бы современные методы шифрования).