Quantum algorithm for minimum dominating set problem with circuit design

doi:10.1088/1674-1056/ad02e5

中国物理B ›› 2024, Vol. 33 ›› Issue (2): 20310-020310.doi: 10.1088/1674-1056/ad02e5

Quantum algorithm for minimum dominating set problem with circuit design

Haoying Zhang(张皓颖)¹, Shaoxuan Wang(王绍轩)¹, Xinjian Liu(刘新建)¹, Yingtong Shen(沈颖童)¹, 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

收稿日期:2023-06-14 修回日期:2023-10-03 接受日期:2023-10-13 出版日期:2024-01-16 发布日期:2024-01-25
通讯作者: Yukun Wang E-mail:wykun06@gmail.com
基金资助:
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).

Quantum algorithm for minimum dominating set problem with circuit design

Haoying Zhang(张皓颖)¹, Shaoxuan Wang(王绍轩)¹, Xinjian Liu(刘新建)¹, Yingtong Shen(沈颖童)¹, 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

Received:2023-06-14 Revised:2023-10-03 Accepted:2023-10-13 Online:2024-01-16 Published:2024-01-25
Contact: Yukun Wang E-mail:wykun06@gmail.com
Supported by:
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).

摘要/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.

关键词: quantum algorithm, circuit design, minimum dominating set

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.

Key words: quantum algorithm, circuit design, minimum dominating set

中图分类号: (Quantum algorithms, protocols, and simulations)

03.67.Ac

Haoying Zhang(张皓颖), Shaoxuan Wang(王绍轩), Xinjian Liu(刘新建), Yingtong Shen(沈颖童), and Yukun Wang(王玉坤). Quantum algorithm for minimum dominating set problem with circuit design[J]. 中国物理B, 2024, 33(2): 20310-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

Quantum algorithm for minimum dominating set problem with circuit design

Quantum algorithm for minimum dominating set problem with circuit design

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Peng-Fei Song(宋鹏飞) and Dan-Bo Zhang(张旦波). Simulation of optimal work extraction for quantum systems with work storage[J]. 中国物理B, 2024, 33(2): 20312-020312.
[2]	Zhi-Quan Shi(石志全), Xu-Dan Xie(谢旭丹), and Dan-Bo Zhang(张旦波). Variational quantum simulation of the quantum critical regime[J]. 中国物理B, 2023, 32(8): 80305-080305.
[3]	Yan-Yan Hou(侯艳艳), Jian Li(李剑), Xiu-Bo Chen(陈秀波), and Chong-Qiang Ye(叶崇强). Variational quantum semi-supervised classifier based on label propagation[J]. 中国物理B, 2023, 32(7): 70309-070309.
[4]	Shang Gao(高尚) and Yu-Guang Yang(杨宇光). A quantum algorithm for Toeplitz matrix-vector multiplication[J]. 中国物理B, 2023, 32(10): 100309-100309.
[5]	Xue-Yi Guo(郭学仪), Shang-Shu Li(李尚书), Xiao Xiao(效骁), Zhong-Cheng Xiang(相忠诚), Zi-Yong Ge(葛自勇), He-Kang Li(李贺康), Peng-Tao Song(宋鹏涛), Yi Peng(彭益), Zhan Wang(王战), Kai Xu(许凯), Pan Zhang(张潘), Lei Wang(王磊), Dong-Ning Zheng(郑东宁), and Heng Fan(范桁). Variational quantum simulation of thermal statistical states on a superconducting quantum processer[J]. 中国物理B, 2023, 32(1): 10307-010307.
[6]	Shi-Jie Pan(潘世杰), Lin-Chun Wan(万林春), Hai-Ling Liu(刘海玲), Yu-Sen Wu(吴宇森), Su-Juan Qin(秦素娟), Qiao-Yan Wen(温巧燕), and Fei Gao(高飞). Quantum algorithm for neighborhood preserving embedding[J]. 中国物理B, 2022, 31(6): 60304-060304.
[7]	Dan-Bo Zhang(张旦波), Bin-Lin Chen(陈彬琳), Zhan-Hao Yuan(原展豪), and Tao Yin(殷涛). Variational quantum eigensolvers by variance minimization[J]. 中国物理B, 2022, 31(12): 120301-120301.
[8]	Xiao-Yuan Wang(王晓媛), Chuan-Tao Dong(董传涛), Zhi-Ru Wu(吴志茹), and Zhi-Qun Cheng(程知群). A review on the design of ternary logic circuits[J]. 中国物理B, 2021, 30(12): 128402-128402.
[9]	麦麦提依明·吐孙, 伍旸, 刘文权, 荣星, 杜江峰. Experimental implementation of a continuous-time quantum random walk on a solid-state quantum information processor[J]. 中国物理B, 2019, 28(11): 110302-110302.
[10]	戴坤哲, 赵鹏, 李蒙蒙, 谭新生, 于海峰, 于扬. Demonstration of quantum permutation parity determine algorithm in a superconducting qutrit[J]. 中国物理B, 2018, 27(6): 60305-060305.
[11]	何广平. Coherent attacks on a practical quantum oblivious transfer protocol[J]. 中国物理B, 2018, 27(10): 100308-100308.
[12]	王蕊, 孙辉, 王杰智, 王鲁, 王晏超. Applications of modularized circuit designs in a new hyper-chaotic system circuit implementation[J]. , 2015, 24(2): 20501-020501.
[13]	薛薇, 徐进康, 仓诗建, 贾红艳. Synchronization of the fractional-order generalized augmented Lü system and its circuit implementation[J]. 中国物理B, 2014, 23(6): 60501-060501.
[14]	付向群, 鲍皖苏, 李发达, 张宇超. Realization of quantum Fourier transform over Z_N[J]. 中国物理B, 2014, 23(2): 20306-020306.
[15]	王洪福, 张寿. Application of quantum algorithms to direct measurement of concurrence of a two-qubit pure state[J]. 中国物理B, 2009, 18(7): 2642-2648.