Задачу коммивояжера решили одним кубитом

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

Задача коммивояжера — известная NP-трудная проблема. Ее суть состоит в том, чтобы построить кратчайший маршрут, который проходит через каждый город один раз. Классические компьютеры для этого либо требуют огромных затрат по времени вычислений, либо позволяют найти решение, но оно не всегда оказывается оптимальным (так называемые эвристические алгоритмы). То есть маршрут будет одним из самых коротких, но только с некоторой вероятностью оптимальным. Часто оптимальность решения исследователям трудно проверить именно из-за NP-сложности задачи.

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

Группа физиков под руководством Питера Шмельхера (Peter Schmelcher) из Гамбургского университета предложила новый подход в решении задачи коммивояжера. Вместо квантовой запутанности ученые использовали принцип суперпозиции.

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

Главная сложность, с которой столкнулись исследователи, это постобработка результатов. Некоторые маршруты не удовлетворяли условиям задачи коммивояжера. Например, проходили через один и тот же город дважды, или были запрещенными (то есть использовали пути, не предусмотренные в задаче). Отсечь неправильные решения ученым помогла настройка операторов вращения с помощью алгоритма SPSA. Точность описанного подхода оказалась ограничена количеством городов и их взаимным расположением (симметрично или асимметрично на экваторе блоховской сферы). Для шести симметрично расположенных городов в 97 процентах случаев ученые получили точность решения более 0,99. Уже для семи городов эта доля упала до 62 процентов.

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

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