Quantum Approximate Optimization Algorithm for Graph Partitioning

YUAN Zhi-qiang; YANG Si-chun; RUAN Yue; XUE Xi-ling; TAO Tao

doi:10.12263/DZXB.20220784

您当前的位置：

首页 >

文章列表页 >

Quantum Approximate Optimization Algorithm for Graph Partitioning

PAPERS | 更新时间：2025-12-11

- Quantum Approximate Optimization Algorithm for Graph Partitioning
- ACTA ELECTRONICA SINICA Vol. 52, Issue 6, Pages: 2025-2036(2024)
- 作者机构：
  
  安徽工业大学计算机科学与技术学院，安徽马鞍山 243032
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61802002);Natural Science Foundation of Anhui Province(1708085MF162;1908085MF212);Anhui Provincial Key Research and Development Project(KJ2020A0233;2022AH050319);Key Research and Development Project of Anhui Province(201904d07020020)
- DOI：10.12263/DZXB.20220784
  CLC： TP301.6;
- Received：06 July 2022，
  
  Revised：2023-02-16，
  
  Published：25 June 2024
- 稿件说明：
移动端阅览
袁志强, 杨思春, 阮越, 等. 一种求解图分割问题的量子近似优化算法[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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Heterogeneous Graph-Based Identification of Critical Relays in Tor Networks

Recent Advances in Modulation Mechanisms of Polarity and Chirality of Magnetic Vortices and Magnetization Dynamic Properties

A Foundation Model for Traffic Classification Based on Mixture-of-Experts

A Full-Scene Detection Algorithm for Underground Parking Spaces Fusing Vision and Geometric Reasoning

Fuzz Testing of the Linux Kernel Integrating Dependency Inference and Weight Optimization

Related Author

YUAN Zhi-qiang

YANG Si-chun

RUAN Yue

XUE Xi-ling

TAO Tao

Related Institution

School of Computer Science and Technology， Anhui University of Technology， Maanshan

⁰