Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (3): 849-854.DOI: 10.11772/j.issn.1001-9081.2023030332
• Advanced computing • Previous Articles Next Articles
Lingling GUO, Zhiqiang LI(), Menghuan DUAN
Received:
2023-03-30
Revised:
2023-04-13
Accepted:
2023-04-17
Online:
2023-05-09
Published:
2024-03-10
Contact:
Zhiqiang LI
About author:
GUO Lingling, born in 1999, M. S. candidate. Her research interests include quantum circuit, quantum algorithms.Supported by:
通讯作者:
李志强
作者简介:
郭玲玲(1999—),女,江苏盐城人,硕士研究生,主要研究方向:量子电路、量子算法基金资助:
CLC Number:
Lingling GUO, Zhiqiang LI, Menghuan DUAN. Application of quantum approximate optimization algorithm in exact cover problems[J]. Journal of Computer Applications, 2024, 44(3): 849-854.
郭玲玲, 李志强, 段孟环. 量子近似优化算法在精确覆盖问题中的应用[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 849-854.
Add to citation manager EndNote|Ris|BibTeX
URL: http://www.joca.cn/EN/10.11772/j.issn.1001-9081.2023030332
U中的元素 | 集合 | |
---|---|---|
1,2,3,4,5,6,7 | 1,2,3,6 | |
1,3,6 | ||
4,5,7 | ||
7 |
Tab.1 Example of exact cover problem
U中的元素 | 集合 | |
---|---|---|
1,2,3,4,5,6,7 | 1,2,3,6 | |
1,3,6 | ||
4,5,7 | ||
7 |
迭代次数 | 损失值 | 迭代次数 | 损失值 |
---|---|---|---|
160 | 2.156 250 000 | 260 | 2.087 890 625 |
180 | 2.109 375 000 | 280 | 2.087 890 625 |
200 | 2.099 609 375 | 300 | 2.087 890 625 |
220 | 2.089 843 750 | 320 | 2.087 890 625 |
240 | 2.087 890 625 |
Tab. 2 Corresponding loss values with evolution steps of 11 for different iterations
迭代次数 | 损失值 | 迭代次数 | 损失值 |
---|---|---|---|
160 | 2.156 250 000 | 260 | 2.087 890 625 |
180 | 2.109 375 000 | 280 | 2.087 890 625 |
200 | 2.099 609 375 | 300 | 2.087 890 625 |
220 | 2.089 843 750 | 320 | 2.087 890 625 |
240 | 2.087 890 625 |
演化步数 | 正确概率/% | 演化步数 | 正确概率/% |
---|---|---|---|
2 | 33.1 | 8 | 92.3 |
3 | 41.4 | 9 | 81.9 |
4 | 53.3 | 10 | 94.7 |
5 | 58.3 | 11 | 95.6 |
6 | 82.5 | 12 | 93.2 |
7 | 88.9 |
Tab. 3 Correct probabilities of problems with iterations of 240 for different evolution steps
演化步数 | 正确概率/% | 演化步数 | 正确概率/% |
---|---|---|---|
2 | 33.1 | 8 | 92.3 |
3 | 41.4 | 9 | 81.9 |
4 | 53.3 | 10 | 94.7 |
5 | 58.3 | 11 | 95.6 |
6 | 82.5 | 12 | 93.2 |
7 | 88.9 |
测量结果 | 正确概率/% | 测量结果 | 正确概率/% |
---|---|---|---|
0010 | 0.2 | 1010 | 95.6 |
0110 | 2.8 | 1011 | 0.5 |
1000 | 0.1 | 1110 | 0.7 |
1001 | 0.1 |
Tab. 4 Measurements with evolution steps of 11 and iterations of 240
测量结果 | 正确概率/% | 测量结果 | 正确概率/% |
---|---|---|---|
0010 | 0.2 | 1010 | 95.6 |
0110 | 2.8 | 1011 | 0.5 |
1000 | 0.1 | 1110 | 0.7 |
1001 | 0.1 |
1 | MONTANARO A. Quantum algorithms: an overview [J]. npj Quantum Information, 2016, 2: 15023. 10.1038/npjqi.2015.23 |
2 | SHOR P W. Algorithms for quantum computation: discrete logarithms and factoring [C]// Proceedings 35th Annual Symposium on Foundations of Computer Science. Piscataway: IEEE, 1994: 124-134. 10.1007/3-540-58691-1_68 |
3 | 王潮,姚皓南,王宝楠,等. 量子计算密码攻击进展[J]. 计算机学报, 2020, 43(9): 1691-1707. 10.11897/SP.J.1016.2020.01691 |
WANG C, YAO H N, WANG B N, et al. Progress in quantum computing cryptographic attacks [J]. Chinese Journal of Computers, 2020, 43(9): 1691-1707. 10.11897/SP.J.1016.2020.01691 | |
4 | 钱建发,张莉娜. 利用立方图的线图构造量子纠错码[J]. 计算机工程与应用, 2013, 49(6): 16-18. 10.3778/j.issn.1002-8331.1210-0304 |
QIAN J F, ZHANG L N. Construction of quantum codes from line graph of cube [J]. Computer Engineering and Applications, 2013, 49(6): 16-18. 10.3778/j.issn.1002-8331.1210-0304 | |
5 | NARAYANAN A. Quantum computing for beginners [C]// Proceedings of the 1999 Congress on Evolutionary Computation. Piscataway: IEEE, 1999, 3: 2231-2238. 10.1109/cec.1999.781900 |
6 | SELF C N, KHOSLA K E, SMITH A W R, et al. Variational quantum algorithm with information sharing [J]. npj Quantum Information, 2021, 7: 116. 10.1038/s41534-021-00452-9 |
7 | FARHI E, GOLDSTONE J, GUTMANN S. A quantum approximate optimization algorithm [EB/OL]. [2023-01-25]. . 10.22331/q-2022-07-07-759 |
8 | HERRMAN R, TREFFERT L, OSTROWSKI J, et al. Impact of graph structures for QAOA on MaxCut [J]. Quantum Information Processing, 2021, 20: 289. 10.1007/s11128-021-03232-8 |
9 | 王富民,倪明,周明,等. 量子绝热近似求解最大割问题的最优解[J]. 计算机工程, 2020, 46(1): 25-30. |
WANG F M, NI M, ZHOU M, et al. Optimal solution of max-cut problem using quantum adiabatic approximation [J]. Computer Engineering, 2020, 46(1): 25-30. | |
10 | 何键浩,李绿周. 量子优化算法综述[J]. 计算机研究与发展, 2021, 58(9): 1823-1834. 10.7544/issn1000-1239.2021.20210276 |
HE J H, LI L Z. An overview of quantum optimization [J]. Journal of Computer Research and Development, 2021, 58(9): 1823-1834. 10.7544/issn1000-1239.2021.20210276 | |
11 | BRAVYI S, KLIESCH A, KOENIG R, et al. Hybrid quantum-classical algorithms for approximate graph coloring [J]. Quantum, 2022, 6: 678. 10.22331/q-2022-03-30-678 |
12 | RUAN Y, MARSH S, XUE X, et al. The quantum approximate algorithm for solving traveling salesman problem [J]. Computers, Materials & Continua, 2020, 63(3): 1237-1247. 10.32604/cmc.2020.010001 |
13 | CHOI J, KIM J. A tutorial on quantum approximate optimization algorithm (QAOA): fundamentals and applications [C]// Proceedings of the 2019 International Conference on Information and Communication Technology Convergence. Piscataway: IEEE, 2019: 138-142. 10.1109/ictc46691.2019.8939749 |
14 | ZHANG Y J, MU X D, LIU X W, et al. Applying the quantum approximate optimization algorithm to the minimum vertex cover problem [J]. Applied Soft Computing, 2022, 118:108554. 10.1016/j.asoc.2022.108554 |
15 | VIKSTÅL P, GRÖNKVIST M, SVENSSON M, et al. Applying the quantum approximate optimization algorithm to the tail-assignment problem [J]. Physical Review Applied, 2020, 14: 034009. 10.1103/physrevapplied.14.034009 |
16 | GONG C, WANG T, HE W, et al. A quantum approximate optimization algorithm for solving Hamilton path problem [J]. The Journal of Supercomputing, 2022, 78: 15381-15403. 10.1007/s11227-022-04462-y |
17 | KORTEN T, DIEZ S, LINKE H, et al. Design of network-based biocomputation circuits for the exact cover problem [J]. New Journal of Physics, 2021, 23: 085004. 10.1088/1367-2630/ac175d |
18 | GRÖNKVIST M. The tail assignment problem [R]. Göteborg, Sweden: Chalmers University of Technology and Göteborg University, Department of Computer Science and Engineering, 2005: 4-6. |
19 | BA C. An exact cover-based approach for service composition[C]// Proceedings of the 2016 IEEE International Conference on Web Services. Piscataway: IEEE, 2016: 631-636. 10.1109/icws.2016.87 |
20 | BENGTSSON A, VIKSTÅL P, WARREN C, et al. Improved success probability with greater circuit depth for the quantum approximate optimization algorithm [J]. Physical Review Applied, 2020, 14: 034010. 10.1103/physrevapplied.14.034010 |
21 | LUCAS A. Ising formulations of many NP problems [J]. Frontiers in Physics, 2014, 2: 5. 10.3389/fphy.2014.00005 |
22 | FU Y, ANDERSON P W. Application of statistical mechanics to NP-complete problems in combinatorial optimisation [J]. Journal of Physics A: Mathematical and General, 1986, 19(9): 1605. 10.1088/0305-4470/19/9/033 |
23 | MÉZARD M, MONTANARI A. Information, Physics, and Computation [M]. Oxford: Oxford University Press, 2009: 35-36. 10.1093/acprof:oso/9780198570837.001.0001 |
24 | ZHOU L, WANG S-T, CHOI S, et al. Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices [J]. Physical Review X, 2020, 10: 021067. 10.1103/physrevx.10.021067 |
25 | MAGNIEZ F, NAYAK A, ROLAND J, et al. Search via quantum walk [C]// Proceedings of the 39th Annual ACM Symposium on Theory of Computing. New York: ACM, 2007: 575-584. 10.1145/1250790.1250874 |
26 | CHILDS A, GOLDSTONE J. Spatial search by quantum walk [J]. Physical Review A, 2004, 70: 022314. 10.1103/physreva.70.022314 |
27 | PAPAGEORGIOU A, PETRAS I. Estimating the ground state energy of the Schrödinger equation for convex potentials [J]. Journal of Complexity, 2014, 30(4): 469-494. 10.1016/j.jco.2014.03.002 |
28 | WILLE R, VAN METER R, NAVEH Y. IBM’s Qiskit tool chain: working with and developing for real quantum computers[C]// Proceedings of the 2019 Design, Automation & Test in Europe Conference & Exhibition. Piscataway: IEEE, 2019: 1234-1240. 10.23919/date.2019.8715261 |
29 | MICELI R, McGUIGAN M. Quantum computation and visualization of Hamiltonians using discrete quantum mechanics and IBM Qiskit [C]// Proceedings of the 2018 New York Scientific Data Summit. Piscataway: IEEE, 2018: 1-6. 10.1109/nysds.2018.8538959 |
30 | FRAZIER P I. A tutorial on Bayesian optimization [EB/OL]. [2022-11-14]. . |
31 | PAN Y, TONG Y, YANG Y. Automatic depth optimization for a quantum approximate optimization algorithm [J]. Physical Review A, 2022, 105(3): 032433. 10.1103/physreva.105.032433 |
32 | POWELL M J D. A direct search optimization method that models the objective and constraint functions by linear interpolation [M]// Advances in Optimization and Numerical Anslysis. Dordrecht: Springer, 1994: 51-67. 10.1007/978-94-015-8330-5_4 |
33 | KNUTH D E. Dancing links [EB/OL]. [2023-01-22]. . |
[1] | . Algorithm for Time Series Prediction based on Multi-Scale Gated Dilated Convolutional Networks [J]. Journal of Computer Applications, 0, (): 0-0. |
[2] | Yuemei XU, Ling HU, Jiayi ZHAO, Wanze DU, Wenqing WANG. Research progress and enlightenment of large language models on multi-lingual intelligence [J]. Journal of Computer Applications, 2023, 43(S2): 1-8. |
[3] | Mingyue WANG, Xiaohong ZOU, Jing CHEN, Chengwei XU. Overlapping community detection algorithm based on label propagation and multiple metrics [J]. Journal of Computer Applications, 2023, 43(S2): 105-110. |
[4] | Yunfei ZENG, Fudong GE. Disaster area prediction method for forest fire by fusing auto-reservoir neural network and long short-term memory network [J]. Journal of Computer Applications, 2023, 43(S2): 60-64. |
[5] | . Logo detection based on improved YOLOv5 [J]. Journal of Computer Applications, 0, (): 0-0. |
[6] | Lina GE, Jingya XU, Zhe WANG, Guifen ZHANG, Liang YAN, Zheng HU. Current research status and challenges of blockchain in supply chain applications [J]. Journal of Computer Applications, 2023, 43(11): 3315-3326. |
[7] | Pengxin TIAN, Guannan SI, Zhaoliang AN, Jianxin LI, Fengyu ZHOU. Survey of data-driven intelligent cloud-edge collaboration [J]. Journal of Computer Applications, 2023, 43(10): 3162-3169. |
[8] | Min ZUO, Hong WANG, Wenjing YAN, Qingchuan ZHANG. Gene splice site identification based on BERT and CNN [J]. Journal of Computer Applications, 2023, 43(10): 3309-3314. |
[9] | . Time series classification method based on multi-scale cross-attention fusion in time-frequency domain [J]. Journal of Computer Applications, 0, (): 0-0. |
[10] | . Review of YOLO algorithm and its application to object detection in autonomous driving scenes [J]. Journal of Computer Applications, 0, (): 0-0. |
[11] | Jingyi WANG, Chao LI, Heng SONG, Di LI, Junwu ZHU. Spectrum combinatorial auction mechanism based on random walk algorithm [J]. Journal of Computer Applications, 2023, 43(8): 2352-2357. |
[12] | Zelin XU, Min YANG, Meng CHEN. Point-of-interest category representation model with spatial and textual information [J]. Journal of Computer Applications, 2023, 43(8): 2456-2461. |
[13] | Zhihui GAO, Qi QIN, Jian DUAN, Xu SHEN, Xiaoyuan JI, Zhiyong LIU, Guanglan LIAO. Design and implementation of workshop monitoring system based on real-time Web technology [J]. Journal of Computer Applications, 2023, 43(S1): 201-206. |
[14] | Xiajiao ZHONG, Shaobing ZHANG, Jing GUO, Shengchao WANG, Miao CHENG, Lian HE, Yimin ZHAO. 3D point cloud tooth and jaw segmentation and identification based on RandLA-Net [J]. Journal of Computer Applications, 2023, 43(S1): 269-275. |
[15] | Xingshen WEI, Peng GAO, Zhuo LYU, Yongjian CAO, Jian ZHOU, Zhihao QU. Adaptive interaction feedback based trust evaluation mechanism for power terminals [J]. Journal of Computer Applications, 2023, 43(6): 1878-1883. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||