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

Quantum Approximate Optimization Algorithm for Graph Partitioning

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

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.