Top

Quantum Information Processing

Published in:

01-07-2023

Quantum speedup for solving the minimum vertex cover problem based on Grover search algorithm

Authors: Zhaocai Wang, Kun Liang, Xiaoguang Bao, Tunhua Wu

Published in: Quantum Information Processing | Issue 7/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The electronic computer possesses powerful computing capabilities, but it is still limited by Moore’s law. Quantum computers are thus found capable of not only overcoming the constraints of Moore’s law but also taking advantage of the quantum effect to increase their arithmetic power for many problems. The minimum vertex cover problem is a classical NP-complete problem, and its traditional algorithms usually require exponential computational complexity. Herein, two algorithms are proposed to solve the minimum vertex cover problem. The first algorithm achieves its classical solution, while the second algorithm is based on the Grover search algorithm to obtain the solution to the quantum computing algorithm of the problem and verify its feasibility via quantum circuit experiments. Comparing the two algorithms, it can be concluded that the quantum algorithm can improve the operational speed of the minimum vertex cover problem by order of magnitude of the square root.

previous article Quantum circuits for discrete-time quantum walks with position-dependent coin operator

next article Efficient multiparty quantum private comparison protocol based on single photons and rotation encryption

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Islam, A., Kalita, B.: Application of minimum vertex cover for keyword-based text summarization process. Int. J. Comput. Intell. Res. 13(1), 113–125 (2017)

Yigit, Y., Akram, V.K., Dagdeviren, O.: Breadth-first search tree integrated vertex cover algorithms for link monitoring and routing in wireless sensor networks. Comput. Netw. 194, 108–144 (2021)CrossRef

Khamayseh, Y., Mardini, W., Shatnawi, A.: An approximation algorithm for vertex cover problem. In: International Conference on Computer Networks and Communication Systems (2012)

Ambühl, C., Mastrolilli, M.: Single machine precedence constrained scheduling is a vertex cover problem. Algorithmica 53(4), 488–503 (2009)MathSciNetCrossRefMATH

Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 439–485 (2005)

Yuan, S.-Y., Kuo, S.-Y.: A new technique for optimization problems in graph theory. IEEE Trans. Comput. 47(2), 190–196 (1998)ADSMathSciNetCrossRefMATH

Bhasin, H., Amini, M.: The applicability of genetic algorithm to vertex cover. Int. J. Comput. Appl. 123(17), 29–34 (2015)

Chen, M., Zhou, B., Ren, Z.: Genetic algorithm based on random uniform design. Appl. Math. A J. Chin. Univ. 25(3), 279–283 (2010)MathSciNetMATH

Gao, L., Xu, J.: DNA algorithm for minimum vertex cover problem based on molecular computation. Syst. Eng. Electron. 26(4), 544–548 (2004)

10.

Hasudungan, R., Pangestuty, D.M., Latifah, A.J., et al.: Solving minimum vertex cover problem using DNA computing. J. Phys. Conf. Ser. 1361, 012038 (2019)CrossRef

11.

Zhang, Y., Mu, X., Liu, X.-W., Wang, X., Zhang, X., Li, K., Wu, T., Zhao, D., Dong, C.: Applying the quantum approximate optimization algorithm to the minimum vertex cover problem. Appl. Soft Comput. 118, 108554 (2022)CrossRef

12.

Chen, J., Xu, R.: Minimum vertex cover problem based on ant colony algorithm. In: 7th Advanced Forum on Transportation of China (AFTC 2011), pp. 125–129 (2011). IET

13.

Landauer, R.: Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 44(1/2), 261–269 (2000)CrossRef

14.

Cho, C.-H., Chen, C.-Y., Chen, K.-C., Huang, T.-W., Hsu, M.-C., Cao, N.-P., Zeng, B., Tan, S.-G., Chang, C.-R.: Quantum computation: algorithms and applications. Chin. J. Phys. 72, 248–269 (2021)MathSciNetCrossRef

15.

Wong, R., Chang, W.-L.: Quantum speedup for protein structure prediction. IEEE Trans. Nanobiosci. 20(3), 323–330 (2021)CrossRef

16.

Brassard, G., Høyer, P., Tapp, A.: Quantum counting. In: International Colloquium on Automata, Languages, and Programming, pp. 820–831 (1998). Springer

17.

Benioff, P.: Quantum mechanical hamiltonian models of turing machines. J. Stat. Phys. 29(3), 515–546 (1982)ADSMathSciNetCrossRefMATH

18.

Deutsch, D.: Quantum theory, the church-turing principle and the universal quantum computer. Proc. R. Soc. Lond. A Math. Phys. Sci. 400(1818), 97–117 (1985)ADSMathSciNetMATH

19.

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)ADSMathSciNetCrossRefMATH

20.

Grover, L.K.: A fast quantum mechanical algorithm for database search, 212–219 (1996)

21.

Uno, S., Suzuki, Y., Hisanaga, K., Raymond, R., Tanaka, T., Onodera, T., Yamamoto, N.: Modified Grover operator for quantum amplitude estimation. New J. Phys. 23(8), 083031 (2021)ADSMathSciNetCrossRef

22.

Liu, Y., Koehler, G.J.: Using modifications to Grover’s search algorithm for quantum global optimization. Eur. J. Oper. Res. 207(2), 620–632 (2010)MathSciNetCrossRefMATH

23.

Panchi, L., Shiyong, L.: Grover quantum searching algorithm based on weighted targets. J. Syst. Eng. Electron. 19(2), 363–369 (2008)CrossRefMATH

24.

Narayanan, A., Moore, M.: Quantum-inspired genetic algorithms. In: Proceedings of IEEE International Conference on Evolutionary Computation, pp. 61–66 (1996). IEEE

25.

Han, K.-H., Kim, J.-H.: Genetic quantum algorithm and its application to combinatorial optimization problem. In: Proceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No. 00TH8512), vol. 2, pp. 1354–1360 (2000). IEEE

26.

Wang, L., Tang, F., Wu, H.: Hybrid genetic algorithm based on quantum computing for numerical optimization and parameter estimation. Appl. Math. Comput. 171(2), 1141–1156 (2005)MathSciNetMATH

27.

Ma, X.-L., Li, Y.-G.: An improved quantum ant colony algorithm and its application. IERI Procedia 2, 522–527 (2012)CrossRef

28.

Wang, L., Niu, Q., Fei, M.: A novel quantum ant colony optimization algorithm and its application to fault diagnosis. Trans. Inst. Meas. Control. 30(3–4), 313–329 (2008)CrossRef

29.

Tao, W., Lei, X., Xi, C., Amir, H.A., Shu, Z.: A novel quantum-behaved particle swarm optimization algorithm. CMC-Comput. Mater. Continua 63(2), 873–890 (2020)

30.

Zhou, N.-R., Xia, S.-H., Ma, Y., Zhang, Y.: Quantum particle swarm optimization algorithm with the truncated mean stabilization strategy. Quantum Inf. Process. 21(2), 1–23 (2022)ADSMathSciNetCrossRefMATH

31.

Kak, S.C.: Quantum neural computing. Adv. Imaging Electron. Phys. 94, 259–313 (1995)CrossRef

32.

Panchi, L., Kaoping, S., Erlong, Y.: Quantum neural networks model and algorithm based on the quantum gates circuit. Control Decision 27(1), 143–146 (2012)MathSciNet

33.

Panchi, L., Shiyong, L.: Learning algorithm and application of quantum bp neural networks based on universal quantum gates. J. Syst. Eng. Electron. 19(1), 167–174 (2008)CrossRefMATH

34.

Chen, J., Wang, L., Charbon, E.: A quantum-implementable neural network model. Quantum Inf. Process. 16(10), 1–24 (2017)MathSciNetCrossRefMATH

35.

Yu, H., Wilczek, F., Wu, B.: Quantum algorithm for approximating maximum independent sets. Chin. Phys. Lett. 38(3), 30304 (2021)CrossRef

36.

Bonnetain, X., Bricout, R., Schrottenloher, A., Shen, Y.: Improved classical and quantum algorithms for subset-sum. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 633–666 (2020). Springer

37.

Zheng, Q., Zhu, P., Xue, S., Wang, Y., Wu, C., Yu, X., Yu, M., Liu, Y., Deng, M., Wu, J., et al.: Quantum algorithm and experimental demonstration for the subset sum problem. Sci. China Inf. Sci. 65(8), 1–14 (2022)ADSMathSciNetCrossRef

38.

Wen-Zhang, L., Jing-Fu, Z., Gui-Lu, L.: A parallel quantum algorithm for the satisfiability problem. Commun. Theor. Phys. 49(3), 629–630 (2008)ADSCrossRefMATH

39.

Chang, W.-L., Chung, W.-Y., Hsiao, C.-Y., Wong, R., Chen, J.-C., Feng, M., Vasilakos, A.V.: Quantum speedup for inferring the value of each bit of a solution state in unsorted databases using a bio-molecular algorithm on IBM Quantum’s computers. IEEE Trans. Nanobiosci. 21(2), 286–293 (2021)CrossRef

40.

Mölle, D., Richter, S., Rossmanith, P.: Enumerate and expand: New runtime bounds for vertex cover variants. In: Computing and Combinatorics: 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, Aug 15-18, 2006. Proceedings 12, pp. 265–273 (2006). Springer

41.

Wu, X., Wang, Z., Wu, T., Bao, X.: Solving the family traveling salesperson problem in the Adleman-Lipton model based on DNA computing. IEEE Trans. Nanobiosci. 21(1), 75–85 (2021)CrossRef

42.

Wang, Z., Deng, A., Wang, D., Wu, T.: A parallel algorithm to solve the multiple travelling salesmen problem based on molecular computing model. Int. J. Bio-Inspired Comput. 20(3), 160–171 (2022)CrossRef

Title: Quantum speedup for solving the minimum vertex cover problem based on Grover search algorithm
Authors: Zhaocai Wang
Kun Liang
Xiaoguang Bao
Tunhua Wu
Publication date: 01-07-2023
Publisher: Springer US
Published in: Quantum Information Processing / Issue 7/2023
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI: https://doi.org/10.1007/s11128-023-04010-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 7/2023

A secure controlled quantum image steganography scheme based on the multi-channel effective quantum image representation model

Deterministic hierarchical quantum operation sharing with five-qubit partially entangled states

A doubly stochastic matrices-based approach to optimal qubit routing

Star network quantum steering

Logical qubit behavior model and fast simulation for surface code

Evolutionary-based searching method for quantum circuit architecture