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