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

Во-первых, что за шифр. Это очень известный шифр, предложенный ещё в 1977 году, названный по первым буквам фамилий создателей: Rivest, Shamir и Adleman. Его стойкость основана на сложности решения задачи разложения целого числа на простые сомножители: 33=3x11, 45=3x3x5 и т.д. Для больших чисел это вычислительно очень сложная задача, даже если заранее известно, что в числе только два простых сомножителя. Например, попробуйте разложить на простые сомножители число 91 (ответ: 13х7). Если вы найдете эти сомножители, то обратно перемножить их легко, а вот найти их, когда они неизвестны - тут перебирать надо, даже с таким маленьким числом. Длина ключа в шифре RSA - это каким количеством двоичных разрядов записывается целое число. 2048 - значит это число имеет 2048 двоичных разрядов, или примерно 700 (!) десятичных. Число миллион имеет 7 десятичных разрядов, а тут 700! Найти простые сомножители для такого числа совершенно нереально для любых мыслимых суперкомпьютеров.

Квантовые вычисления во многом или даже в основном обязаны своей популярностью именно тем, что Питером Шором (Shor) в 1994 году был найден квантовый алгоритм, способный за разумное время решить эту задачу, а также и другие, родственные. Квантовый компьютер оказывается способным взломать все используемые шифры с так называемым открытым ключом. Без таких шифров невозможно представить современную инфраструктуру: сотовая связь, банковские карточки и т.п. Согласно алгоритму Шора для взлома шифра RSA квантовому компьютеру требуется количество кубитов, вдвое превышающую длину ключа. То есть если длина ключа - 2048 битов, то для взлома квантовому компьютеру достаточно иметь 2048х2=4096 кубитов. Всего-то! В современных квантовых компьютерах число кубитов уже перевалило за тысячу!

НО: 4096 - это при условии идеального выполнения квантовых операций. А так не бывает, квантовые вычисления очень сильно подвержены шумам. Поэтому надо вводить коды исправления ошибок, которые мы тоже затрагивали. Множество "физических" кубитов могут моделировать один "логический". Физические кубиты подвержены шумам, но можно так организовать их работу, чтоб они все вместе соответствовали одному логическому кубиту, который уже почти бесшумный. Поэтому 4096 - это число именно логических кубитов. А физических кубитов даже при очень точном (99,99%) выполнении операций нужно намного больше. А намного - это насколько? До этого так называемые "поверхностные коды" требовали, чтоб каждому логическому кубиту соответствовало порядка тысячи физических. Поэтому умножаем 4096 на 1000 и получаем, что число физических кубитов должно быть порядка нескольких миллионов. Это уже кажется каким-то бесконечно далеким от нынешних компьютеров на порядка тысячи кубитов.