Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (6): 351-357.doi: 10.11896/jsjkx.220400051

• Interdiscipline & Frontier • Previous Articles     Next Articles

Solving Graph Coloring Problem Based on Grover Algorithm

LIU Xiaonan1, LIU Zhengyu2, XIE Haoshan1, ZHAO Chenyan1   

  1. 1 State Key Laboratory of Mathematical Engineering and Advanced Computing,PLA Information Engineering University,Zhengzhou 450000,China
    2 School of Computer and Artificial Intelligence,Zhengzhou University,Zhengzhou 450000,China
  • Received:2022-04-06 Revised:2022-09-22 Online:2023-06-15 Published:2023-06-06
  • About author:LIU Xiaonan,born in 1977,Ph.D,associate professor,master’s supervisor,is a member of China Computer Federation.His main research interests include quantum algorithm and high-perfor-mance parallel computation.LIU Zhengyu,born in 1997,postgra-duate,is a member of China Computer Federation.His main research interests include quantum algorithm and quantum machine learning.
  • Supported by:
    National Natural Science Foundation of China(61972413,61701539).

PDF (PC)

312

Abstract: Grover quantum search algorithm is a famous quantum algorithm designed for unstructured search problems.It can be used to solve problems such as graph coloring and shortest path sorting,and can also effectively decipher cryptosystems.Graph coloring problem is one of the most famous NP complete problems.In this paper,the graph coloring problem is transformed into an undirected graph in mathematics,and then it is transformed into a Boolean satisfiability problem by using Boolean expression.The steps and principles of solving Boolean expression in quantum circuit diagram and the transformation process from graph co-loring problem to Boolean satisfiability problem are introduced.Finally,on the IBMQ cloud platform,for the three nodes,2-coloring problem and 4-coloring problem are simulated.Experimental results verify the feasibility of using Grover algorithm to solve the graph coloring problem.In the 2-coloring problem with search space of 8 and the 4-coloring problem with search space of 64,the target items are searched with nearly 82% and 97% success probability respectively.In this paper,Grover algorithm is used to solve the 4-coloring problem,expand the experimental scale of the algorithm in this problem field,and improve the quantum circuit of the existing experiments,so that the qubit cost is lower and the result success rate is higher,which shows the remarkable acceleration effect of Grover algorithm in large-scale search problems.

Key words: Grover algorithm, Graph coloring problem, Quantum circuit, IBMQ, Boolean satisfiability problem

CLC Number: 

  • TP385
[1]HUANG H L,WU D C,FAN D J,et al.Superconducting quantum computing:a review[J].Science China Information Sciences,2020,63(8):595-600.
[2]LIU X N,SONG H C,WANG HON,et al.Overview of improvement and application of Grover algorithm [J].Computer Science,2021,48(10):315-323.
[3]SHIMIZU K,MORI R.Exponential-time quantum algorithmsfor graph coloring problems[J].2022,84(12):3603-3621.
[4]FERNANDES D,SILVA C,DUTRA I.Using Grover's search quantum algorithm to solve Boolean satisfiability problems,part 2[J].Crossroads,2019,26(2):68-71.
[5]SANYAL B A,SAHA A,SAHA B,et al.Circuit design for clique problem and its implementation on quantum computer[J].IET Quantum Communication,2021,3(1):30-49.
[6]SAHA A,CHONGDER A,MANDAL S B,et al.Synthesis ofVertex Coloring Problem Using Grover's Algorithm[C]//IEEE International Symposium on Nanoelectronic & Information Systems.IEEE,2016.
[7]SAHA A,SAHA D,CHAKRABARTI A.Circuit Design for K-coloring Problem and it's Implementation on Near-term Quantum Devices[C]//2020 IEEE International Symposium of Smart Electronic Systems(isEs),Chennai,India.2020:17-22.
[8]HU S,LIU P,CHEN C,et al.Reduction-Based Problem Mapping for Quantum Computing[J].Computer,2019,52(6):47-57.
[9]YANG M T.Algorithms on Graph Coloring Problem[J].Journal of Physics:Conference series,2020,1634(1):012053.
[10]RYBALOV A N.On generic NP-completeness of the Booleansatisfiability problem[J].Prikladnaya Diskretnaya Matematika,2017(36):106-112.
[11]LI G,DING Y,XIE Y.Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices[C]//the Twenty-Fourth International Conference.2019.
[12]SCHWABE P,WESTERBAAN B.Solving binary MQ withGrover's algorithm[J/OL].https://eprint.iacr.org/2019/151.pdf.
[13]SONG H C,LIU X N,WANG H,et al.Integer Decomposition Based on Grover search algorithm [J].Computer Science,2021,48(4):20-25.
[14]MAREK S,MAREK W.Recommendation systems with thequantum k-NN and Grover algorithms for data processing[J].International Journal of Applied Mathematics and Computer Science,2019,29(1):139-150.
[15]YANG S Q,DENG Z Y,LI B.Improved Grover quantum search algorithm [J].Journal of Nanchang University(Science Edition),2017,41(6):581-584.
[16]KAIN B.Searching a quantum database with Grover's search algorithm[J].American Journal of Physics,2021,89(6):618-626.
[17]MAGNIEZ F,SANTHA M,SZEGEDY M.Quantum Algo-rithms for the Triangle Problem[J].SIAM Journal on Computing,2007,37(2):413-424.
[18]SHARMA P C,CHAUDHARI N S.Investigation of Satisfiability Based Solution Approach for Graph Coloring Problem[J].International Journal of Engineering and Advanced Technology(IJEAT),2016,6(1):106-112.
[1] LIU Jian-mei, WANG Hong, MA Zhi. Optimization for Shor's Integer Factorization Algorithm Circuit [J]. Computer Science, 2022, 49(6A): 649-653.
[2] WANG Jian-chang, WANG Shuo, LI Zhuang, JIANG Hua. Improved Algorithm for Tabu Search of Graph Coloring Problems [J]. Computer Science, 2022, 49(11A): 211000128-5.
[3] SONG Hui-chao, LIU Xiao-nan, WANG Hong, YIN Mei-juan, JIANG Duo. Integer Decomposition Based on Grover Search Algorithm [J]. Computer Science, 2021, 48(4): 20-25.
[4] LIU Xiao-nan, SONG Hui-chao, WANG Hong, JIANG Duo, AN Jia-le. Survey on Improvement and Application of Grover Algorithm [J]. Computer Science, 2021, 48(10): 315-323.
[5] LIU Jiang, ZHOU Hong-hao. New Algebraic Logic Reduction Method for Boolean Formula [J]. Computer Science, 2020, 47(5): 32-37.
[6] GAO Chao-xin, CHEN Xin and XIANG Xu-dong. Intelligent Optimization Algorithm for Interference Coordination in LTE-A Femtocell System [J]. Computer Science, 2015, 42(8): 273-278.
[7] FAN Fu-you, YANG Guo-wu, ZHANG Yan and YANG Gang. Three-valued Quantum Elementary and Implementation of Quantum Fourier Transform Circuit [J]. Computer Science, 2015, 42(7): 57-61.
[8] FAN Fu-you,YANG Guo-wu,LI Xiao-yu and LUO Qing-bin. Realization of Toffoli Gate Only Using CNOT Gate in Hybrid Multi-value Reversible Logic [J]. Computer Science, 2014, 41(8): 115-117.
[9] LUO Qing-bin,YANG Guo-wu,SHAO Yuan-hua and FAN Fu-you. Judgment of NP-NP Equivalence for 3-bit Reversible Logic Functions via Fixed Polarity Reed-muller Forms [J]. Computer Science, 2013, 40(10): 218-220.
[10] . [J]. Computer Science, 2008, 35(3): 13-17.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.