×

Quantum branch-and-bound algorithm and its application to the travelling salesman problem. (English. Russian original) Zbl 1426.81026

J. Math. Sci., New York 241, No. 2, 168-184 (2019); translation from Itogi Nauki Tekh., Ser. Sovrem. Mat. Prilozh., Temat. Obz. 138, 60-75 (2017).
Summary: 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.

MSC:

81P68 Quantum computation
68Q12 Quantum algorithms and complexity in the theory of computing
68P10 Searching and sorting
91B26 Auctions, bargaining, bidding and selling, and other market models
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Ahuja, S. Kapoor, “A quantum algorithm for finding the maximum,” e-print arxiv.org/abs/quant-ph/9911082
[2] A. Ambainis, “Quantum search algorithm,” SIGACT News, 35, No. 2, 22-35 (2004). · doi:10.1145/992287.992296
[3] C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, “Strengths and weaknesses of quantum computing,” SIAM J. Comput., 26, No. 5, 1510-1523 (1997). · Zbl 0895.68044 · doi:10.1137/S0097539796300933
[4] P. Billingsley, Probability and Measure, Wiley, New York (1995). · Zbl 0822.60002
[5] G. Brassard, P. Høyer, M. Mosca, and A. Tapp, “Quantum amplitude amplification and estimation,” Quantum Comput. Quantum Inform. Sci., Contemp. Math. Ser., 305, 53-74 (2002). · Zbl 1063.81024
[6] N. J. Cerf, L. Grover, and C. P. Williams, “Nested quantum search and structured problems,” Phys. Rev. A, 61, No. 3, 032303 (2000). · doi:10.1103/PhysRevA.61.032303
[7] A. Childs, S. Kimmel, and R. Kothari, “The quantum query complexity of read-many formulas,” Lect. Notes Comput. Sci., 7501, 336-348 (2012). · Zbl 1365.68261
[8] A. M. Childs, A. J. Landahl, and P. A. Parrilo, “Improved quantum algorithms for the ordered search problem via semidefinite programming,” Phys. Rev. A, 75, No. 3, 032335 (2007). · doi:10.1103/PhysRevA.75.032335
[9] R. Cleve, D. Gavinsky, and D. L. Yonge-Mallo, “Quantum algorithms for evaluating min-max trees,” in: Theory of Quantum Computation, Communication, and Cryptography, Lect. Notes Comput. Sci., 5106, (2008), pp. 11-15. · Zbl 1162.68456
[10] M. Cortina-Borja and T. Robinson, “Estimating the asymptotic constants of the total length of Euclidean minimal spanning trees with power-weighted edges,” Stat. Probab. Lett., 47, No. 2, 125-128 (2000). · Zbl 1063.90058 · doi:10.1016/S0167-7152(99)00147-9
[11] T. G. Crainic, B. Le Cun, and C. Roucairol, “Parallel branch-and-bound algorithms,” in: Parallel Combinatorica and Optimization, Wiley, New York (2006), pp. 1-28.
[12] C. Dürr, M. Heiligman, P. Høyer, and M. Mhalla, “Quantum query complexity of some graph problems,” SIAM J. Comput., 35, No. 6, 1310-1328 (2006). · Zbl 1101.81024 · doi:10.1137/050644719
[13] C. Dürr and P. Høyer, “A quantum algorithm for finding the minimum,” arxiv.org/abs/quant-ph/9607014
[14] E. Farhi, J. Goldstone, and S. Gutmann, “A quantum algorithm for the Hamiltonian NAND tree,” Theory Comput., 4, 169-190 (2008). · Zbl 1213.68284 · doi:10.4086/toc.2008.v004a008
[15] E. Farhi, J. Goldstone, S. Gutmann, M. Sipser, “Invariant quantum algorithms for insertion into an ordered list,” arxiv.org/abs/quant-ph/9901059
[16] I. P. Gent and T. Walsh, “The TSP phase transition,” Artificial Intelligence, 88, No. 1, 349-358 (1996). · Zbl 0907.68177 · doi:10.1016/S0004-3702(96)00030-6
[17] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in: Proc. 28 Ann. Symp. on the Theory of Computing, ACM Press, New York (1996), pp. 212-219. · Zbl 0922.68044
[18] P. Høyer, J. Neerbek, and Y. Shi, “Quantum complexities of ordered searching, sorting, and element distinctness,” Algorithmica, 34, No. 4, 429-448 (2002). · Zbl 1012.68071 · doi:10.1007/s00453-002-0976-3
[19] H. Kesten and S. Lee, “The central limit theorem for weighted minimal spanning trees on random points,” Ann. Probab., 6, No. 2, 495-527 (1996). · Zbl 0862.60008 · doi:10.1214/aoap/1034968141
[20] L. A. B. Kowada, C. Lavor, R. Portugal, and C. M. H. de Figueiredo, “A new quantum algorithm for solving the minimum searching problem,” Int. J. Quantum Inform., 6, No. 3, 427-436 (2008). · Zbl 1192.81085 · doi:10.1142/S021974990800361X
[21] S. Mandrà, G. G. Guerreschi, and A. Aspuru-Guzik, “Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems,” New J. Phys., 18, No. 7, 073003 (2016). · Zbl 1456.81147 · doi:10.1088/1367-2630/18/7/073003
[22] B. W. Reichardt, “Reflections for quantum query algorithms,” in: Proc. 22 ACM-SIAM Symp. on Discrete Algorithms (2011), pp. 560-569; arxiv.org/abs/1005.1601 · Zbl 1373.68230
[23] M. Steele, “Growth rates of Euclidean minimal spanning trees with power weighted edges,” Ann. Probab., 16, No. 4, 1767-1787 (1988). · Zbl 0655.60023 · doi:10.1214/aop/1176991596
[24] H. Wagner, Principles of Operations Research, Prentice Hall, Englewood Cliffs, New Jersey (1969). · Zbl 0193.18402
[25] T. J. Yoder, G. H. Low, and I. L. Chuang, “Fixed-point quantum search with an optimal number of queries,” Phys. Rev. Lett., 113, 210501 (2014). · doi:10.1103/PhysRevLett.113.210501
[26] W. Zhang, State-Space Search: Algorithms, Complexity, Extensions, and Applications, Springer-Verlag (1999). · Zbl 0942.90001
[27] D. A. Zholobov, Introduction in Mathematical Programming [in Russian], MEPhI, Moscow (2008).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.