Quantum Branch-and-Bound Algorithm and its Application to the Travelling Salesman Problem
- Авторлар: Markevich E.1,2,3, Trushechkin A.1
-
Мекемелер:
- National Research Nuclear University MEPhI
- Steklov Mathematical Insitute of the Russian Academy of Sciences
- National University of Science and Technology MISiS
- Шығарылым: Том 241, № 2 (2019)
- Беттер: 168-184
- Бөлім: Article
- URL: https://journals.rcsi.science/1072-3374/article/view/242872
- DOI: https://doi.org/10.1007/s10958-019-04415-6
- ID: 242872
Дәйексөз келтіру
Аннотация
We propose a quantum branch-and-bound algorithm based on the general scheme of the branch-and-bound method and the quantum nested searching algorithm and examine its computational efficiency. We also compare this algorithm with a similar classical algorithm on the example of the travelling salesman problem. We show that in the vast majority of problems, the classical algorithm is quicker than the quantum algorithm due to greater adaptability. However, the operation time of the quantum algorithm is constant for all problem, whereas the classical algorithm runs very slowly for certain problems. In the worst case, the quantum branch-and-bound algorithm is proved to be several times more efficient than the classical algorithm.
Авторлар туралы
E. Markevich
National Research Nuclear University MEPhI; Steklov Mathematical Insitute of the Russian Academy of Sciences; National University of Science and Technology MISiS
Хат алмасуға жауапты Автор.
Email: eva-markevich@mail.ru
Ресей, Moscow; Moscow; Moscow
A. Trushechkin
National Research Nuclear University MEPhI
Email: eva-markevich@mail.ru
Ресей, Moscow