Насколько я понимаю, кажется, что есть некоторая уверенность в том, что квантовый отжиг ускорит такие проблемы, как коммивояжер, благодаря эффективности, обеспечиваемой, например, квантовым туннелированием. Однако знаем ли мы, в какой степени предусмотрено ускорение?
Во-первых, позвольте мне заметить, что квантовый отжиг, или, точнее, адиабатическая модель квантовых вычислений, полиномиально эквивалентна традиционной модели квантовых вычислений на основе затвора . Во-вторых, общая проблема коммивояжера - NP NPC . В-третьих, обычно считается, что с квантовыми вычислениями, основанными на затворе, невозможно решить за полиномиальное время NP полные проблемы . Все это означает, что считается маловероятным, чтобы с помощью квантового отжига можно было решить за полиномиальное время общую проблему коммивояжера.
Несмотря на то, что считается, что общая проблема может быть решена только в экспоненциальном времени, также с квантовым отжигом, все же может быть некоторое ускорение, например, полиномиальное ускорение. Не так много известно об этом для общего случая. Тем не менее, есть очень хорошая недавняя работа, которая показывает, что существуют квантовые алгоритмы с ограниченной ошибкой, которые обеспечивают квадратичное квантовое ускорение, когда степень каждой вершины (в сложной задаче продавца) не больше 3.