论文标题
用量子假想时间演变求解最大值
Solving MaxCut with Quantum Imaginary Time Evolution
论文作者
论文摘要
我们介绍了一种基于量子假想时间演化（QITE）有效地解决最大问题的方法。我们采用线性ansatz进行单一更新和无涉及纠缠的初始状态，以及在给定图和一个子图之间插值的虚构时间依赖性的汉密尔顿插值。我们将该方法应用于数千个随机选择的图形，最多五十个顶点。我们表明，对于所有考虑的图，我们的算法表现出93％及以上的性能融合到Maxcut问题的最大解决方案。我们的结果与经典算法的性能相比，例如贪婪和戈曼斯 - 威廉姆森算法。我们还讨论了QITE算法的最终状态与基态作为性能度量的重叠，这是其他经典算法未共享的量子特征。可以通过引入高阶Ansaetze和纠缠初始状态来改进该度量。
We introduce a method to solve the MaxCut problem efficiently based on quantum imaginary time evolution (QITE). We employ a linear Ansatz for unitary updates and an initial state involving no entanglement, as well as an imaginary-time-dependent Hamiltonian interpolating between a given graph and a subgraph with two edges excised. We apply the method to thousands of randomly selected graphs with up to fifty vertices. We show that our algorithm exhibits a 93% and above performance converging to the maximum solution of the MaxCut problem for all considered graphs. Our results compare favorably with the performance of classical algorithms, such as the greedy and Goemans-Williamson algorithms. We also discuss the overlap of the final state of the QITE algorithm with the ground state as a performance metric, which is a quantum feature not shared by other classical algorithms. This metric can be improved by introducing higher-order Ansaetze and entangled initial states.
