论文标题
提高量子最大切割的近似算法
An Improved Approximation Algorithm for Quantum Max-Cut
论文作者
论文摘要
我们给出了量子最大切割的近似算法，该算法是通过将SDP松弛到纠缠量子状态将其舍入的。 SDP用于选择变异量子电路的参数。然后将纠缠状态表示为应用于产品状态的量子电路。它在无三角形图上达到了0.582的近似值。 Thompson先前的最佳算法，Gosset，Morenz和Parekh，近似值分别达到0.531和0.533。此外，我们研究了EPR Hamiltonian，我们认为这是一个自然的中间问题，它隔离了当地汉密尔顿问题的一些关键量子特征。对于EPR Hamiltonian，我们在所有图上提供了近似值$ 1 / \ sqrt {2} $的近似算法。
We give an approximation algorithm for Quantum Max-Cut which works by rounding an SDP relaxation to an entangled quantum state. The SDP is used to choose the parameters of a variational quantum circuit. The entangled state is then represented as the quantum circuit applied to a product state. It achieves an approximation ratio of 0.582 on triangle-free graphs. The previous best algorithms of Anshu, Gosset, Morenz, and Parekh, Thompson achieved approximation ratios of 0.531 and 0.533 respectively. In addition, we study the EPR Hamiltonian, which we argue is a natural intermediate problem which isolates some key quantum features of local Hamiltonian problems. For the EPR Hamiltonian, we give an approximation algorithm with approximation ratio $1 / \sqrt{2}$ on all graphs.
