Квантовый алгоритм впервые применен для факторизации трехзначного числа

Задача нахождения простых множителей у целого числа с ростом его величины свыше 100000 быстро становится непосильной для классических компьютерных алгоритмов. Напротив, квантовые компьютеры теоретически способны разложить на множители как угодно большое целое число. На практике, из-за трудности сохранения квантовой когерентности наибольшее факторизованное таким образом число было 21. В публикации для Physical Review Letters физики Университета науки и технологии (Хефэй, Китай) представили алгоритм, позволивший разложить на наибольшие простые множители 11 и 13 трехзначное число 143.

Первый и самый известный алгоритм квантовой факторизации предложен Питером Шором (Peter Shor) в 1994 г. Китайские ученые использовали альтернативный метод под названием адиабатические квантовые вычисления (AQC). Он разработан Эдвардом Фархи (Edward Farhi) в 2001 г. для решения задач оптимизации — нахождения наилучших из многих возможных величин.

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

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

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

Физически, экспериментальная установка представляла собой жидкокристаллическую систему ЯМР (ядерный магнитный резонанс), в которой магнитное ядро поглощало излучение и переизлучало его с определенной частотой.

Стратегія охолодження ЦОД для епохи AI