Quantum Branch-and-Bound Algorithm and its Application to the Travelling Salesman Problem
- Authors: Markevich E.A.1,2,3, Trushechkin A.S.1
-
Affiliations:
- National Research Nuclear University MEPhI
- Steklov Mathematical Insitute of the Russian Academy of Sciences
- National University of Science and Technology MISiS
- Issue: Vol 241, No 2 (2019)
- Pages: 168-184
- Section: Article
- URL: https://journals.rcsi.science/1072-3374/article/view/242872
- DOI: https://doi.org/10.1007/s10958-019-04415-6
- ID: 242872
Cite item
Abstract
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.
About the authors
E. A. Markevich
National Research Nuclear University MEPhI; Steklov Mathematical Insitute of the Russian Academy of Sciences; National University of Science and Technology MISiS
Author for correspondence.
Email: eva-markevich@mail.ru
Russian Federation, Moscow; Moscow; Moscow
A. S. Trushechkin
National Research Nuclear University MEPhI
Email: eva-markevich@mail.ru
Russian Federation, Moscow