一种求解图分割问题的量子近似优化算法

袁志强; 杨思春; 阮越; 薛希玲; 陶陶

doi:10.12263/DZXB.20220784

您当前的位置：

首页 >

文章列表页 >

一种求解图分割问题的量子近似优化算法

学术论文 | 更新时间：2025-12-11

- 一种求解图分割问题的量子近似优化算法
- Quantum Approximate Optimization Algorithm for Graph Partitioning
- 电子学报 2024年52卷第6期页码：2025-2036
- 作者机构：
  
  安徽工业大学计算机科学与技术学院，安徽马鞍山 243032
- 作者简介：
  
  [ "袁志强男，1994年生，安徽阜阳人.现为安徽工业大学计算机科学与技术学院硕士研究生.主要研究方向为量子算法. Email: yuanzhiq1994@163.com" ]
  杨思春男，1970年生，安徽六安人.现为安徽工业大学计算机科学与技术学院教授.主要研究方向为三支概念分析、粒计算、粗糙集和自然语言处理.
  阮越男，1972年生，安徽马鞍山人.现为安徽工业大学计算机科学与技术学院讲师.主要研究方向为量子算法和量子图像处理.
  薛希玲女，1985年生，山东临沂人.现为安徽工业大学计算机科学与技术学院讲师.主要研究方向为量子计算和量子行走.
  [ "陶陶男，1977年生，安徽无为人.现为安徽工业大学计算机科学与技术学院副教授.主要研究方向为深度学习和量子算法. Email: taotao@ahut.edu.cn" ]
- 基金信息：
  
  国家自然科学基金(61802002);安徽省自然科学基金(1708085MF162;1908085MF212);安徽省高校自然科学重点项目(KJ2020A0233;2022AH050319);安徽省重点研究与开发计划项目(201904d07020020)
- DOI：10.12263/DZXB.20220784
  中图分类号： TP301.6;
- 收稿：2022-07-06，
  
  修回：2023-02-16，
  
  纸质出版：2024-06-25
- 稿件说明：
移动端阅览
袁志强, 杨思春, 阮越, 等. 一种求解图分割问题的量子近似优化算法[J]. 电子学报, 2024, 52(06): 2025-2036.

YUAN Zhi-qiang, YANG Si-chun, RUAN Yue, et al. Quantum Approximate Optimization Algorithm for Graph Partitioning[J]. Acta Electronica Sinica, 2024, 52(06): 2025-2036.
袁志强, 杨思春, 阮越, 等. 一种求解图分割问题的量子近似优化算法[J]. 电子学报, 2024, 52(06): 2025-2036. DOI：10.12263/DZXB.20220784

YUAN Zhi-qiang, YANG Si-chun, RUAN Yue, et al. Quantum Approximate Optimization Algorithm for Graph Partitioning[J]. Acta Electronica Sinica, 2024, 52(06): 2025-2036. DOI：10.12263/DZXB.20220784

摘要

量子近似优化算法（Quantum Approximate Optimization Algorithm，QAOA）是求解组合优化问题的算法框架，是近期最有可能展示量子计算优势的算法之一.在QAOA框架内，表征解的量子态采取的二进制编码方案导致的对称性限制了QAOA的性能.为了克服这一局限性，本文受Dicke态制备算法的启发，给出了一种新的解编码方案，消除了现有编码方案中的对称性.本文还设计了新的演化算子——星图（Star Graph，SG）算子，及其对应的SG算法，给出了算法求解图分割问题时的量子电路.在IBM Q上的实验结果显示，星图算法比标准QAO算法平均约有25.3%的性能提升.

Abstract

Quantum approximate optimization algorithm (QAOA) is an algorithm framework for solving combinatorial optimization problems. It is regarded as one of the promising candidates to demonstrate the advantages of quantum computing in the near future. Within the QAOA framework

the symmetries of quantum states induced by the binary encoding scheme restrain the performance of QAOA. Inspired by the Dicke state preparation algorithm

we proposed a new encoding scheme that eliminated the symmetry of quantum states representing solutions. Beyond that

we also proposed a novel evolution operator

star graph (SG) mixer

and its corresponding SG algorithm. The quantum circuit implementation of the SG algorithm on IBM Q showed the SG algorithm has an average performance improvement of about 25.3% over the standard QAOA algorithm in solving the graph partitioning problem.

关键词

Keywords

references

FARHI E , GOLDSTONE J , GUTMANN S . A quantum approximate optimization algorithm [EB/OL ] . ( 2014 )[2022 ] . https://arxiv.org/abs/1411.4028 https://arxiv.org/abs/1411.4028 .

FARHI E , GOLDSTONE J , GUTMANN S . A quantum approximate optimization algorithm applied to a bounded occurrence constraint pro-blem [EB/OL ] . ( 2014 )[2022 ] . https://arxiv.org/abs/1412.6062 https://arxiv.org/abs/1412.6062 .

FARHI E , HARROW A . Quantum supremacy through the quantum approximate optimization algorithm [EB/OL ] . ( 2016 )[2022 ] . https://arxiv.org/abs/1602.07674 https://arxiv.org/abs/1602.07674 .

YANG Z , RAHMANI A , SHABANI A , et al . Optimizing variational quantum algorithms using Pontryagin’s minimum principle [J ] . Physical Review X , 2017 , 7 ( 2 ): 021027 .

JIANG Z , RIEFFEL E , WANG Z . Near optimal quantum circuit for Grover’s unstructured search using a transverse field [J ] . Physical Review A , 2017 , 95 ( 6 ): 062317 .

WECKER D , HASTINGS M , TROYER M . Training a quantum optimizer [J ] . Physical Review A , 2016 , 94 ( 2 ): 022309 .

WANG Z , HADFIELD S , RIEFFEL E , et al . Quantum approximate optimization algorithm for Maxcut: A fermionic view [J ] . Physical Review A , 2018 , 97 ( 2 ): 022304 .

VENTURELLI D , DO M , RIEFFEL , et al . Compiling quantum circuits to realistic hardware architectures using temporal planners [J ] . Quantum Science and Technology , 2018 , 3 ( 2 ): 025004 .

PRESKILL J . Quantum computing in the NISQ era and beyond [J ] . ( 2018 )[2022 ] . https://arxiv.org/abs/1801.00862 https://arxiv.org/abs/1801.00862 .

FARHI E , GOLDSTONE J , GUTMANN S , et al . A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem [J ] . Science , 2001 , 292 ( 5516 ): 472 - 475 .

HALL B . Lie Groups, Lie Algebras, and Representations: An Elementary Introduction [M ] . 1st ed . New York : Springer , 2003 : 35 - 37 .

RUAN Y , YUAN Z , XUE X , et al . Quantum approximate optimization for combinatorial problems with constraints‍ [J ] . Information Sciences , 2023 , 619 : 98 - 125 .

LUCAS A . Ising formulations of many NP pro-blems [J ] . Frontiers in Physics , 2014 , 2 ( 5 ): 1 - 15 .

FARHI E , GAMARNIK D , GUTMANN S . The quantum approximate optimization algorithm needs to see the whole graph: A typical case [EB/OL ] . ( 2020 )[2022 ] . https://arxiv.org/abs/2004.09002 https://arxiv.org/abs/2004.09002 .

FARHI E , GAMARNIK D , GUTMANN S . The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples [EB/OL ] . ( 2020 )[2022 ] . https://arxiv.org/abs/2005.08747 https://arxiv.org/abs/2005.08747 .

BRAVYI S , KLIESCH A , KOENIG R , et al . Obstacles to variational quantum optimization from symmetry protection [J ] . Physical Review Letters , 2020 , 125 ( 26 ): 260505 .

EGGER D , MARECEK J , WOERNER S . Warm-starting quantum optimization [EB/OL ] . ( 2021 )[2022 ] . https://arxiv.org/abs/2009.10095 https://arxiv.org/abs/2009.10095 .

CHAI Y , HAN Y , WU Y , et al . Shortcuts to quantum approximate optimization algorithm [J ] . ( 2021 )[2022 ] . https://arxiv.org/abs/2112.10943 https://arxiv.org/abs/2112.10943 .

HADFIELD S . Quantum algorithms for scientific computing and approximate optimization [EB/OL ] . ( 2018 )[2022 ] . https://arxiv.org/abs/1805.03265 https://arxiv.org/abs/1805.03265 .

HADFIELD S , WANG Z , O’GORMAN B , et al . From the quantum approximate optimization algorithm to a quantum alternating operator ansatz [J ] . Algorithms , 2019 , 12 ( 2 ): 34 .

HADFIELD S , WANG Z , O’GORMAN B , et al . Quantum approximate optimization with hard and soft constraints [C ] // The Second International Workshop on Post-Moore’s Era Supercomputing . New York : Association for Computing Machinery , 2017 : 15 - 21 .

MARSH S , WANG Z . A quantum walk-assisted approximate algorithm for bounded NP optimisation problems [J ] . Quantum Information Processing , 2019 , 18 ( 3 ): 61 .

SALEEM Z , TARIQ B , SUCHARA M . Approaches to constrained quantum approximate optimization [EB/OL ] . ( 2020 )[2022 ] . https://arxiv.org/abs/2010.06660 https://arxiv.org/abs/2010.06660 .

BRAVYI S , HASTINGS M , VERSTRAETE F . Liebrobinson bounds and the generation of correlations and topological quantum order [J ] . Physical Review Letters , 2006 , 97 ( 5 ): 050401 .

GU Z , WEN X . Tensor-entanglement-fltering renormalization approach and symmetry protected topological order [J ] . Physical Review B , 2009 , 80 ( 15 ): 155131 .

SCHUCH N , PEREZ-GARCIA D , CIRAC I . Classifying quantum phases using matrix product states and projected entangled pair states [J ] . Physical Review B , 2011 , 84 ( 16 ): 165139 .

POLLMANN F , BERG E , TURNER A , et al . Entanglement spectrum of a topological phase in one dimension‍ [J ] . Physical Review B , 2009 , 81 ( 6 ): 064439 .

BARTSCHI A , EIDENBENZ S . Deterministic preparation of dicke states [EB/OL ] . ( 2019 )[2022 ] . https://arxiv.‍org/abs/1904.07358 https://arxiv.‍org/abs/1904.07358 .

JOHNSON D , ARAGON C , MCGEOCH L , et al . Optimization by simulated annealing: An experimental evaluation [J ] . Operations Research , 1989 , 37 ( 6 ): 865 - 892 .

BICHOT C , SIARRY P . General Introduction to Graph Partitioning [M ] . New York : John Wiley & Sons, Inc , 2013 : 1 - 25 .

KARP R , MILLER R , THATCHER J . Reducibility among combinatorial problems [J ] . Journal of Symbolic Logic , 2010 , 40 ( 4 ): 618 - 619 .

GAREY M , JOHNSON D , STOCKMEYER L . Some simplified NP-complete graph problems [J ] . Theoretical Computer Science , 1976 , 1 ( 3 ): 237 - 267 .

DICKE R . Coherence in spontaneous radiation processes‍ [J ] . Physical Review , 1954 , 93 ( 1 ): 99 - 110 .

COOK J , EIDENBENZ S , BARTSCHI A . The quantum alternating operator ansatz on maximum k-vertex cover‍ [C ] // 2020 IEEE International Conference on Quantum Computing and Engineer-ing(QCE) . Denver : IEEE , 2020 : 83 - 92 .

WANG Z , RUBIN N , DOMINY J , et al . Xy-mixers: Analytical and numerical results for QAOA [J ] . Physical Review A , 2019 , 101 ( 1 ): 012320 .

LAROSE R . Overview and comparison of gate level quantum software platforms [J ] . Quantum , 2019 , 3 : 130 .

SIRAICHI M , SANTOS V , COLLANGE S , et al . Qubit allocation [C ] // Proceedings of the 2018 International Symposium on Code Generation and Optimization . New York : IEEE , 2018 : 113 - 125 .

BHARTI K , CERVERA-LIERTA A , KYAW T , et al . Noisy intermediate-scale quantum algorithms [J ] . Reviews of Modern Physics , 2022 , 94 ( 1 ): 015004 .

MURALI P , MCKAY D , MARTONOSI M , et al . Software mitigation of crosstalk on noisy inter-mediate-scale quantum computers [C ] // Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems . New York : ACM , 2020 : 1001 - 1016 .

TEMME K , BRAVYI S , GAMBETTA J . Error mitigation for short-depth quantum circuits [J ] . Physical review letters , 2017 , 119 ( 18 ): 180509 .

ENDO S , BENJAMIN S , LI Y . Practical quantum error mitigation for near-future applications [J ] . Physical Review X , 2018 , 8 ( 3 ): 031027 .

KWON H , BAE J . A hybrid quantum-classical approach to mitigating measurement errors in quantum algorithms‍ [J ] . IEEE Transactions on Computers , 2020 , 70 ( 9 ): 1401 - 1411 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于加权优先级与数据包到达时间的MP-QUIC调度算法

面向类别不平衡ECG的快速患者间域适应心律失常识别方法

基于大模型的RAG算法的快速评估系统：RGE-Pipeline

一种信号外推和层级学习SAR超分辨率方法

基于TCAD与DNN的FinFET器件辐射总剂量效应模型