计算机科学 ›› 2023, Vol. 50 ›› Issue (6): 351-357.doi: 10.11896/jsjkx.220400051
刘晓楠1, 刘正煜2, 谢浩山1, 赵晨言1
LIU Xiaonan1, LIU Zhengyu2, XIE Haoshan1, ZHAO Chenyan1
摘要: Grover量子搜索算法是针对非结构化搜索问题设计的著名量子算法,可用于解决图着色、最短路径排序等问题,也可以有效破译密码系统。图着色问题是最著名的NP-完全问题之一,文中首先将图着色问题转化为数学上的无向图;然后采用布尔表达式将其转换为布尔可满足性问题,介绍了量子线路图解决布尔表达式的步骤原理以及图着色问题向布尔可满足性问题的转换过程;最后在IBMQ云平台上,对三节点的2-着色问题以及4-着色问题进行模拟仿真。实验结果验证了使用Grover算法求解图着色问题的可行性,在搜索空间为8的2-着色问题和搜索空间为64的4-着色问题中,分别以近82%和97%的成功概率搜索到目标项。文中使用Grover算法解决了4-着色问题,拓展了该算法在此问题领域上的实验规模,且改进了现有实验的量子线路,使量子位成本更低,结果的成功率更高,展示了Grover算法在大型搜索问题中显著的加速效果。
中图分类号:
[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. |
|