论文标题
递归QAOA优于最大切割问题的原始QAOA
Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs
论文作者
论文摘要
量子近似优化算法是杂种量子古典变异算法，旨在近似求解组合优化问题，例如最大切割问题。尽管它具有近期量子应用的潜力，但众所周知，量子近似优化算法对某些实例解决最大切割问题的局限性，以任何恒定的水平$ p $。最近，已经提出了递归量子近似优化算法，该算法是量子近似优化算法的非本地版本，以克服这些局限性。但是，大多数是数值证据表明，递归量子近似优化算法优于特定实例的原始量子近似优化算法。在本文中，我们在分析上证明，递归量子近似优化算法比原始算法更具竞争力，该算法可以解决最大切割问题以相对于近似比的完整图。
Quantum approximate optimization algorithms are hybrid quantum-classical variational algorithms designed to approximately solve combinatorial optimization problems such as the MAX-CUT problem. In spite of its potential for near-term quantum applications, it has been known that quantum approximate optimization algorithms have limitations for certain instances to solve the MAX-CUT problem, at any constant level $p$. Recently, the recursive quantum approximate optimization algorithm, which is a non-local version of quantum approximate optimization algorithm, has been proposed to overcome these limitations. However, it has been shown by mostly numerical evidences that the recursive quantum approximate optimization algorithm outperforms the original quantum approximate optimization algorithm for specific instances. In this paper, we analytically prove that the recursive quantum approximate optimization algorithm is more competitive than the original one to solve the MAX-CUT problem for complete graphs with respect to the approximation ratio.
