Publication:
Quantum Branch-and-Bound Algorithm and its Application to the Travelling Salesman Problem

Простая страница элемента
dc.contributor.authorMarkevich, E. A.
dc.contributor.authorTrushechkin, A. S.
dc.date.accessioned2024-11-21T10:31:13Z
dc.date.available2024-11-21T10:31:13Z
dc.date.issued2019
dc.description.abstract© 2019, Springer Science+Business Media, LLC, part of Springer Nature.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.
dc.format.extentС. 168-184
dc.identifier.citationMarkevich, E. A. Quantum Branch-and-Bound Algorithm and its Application to the Travelling Salesman Problem / Markevich, E.A., Trushechkin, A.S. // Journal of Mathematical Sciences (United States). - 2019. - 241. - № 2. - P. 168-184. - 10.1007/s10958-019-04415-6
dc.identifier.doi10.1007/s10958-019-04415-6
dc.identifier.urihttps://www.doi.org/10.1007/s10958-019-04415-6
dc.identifier.urihttps://www.scopus.com/record/display.uri?eid=2-s2.0-85069891110&origin=resultslist
dc.identifier.urihttps://openrepository.mephi.ru/handle/123456789/18446
dc.relation.ispartofJournal of Mathematical Sciences (United States)
dc.titleQuantum Branch-and-Bound Algorithm and its Application to the Travelling Salesman Problem
dc.typeArticle
dspace.entity.typePublication
oaire.citation.issue2
oaire.citation.volume241
relation.isOrgUnitOfPublication010157d0-1f75-46b2-ab5b-712e3424b4f5
relation.isOrgUnitOfPublication.latestForDiscovery010157d0-1f75-46b2-ab5b-712e3424b4f5
Файлы
Коллекции
Публикации