Категорический императив кванта

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

В свое время физики придумали квантовые компьютеры, логической единицей которых является не классический объект (бит) с состояниями «0» и «1», но квантовый — так называемый кубит. В настоящее время квантовые компьютеры реализованы экспериментально; самый большой из них содержит 433 кубита.

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

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

Алгоритм Шора. Фото: Wikimedia Commons, CC BY-SA 4.0

В конце прошлого года появилась статья китайских ученых (Бао Ян и другие), в которой предъявлен результат, который претендует на революционность: они продемонстрировали, что совсем маленький квантовый компьютер из 10 кубитов справляется с реализацией алгоритма разложения на простые множители. Речь идет не о стандартном алгоритме Шора, а о так называемом алгоритме Шнорра. Его до сих пор не реализовывали на квантовом компьютере.

читайте также

Всё по науке

Десять самых выдающихся открытий и изобретений в 2022 году

Андрей Заякин3 января 2023

читайте также

Всё по науке

Десять самых выдающихся открытий и изобретений в 2022 году

Андрей Заякин3 января 2023

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

Переворачивает ли это ситуацию с компьютерной безопасностью? Как кажется, пока нет — автор статьи в Nature Давиде Кастельвекки приводит скептические соображения экспертов по поводу эффективности предлагаемого метода. В работе китайских ученых использовался пример чисел гораздо меньших, чем те, которые нужно разлагать для реального взлома шифра. И китайские товарищи также не показали, что их метод дает результаты быстрее, чем обычный лэптоп. Как будет расти время решения задачи при увеличении рассматриваемых чисел — мы тоже пока что не знаем. Таким образом, эффект от «квантовости» вычислений пока что неясен. Поэтому сама принципиальная реализация разложения на простые числа на квантовом компьютере еще не говорит ничего о достижимости взлома квантового шифрования.