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

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

扫码查看
原文链接
  • 万方数据
  • 维普
量子近似优化算法(Quantum Approximate Optimization Algorithm,QAOA)是求解组合优化问题的算法框架,是近期最有可能展示量子计算优势的算法之一.在QAOA框架内,表征解的量子态采取的二进制编码方案导致的对称性限制了QAOA的性能.为了克服这一局限性,本文受Dicke态制备算法的启发,给出了一种新的解编码方案,消除了现有编码方案中的对称性.本文还设计了新的演化算子——星图(Star Graph,SG)算子,及其对应的SG算法,给出了算法求解图分割问题时的量子电路.在IBM Q上的实验结果显示,星图算法比标准QAO算法平均约有25.3％的性能提升.
Quantum Approximate Optimization Algorithm for Graph Partitioning
Quantum approximate optimization algorithm (QAOA) is an algorithm framework for solving combinatori-al optimization problems. It is regarded as one of the promising candidates to demonstrate the advantages of quantum com-puting 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 evolu-tion operator,star graph (SG) mixer,and its corresponding SG algorithm. The quantum circuit implementation of the SG al-gorithm 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.

quantum approximate optimization algorithmcombinatorial optimizationstar graph mixerstar graph algorithmgraph partitioning

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

展开 >

安徽工业大学计算机科学与技术学院,安徽马鞍山 243032

量子近似优化算法 组合优化问题 星图算子 星图算法 图分割

国家自然科学基金安徽省自然科学基金安徽省自然科学基金安徽省高校自然科学重点项目安徽省高校自然科学重点项目安徽省重点研究与开发计划项目

618020021708085MF1621908085MF212KJ2020A02332022AH050319201904d07020020

2024

10.12263/DZXB.20220784

电子学报
中国电子学会

电子学报

CSTPCD北大核心
影响因子：1.237
ISSN：0372-2112
年,卷(期)：2024.52(6)