Найдено решение задачи коммивояжера с использованием одного кубита

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

Исследователи из Университета Гамбурга во главе с Капилом Госвами разработали метод решения задачи коммивояжера с использованием всего одного кубита. Этот подход может применяться и к другим задачам, что может изменить представление специалистов о квантовых алгоритмах.

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

Компьютерные ученые разработали алгоритмы, которые рассчитывают оптимальные маршруты, хотя и не всегда самые короткие. Однако даже эти алгоритмы требуют значительных вычислительных ресурсов при большом числе городов. Квантовые вычисления давно обещали ускорение этих алгоритмов, но существующие квантовые алгоритмы также требуют большого числа кубитов. Например, алгоритм для 9 и 10 городов на квантовой архитектуре D-wave требует 73 логических кубита или 5436 физических кубитов.

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

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

Для большего числа городов квантовые состояния должны быть более плотно упакованы на поверхности сферы, что делает их более уязвимыми к шумам и ошибкам. Тем не менее, команда успешно справилась с задачами до 9 городов.

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

Несмотря на текущие ограничения квантовых компьютеров, сферы Блоха представляют собой перспективный инструмент в арсенале квантовых вычислений.