论文标题
击败近似量子2局部哈密顿问题的随机分配
Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems
论文作者
论文摘要
量子k-local Hamiltonian问题是经典约束满意度问题的自然概括（K-CSP），对于QMA，NP的量子类似物是完整的。尽管已经对K-Local Hamilton问题的复杂性进行了充分的研究，但仅知道一些近似结果。对于每个项为等级3投影仪的最大2-局部哈密顿量，经典2-SAT的自然量子概括，最著名的近似算法是微不足道的随机分配，得出0.75 approximation。我们介绍了第一个近似算法，即击败这种结合，这是一种经典的多项式时间0.764-附近。对于严格的二次实例（最大纠缠的实例），我们提供了0.801近似算法，并且数值证明我们的算法可能是0.821-Approximation。我们猜想这些是最难近似的实例。我们还提供了改进的其他相关经典2-CSP的量子概括的近似值。最后，我们利用量子连接到Grothendieck问题的概括，以获取经典的恒定因子近似值，用于在双方相互作用图上严格相关的严格二次无纹状体2-局部汉密尔顿人的特殊情况，其中最佳的对数近似是最佳的（对于一般的相互作用图）。我们的工作采用了最近开发的技术来分析CSP的经典近似值，量子科学家和经典计算机科学家都可以访问。
The quantum k-Local Hamiltonian problem is a natural generalization of classical constraint satisfaction problems (k-CSP) and is complete for QMA, a quantum analog of NP. Although the complexity of k-Local Hamiltonian problems has been well studied, only a handful of approximation results are known. For Max 2-Local Hamiltonian where each term is a rank 3 projector, a natural quantum generalization of classical Max 2-SAT, the best known approximation algorithm was the trivial random assignment, yielding a 0.75-approximation. We present the first approximation algorithm beating this bound, a classical polynomial-time 0.764-approximation. For strictly quadratic instances, which are maximally entangled instances, we provide a 0.801 approximation algorithm, and numerically demonstrate that our algorithm is likely a 0.821-approximation. We conjecture these are the hardest instances to approximate. We also give improved approximations for quantum generalizations of other related classical 2-CSPs. Finally, we exploit quantum connections to a generalization of the Grothendieck problem to obtain a classical constant-factor approximation for the physically relevant special case of strictly quadratic traceless 2-Local Hamiltonians on bipartite interaction graphs, where a inverse logarithmic approximation was the best previously known (for general interaction graphs). Our work employs recently developed techniques for analyzing classical approximations of CSPs and is intended to be accessible to both quantum information scientists and classical computer scientists.
