Квантовый алгоритм ветвей и границ и его применение к задаче коммивояжера

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