论文标题
量子深度的下限量子近似优化算法
Lower Bounds on Circuit Depth of the Quantum Approximate Optimization Algorithm
论文作者
论文摘要
量子近似优化算法（QAOA）是一种近似解决组合优化问题的方法。虽然开发了QAOA来解决一系列组合优化问题，但尚不清楚哪种问题最适合于此。证明量子优势的一个因素是问题实例与实现QAOA方法所需的电路深度之间的关系。随着NISQ设备中的误差随电路深度的指数增加，识别电路深度上的下限可以提供有关何时可行的量子优势的见解。在这里，我们确定问题实例的结构如何用于确定QAOA的每次迭代的电路深度的下限，并检查问题结构与电路深度之间的关系，以包括各种组合优化问题，包括MaxCut和MaxindSet。具体来说，我们展示了如何得出一个描述一般组合优化问题的图形$ g $，并表明电路的深度至少是$ g $的色度索引。通过查看电路深度的缩放，我们认为MaxCut，Maxindset以及一些顶点覆盖和布尔值的满足性问题适合于QAOA方法，而Knapsack和Knapsack和旅行销售人员的问题不是。
The quantum approximate optimization algorithm (QAOA) is a method of approximately solving combinatorial optimization problems. While QAOA is developed to solve a broad class of combinatorial optimization problems, it is not clear which classes of problems are best suited for it. One factor in demonstrating quantum advantage is the relationship between a problem instance and the circuit depth required to implement the QAOA method. As errors in NISQ devices increases exponentially with circuit depth, identifying lower bounds on circuit depth can provide insights into when quantum advantage could be feasible. Here, we identify how the structure of problem instances can be used to identify lower bounds for circuit depth for each iteration of QAOA and examine the relationship between problem structure and the circuit depth for a variety of combinatorial optimization problems including MaxCut and MaxIndSet. Specifically, we show how to derive a graph, $G$, that describes a general combinatorial optimization problem and show that the depth of circuit is at least the chromatic index of $G$. By looking at the scaling of circuit depth, we argue that MaxCut, MaxIndSet, and some instances of Vertex Covering and Boolean satisifiability problems are suitable for QAOA approaches while Knapsack and Traveling Sales Person problems are not.
