Факторизация, то есть разложение числа на простые факторы, произведение которых дает данное число, является основой для взлома криптографических систем. Криптография использует тот факт, что факторизация является чрезвычайно трудоемким занятием. И чем больше число, с которым мы имеем дело, тем больше времени требуется для его факторизации. Следовательно, мы знаем, что чем длиннее данный пароль, тем сложнее его взломать. Поэтому, например, 128-битный шифр будет сложнее взломать, чем 64-битный.
Современные вычислительные технологии не позволяют взламывать очень длинные шифры. Это заняло бы слишком много времени.
В случае с квантовыми вычислениями ситуация совершенно иная. Квантовые вычисления позволили бы мгновенно произвести все необходимые вычисления и сразу же взломать даже самый длинный традиционный шифр.
Однако пока мы не можем управлять большим количеством кубитов (квантовых битов), поэтому мы не можем проводить факторизацию больших чисел. Тот факт, что в 1994 году Питер Шор из Bell Laboratories представил квантовый алгоритм разложения больших чисел на простые числа, доказывает, насколько сложна эта задача. 7 лет интенсивных исследований должно было пройти, прежде чем ученым из IBM и Стэнфордского университета удалось факторизовать число 15. Эта задача стала возможной благодаря миллиардам миллиардов частиц, из которых было создано 7 кубитов. Если бы мы захотели взломать современный шифр, нам пришлось бы научиться управлять тысячами кубитов.
С 2001 года был достигнут определенный прогресс. Ученые, использующие адиабатический квантовый алгоритм (AQC), факторизировали число 21. Теперь китайцы пошли гораздо дальше. Впервые в истории была проведена квантовая факторизация трехзначного числа. Это было 143.
Сюй и его коллеги также использовали AQC. Этот метод, в отличие от алгоритма Шора, не опирается на последовательные вычислительные операции. Вместо этого он находит гамильтониан (оператор гамильтониана). Он содержит все возможные решения проблемы, включая правильное. Обработав его соответствующим образом, можно найти основное состояние системы, которое содержит правильный ответ. Все это хорошо работает в теории, но поскольку спектр решений, предлагаемых гамильтонианом, растет экспоненциально с увеличением длины числа, его практическое применение чрезвычайно сложно и также требует контроля большого числа кубитов.
Поэтому Сюй и его команда упростили уравнения, используемые при работе с гамильтонианом, значительно сузив спектр возможных ответов. Мы использовали новый метод и уменьшили количество кубитов, необходимых для работы алгоритма, поэтому мы смогли факторизовать число 143", - говорит Сюй.
Исследователи считают, что их подход будет полезен и для факторизации больших чисел.
Китайцы использовали для своих исследований спектроскоп ядерного магнитного резонанса.