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

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

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

Год назад Одед Регев из Университета Нью-Йорка предложил теоретическое улучшение алгоритма Шора, которое позволяет сократить количество квантовых вентилей. Однако оно требовало большего количества кубитов.

Исследователи из Массачусетского технологического института решили оптимизировать схему Регева так, чтобы она требовала меньшего количества кубитов. Они нашли способ рассчитывать экспоненты при помощи чисел Фибоначчи, что требует простого умножения, а не возведения в квадрат, что позволяет существенно сократить нагрузку на память.

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

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

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