论文标题
通过选择后改善量子近似优化算法
Improving the Quantum Approximate Optimization Algorithm with postselection
论文作者
论文摘要
组合优化是近期和耐断层量子计算机所设想的主要应用之一。在这项工作中，我们考虑了一种良好的量子算法进行组合优化：量子近似优化算法（QAOA）应用于3型图表上的maxcut问题。我们探讨了使用最简单版本的算法（depth-1 QAOA）返回的解决方案的想法，该形式可以通过状态准备有效地模拟。我们得出理论上和下限，表明满足边缘的比例的常数（尽管很小）确实可以实现。大型问题实例（超出经典的模拟能力）的数值实验补充并支持我们的界限。我们还考虑了一种独特的技术：本地更新，不仅可以应用于QAOA，还可以应用于任何优化算法。在QAOA的情况下，理论上可以在理论上对所产生的改进进行大量量化，以实现大量问题实例，并且在没有后选择后。结合了选择后和本地更新，该理论不再可进行处理，而是数字证据表明，可以将两种方法的改进都结合在一起。
Combinatorial optimization is among the main applications envisioned for near-term and fault-tolerant quantum computers. In this work, we consider a well-studied quantum algorithm for combinatorial optimization: the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on 3-regular graphs. We explore the idea of improving the solutions returned by the simplest version of the algorithm (depth-1 QAOA) using a form of postselection that can be efficiently simulated by state preparation. We derive theoretical upper and lower bounds showing that a constant (though small) increase of the fraction of satisfied edges is indeed achievable. Numerical experiments on large problem instances (beyond classical simulatability) complement and support our bounds. We also consider a distinct technique: local updates, which can be applied not only to QAOA but any optimization algorithm. In the case of QAOA, the resulting improvement can be sharply quantified theoretically for large problem instances and in absence of postselection. Combining postselection and local updates, the theory is no longer tractable but numerical evidence suggests that improvements from both methods can be combined.
