Исследователи Google Quantum AI совместно с учёными из Стэнфорда, MIT и Caltech представили революционный квантовый алгоритм, который может решать определённые классы оптимизационных задач, недоступные для классических суперкомпьютеров. Метод под названием Decoded Quantum Interferometry (DQI) использует волновую природу квантовой механики для создания интерференционных паттернов, которые находят почти оптимальные решения.
Квантовая связь между оптимизацией и декодированием
Суть метода заключается в преобразовании сложных оптимизационных задач в задачи декодирования — поиска ближайшего элемента решётки к заданной точке. Хотя в двумерном пространстве такая задача решается тривиально (как поиск ближайшего угла на шахматной доске), в пространствах высокой размерности она становится вычислительно сложной.
Как сообщает Google Research, именно здесь проявляется квантовое преимущество: алгоритм DQI позволяет использовать хорошо изученные методы декодирования, разработанные для коррекции ошибок в системах хранения и передачи данных, для решения оптимизационных задач.
Квантовые компьютеры, которые сами нуждаются в сложных системах коррекции ошибок, теперь могут использовать эти же методы для решения внешних задач. Это напоминает историю про сапожника без сапог — только здесь сапожник научился шить обувь для других, пока сам ходит босиком.
Конкретный пример: оптимальное пересечение полиномов
Наиболее впечатляющий результат исследователи продемонстрировали на задаче оптимального пересечения полиномов (Optimal Polynomial Intersection, OPI). Эта задача широко используется в анализе данных и полиномиальной регрессии, а также находит применение в цифровой коррекции ошибок и криптографии.
С помощью DQI квантовый компьютер преобразует задачу OPI в проблему декодирования кодов Рида-Соломона — семейства кодов, используемых в DVD и QR-кодах. Для которых существуют эффективные алгоритмы декодирования.
Анализ показывает, что определённые экземпляры задачи OPI могут быть решены квантовыми компьютерами с использованием всего нескольких миллионов элементарных квантовых операций, в то время как наиболее эффективные классические алгоритмы потребовали бы более 10²³ операций.
Источник квантового преимущества
Ключевое понимание заключается в том, что как исходные оптимизационные задачи, так и задачи декодирования относятся к классу NP-трудных проблем. Это означает, что найти точное решение для всех экземпляров этих задач невозможно за полиномиальное время даже с помощью квантовых компьютеров.
Однако преимущество возникает благодаря дополнительной алгебраической структуре некоторых задач. В случае OPI решётка имеет алгебраическую структуру — компоненты базисных векторов получаются возведением числа в последовательно возрастающие степени. Эта структура значительно облегчает задачу декодирования, но не упрощает исходную оптимизационную задачу для классических компьютеров.
- Квантовые компьютеры могут преобразовать оптимизацию в декодирование
- Алгебраическая структура делает декодирование эффективным
- Классические методы не получают аналогичного выигрыша
Перспективы и ограничения
Хотя текущие результаты демонстрируют теоретическое преимущество, практическая реализация потребует масштабируемых квантовых компьютеров с коррекцией ошибок. Тем не менее, работа представляет важный шаг в понимании того, какие именно классы задач могут получить выгоду от квантовых вычислений.
Метод DQI открывает новые возможности для применения квантовых технологий в реальных оптимизационных задачах — от планирования маршрутов до организации клинических испытаний, где поиск оптимального решения традиционными методами оказывается вычислительно невыполнимым.