Lower bounds on circuit depth of the quantum approximate optimization algorithm
Lower bounds on circuit depth of the quantum approximate optimization algorithm
复制标题
DOI：
10.1007/s11128-021-03001-7
复制
发表时间：
2021-02-09
影响因子：
2.5
通讯作者：
Siopsis, George
中科院分区：
文献类型：
--
作者：
Herrman, Rebekah;Ostrowski, James;Siopsis, George
量子近似优化算法（QAOA）是一种近似求解组合优化问题的方法。虽然QAOA被开发来解决广泛的一类组合优化问题，但目前还不清楚哪类问题最适合它。证明量子优势的一个因素是问题实例与实现QAOA方法所需的电路深度之间的关系。由于有噪声的中间尺度量子（NISQ）器件中的误差随着电路深度呈指数级增加，因此确定电路深度的下限可以提供量子优势何时可行的见解。在这里，我们确定如何的问题实例的结构可以用来确定电路深度的下限QAOA的每次迭代，并检查问题结构和电路深度之间的关系，包括MaxCut和MaxIndSet的各种组合优化问题。具体地说，我们展示了如何导出一个图，G，它描述了一个一般的组合优化问题，并表明，电路的深度至少是G的色指数。通过查看电路深度的缩放，我们认为，MaxCut，MaxIndSet，顶点覆盖和布尔可满足性问题的一些实例是适合QAOA的方法，而背包和旅行推销员的问题不。
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 noisy intermediate-scale quantum (NISQ) devices increase 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 satisfiability problems are suitable for QAOA approaches while knapsack and traveling salesperson problems are not.