Impact of graph structures for QAOA on MaxCut
Impact of graph structures for QAOA on MaxCut
复制标题
DOI：
10.1007/s11128-021-03232-8
复制
发表时间：
2021-09-01
影响因子：
2.5
通讯作者：
Siopsis, George
中科院分区：
文献类型：
--
作者：
Herrman, Rebekah;Treffert, Lorna;Siopsis, George
量子近似优化算法（QAOA）是利用量子计算求解组合优化问题的一种很有前途的方法。最大割问题的QAOA算法在具有特定结构的图上得到了广泛的研究，然而，关于该算法在任意图上的一般性能却知之甚少。在本文中，我们研究了不同的图形特性与QAOA性能在深度最多三个最大割问题的所有连接的非同构图最多八个顶点。QAOA成功的一些好的预测因素与图的对称性、奇循环和密度有关。例如，在八顶点图上，在QAOA的三次迭代之后，为不包含奇数圈的图选择最优解的平均概率为60.6%，而为包含奇数圈的图选择最优解的平均概率为48.2%。这些研究产生的数据在一个可公开访问的数据库中共享，作为QAOA计算和实验的基准。了解结构和性能之间的关系可以用来识别可能表现出量子优势的组合问题的类别。
The quantum approximate optimization algorithm (QAOA) is a promising method of solving combinatorial optimization problems using quantum computing. QAOA on the MaxCut problem has been studied extensively on graphs with specific structure; however, little is known about the general performance of the algorithm on arbitrary graphs. In this paper, we investigate how different graph characteristics correlate with QAOA performance at depths at most three on the MaxCut problem for all connected non-isomorphic graphs with at most eight vertices. Some good predictors of QAOA success relate to graph symmetries, odd cycles, and density. For example, on eight vertex graphs, the average probability for selecting an optimal solution for graphs that contain no odd cycles after three iterations of QAOA is 60.6% compared to 48.2% for those that do. The data generated from these studies are shared in a publicly accessible database to serve as a benchmark for QAOA calculations and experiments. Knowing the relationship between structure and performance can be used to identify classes of combinatorial problems that are likely to exhibit a quantum advantage.