Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems
Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems
复制标题
DOI：
10.3390/a14100294
复制
发表时间：
2021-10-01
期刊：
影响因子：
2.3
通讯作者：
Siopsis, George
中科院分区：
文献类型：
--
作者：
Herrman, Rebekah;Treffert, Lorna;Siopsis, George
本文提出了一种全局变量替换方法，将组合优化问题中的n变量单项式简化为具有较少变量单项式的等价实例。我们将该技术应用于3-SAT，并分析了使用量子近似优化算法解决约简问题所需的最佳量子幺正电路深度。对于基准的3-SAT问题，我们发现将问题表述为乘积并使用代换法分解门时，幺正电路深度的上界要小于不需要分解的线性表述。
We develop a global variable substitution method that reduces n-variable monomials in combinatorial optimization problems to equivalent instances with monomials in fewer variables. We apply this technique to 3-SAT and analyze the optimal quantum unitary circuit depth needed to solve the reduced problem using the quantum approximate optimization algorithm. For benchmark 3-SAT problems, we find that the upper bound of the unitary circuit depth is smaller when the problem is formulated as a product and uses the substitution method to decompose gates than when the problem is written in the linear formulation, which requires no decomposition.