|
|
|
Quantum algorithm for minimum dominating set problem with circuit design |
| Haoying Zhang(张皓颖)1, Shaoxuan Wang(王绍轩)1, Xinjian Liu(刘新建)1, Yingtong Shen(沈颖童)1, and Yukun Wang(王玉坤)1,2,† |
1 Beijing Key Laboratory of Petroleum Data Mining, China University of Petroleum, Beijing 102249, China;
2 State Key Laboratory of Cryptology, P. O. Box 5159, Beijing 100878, China |
|
|
|
|
Abstract Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing. Researchers are particularly interested in using the acceleration properties of quantum algorithms to solve NP-complete problems. This paper focuses on the well-known NP-complete problem of finding the minimum dominating set in undirected graphs. To expedite the search process, a quantum algorithm employing Grover's search is proposed. However, a challenge arises from the unknown number of solutions for the minimum dominating set, rendering direct usage of original Grover's search impossible. Thus, a swap test method is introduced to ascertain the number of iterations required. The oracle, diffusion operators, and swap test are designed with achievable quantum gates. The query complexity is $O(1.414^n)$ and the space complexity is $O(n)$. To validate the proposed approach, qiskit software package is employed to simulate the quantum circuit, yielding the anticipated results.
|
Received: 14 June 2023
Revised: 03 October 2023
Accepted manuscript online: 13 October 2023
|
|
PACS:
|
03.67.Ac
|
(Quantum algorithms, protocols, and simulations)
|
|
| Fund: Project supported by the National Natural Science Foundation of China (Grant No. 62101600), the Science Foundation of China University of Petroleum, Beijing (Grant No. 2462021YJRC008), and the State Key Laboratory of Cryptology (Grant No. MMKFKT202109). |
Corresponding Authors:
Yukun Wang
E-mail: wykun06@gmail.com
|
Cite this article:
Haoying Zhang(张皓颖), Shaoxuan Wang(王绍轩), Xinjian Liu(刘新建), Yingtong Shen(沈颖童), and Yukun Wang(王玉坤) Quantum algorithm for minimum dominating set problem with circuit design 2024 Chin. Phys. B 33 020310
|
[1] Khadiev K and Ilikaev A 2019 International Conference on Theory and Practice of Natural Computing, December 9-11, 2019, Kingston, Canada, p. 234
[2] Lee T, Magniez F and Santha M 2017 Algorithmica 77 459
[3] Friedman J R, Patel V, Chen W, Tolpygo S K and Lukens J E 2000 Nature 406 43
[4] Ficek Z and Swain S 2005 Quantum interference and coherence: theory and experiments (Heidelberg: Springer Science & Business Media) Vol. 100 p. 3
[5] Horodecki R, Horodecki P, Horodecki M and Horodecki K 2009 Rev. Mod. Phys. 81 865
[6] Jeffery S, Kothari R, Le Gall F and Magniez F 2016 Algorithmica 76 1
[7] Kravchenko D, Khadiev K and Serov D 2019 International Computer Science Symposium, July 1-5, 2019, Novosibirsk, Russia, p. 228
[8] Shukla A and Vedula P 2019 J. Global Optim. 75 199
[9] Mukherjee S 2022 IEEE Trans. Quantum Eng. 3 3101008
[10] Saha A, Saha D and Chakrabarti A 2020 IEEE International Symposium on Smart Electronic Systems (iSES) (Formerly iNiS), December 20-22, 2020, India, Jaipur, p. 17
[11] Shimizu K and Mori R 2022 Algorithmica 84 3603
[12] Wang Y and Perkowski M 2011 IEEE International Symposium on Multiple-Valued Logic, May 23-25, 2011, Tuusula, Finland, p. 294
[13] Saha A, Chongder A, Mandal S B and Chakrabarti A 2015 IEEE International Symposium on Nanoelectronic and Information Systems, December 19-21, 2015, Bhubaneswar, India, p. 101
[14] Aghae M R S, Zukarnain Z A, Mamat A and Zainuddin H 2008 International Conference on Advanced Computer Theory and Engineering, July 29-30, 2008, Phuket, Thailand, p. 251
[15] Fujimura T 2024 Global J. Pure Appl. Math. 6 263
[16] Hartmanis J 1982 SIAM Rev. 24 90
[17] Karbasi A H and Atani R E 2013 Int. J. Secur. Its Appl 7 185
[18] Sanchis L A 2002 Algorithmica 33 3
[19] Hedar A R and Ismail R 2010 International conference on computational science and its applications, March 23-26, 2010, Fukuoka, Japan, p. 457
[20] Fomin F V, Kratsch D and Woeginger G J 2004 International Workshop on Graph-Theoretic Concepts in Computer Science, June 25-27, 2004, Berlin, Heidelberg, p. 245
[21] Van Rooij J M and Bodlaender H L 2011 Discrete Appl. Math 159 2147
[22] Fomin F V, Grandoni F and Kratsch D 2005 International Colloquium on Automata, Languages, and Programming, July 4-8, 2005, Lisbon, Portugal, p. 191
[23] Schiermeyer I 2008 Discrete Appl. Math. 156 3291
[24] Van Rooij J M and Bodlaender H L 2008 arXiv:0802.2827 [cs.DS]
[25] Fomin F V, Grandoni F and Kratsch D J 2009 J. ACM 56 25
[26] Iwata Y 2011 International Symposium on Parameterized and Exact Computation, September 8-10, 2011, Berlin, p. 41
[27] Grover L K 1997 Phys. Rev. Lett. 79 325
[28] Grover L K 1998 Phys. Rev. Lett. 80 4329
[29] Long G L, Li Y S, Zhang W L and Tu C C 2000 Phys. Rev. A 61 042305
[30] Chuang I L, Gershenfeld N and Kubinec M 1998 Phys. Rev. Lett. 80 3408
[31] Boyer M, Brassard G, Hoyer P and Tapp A 1998 Fortschritte der Phys. 46 493
[32] Zhu W, Chen H, Liu Z and Xue X 2014 International Conference in Swarm Intelligence, June 12-15, 2014, Hefei, China, p. 357
[33] Aaronson S and Rall P 2020 Symposium on Simplicity in Algorithms, January 5-8, 2020, Salt Lake City, Utah, USA, p. 24
[34] Guo Y, Shi W, Wang Y and Hu J 2017 J. Phys. Soc. Jpn. 86 024006
[35] Ma B W, Bao W S, Li T, Li F G, Zhang S and Fu X Q 2017 Chin. Phys. Lett. 34 070305
[36] Korepin V E and Grover L K 2006 Quantum Inf. Process. 5 5
[37] Younes A, Rowe J and Miller J 2008 Physica D 237 1074
[38] Barenco A, Bennett C H, Cleve R, DiVincenzo D P, Margolus N, Shor P and Weinfurter H 1995 Phys. Rev. A 52 3457
[39] Haynes T W, Hedetniemi S and Slater P 2013 Fundamentals of domination in graphs (New York: CRC Press) p. 5
[40] Haynes T W, Hedetniemi S T and Henning M A (eds) 2017 Topics in Domination in Graphs (Cham: Springer) Vol. 2 pp. 13-30
[41] Saeedi M and Pedram M 2013 Phys. Rev. A 87 062318
[42] Da Silva A J and Park D K 2022 Phys. Rev. A 106 042602
[43] Vartiainen J J, Möttönen M and Salomaa M M 2004 Phys. Rev. Lett 92 177902
[44] He Y, Luo M X, Zhang E, Wang H K and Wang X F 2017 Int. J. Theor. Phys 56 2350
[45] Vale R, Azevedo T M D, Araújo I, Araujo I F and da Silva A J 2023 arXiv:2302.06377 [quant-ph]
[46] Buhrman H, Cleve R, Watrous J and De Wolf R 2001 Phys. Rev. Lett. 87 167902
[47] Grandoni F 2006 J. Discrete Algorithms 4 209
[48] Long G L 2001 Phys. Rev. A 64 022307 |
| No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
Altmetric
|
|
blogs
Facebook pages
Wikipedia page
Google+ users
|
Online attention
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
View more on Altmetrics
|
|
|
