Product-state approximations to quantum ground states
Product-state approximations to quantum ground states
复制标题
DOI：
10.1145/2488608.2488719
复制
发表时间：
2013-06
期刊：
影响因子：
--
通讯作者：
F. Brandão;A. Harrow
中科院分区：
文献类型：
--
作者：
F. Brandão;A. Harrow
局域哈密顿问题包括估计局域量子哈密顿量的基态能量(由最小本征值给出)。它可以被认为是约束满足问题的量子推广，是量子复杂性理论中的关键问题，是已知的第一个也是最自然的QMA-完全问题。局域哈密顿问题的一个有趣的机制是广泛的误差，其中一个人感兴趣的是以恒定精度估计平均基态能量。根据PCP定理，这个问题是NP难的，但它是否QMA难是量子复杂性理论中一个重要的开放问题。正解将代表PCP定理的量子类比。量子哈密顿不同于经典CSP的一个关键特征是，解可能涉及复杂的纠缠态。在这篇文章中，我们证明了几大类哈密顿量，其乘积(即非纠缠)态可以将基态能量近似到一个小的广泛误差内。首先，我们证明了具有以下性质之一的2-局域哈密顿量的基态能量的良好乘积态近似的存在：(1)超常数次，(2)小展开，或(3)关于某些小分割的次线性纠缠的基态。基于次数的近似是量子哈密顿和经典CSP之间的一个新的令人惊讶的区别，因为在经典设置下，更高的阶通常与更难的CSP相关联。基于展开的近似并不新鲜，但基于低纠缠的近似以前只在纠缠接近于零的区域才为人所知。由于低能积态的存在可以在NP中检验，这意味着任何用于量子PCP定理的哈密顿量都应该具有：(1)恒定度，(2)恒定展开，(3)关于任何分割成小部分的纠缠的“体积定律”。其次，我们证明了在某些情况下，良好的乘积状态逼近不仅存在，而且可以在确定的多项式时间内找到：(1)任意平面图上的2-局部哈密顿算子，解决了Bansal，Bravyi和Terhal的一个公开问题；(2)对任意常数k的稠密k-局部哈密顿算子，解决了Gharibian和Kempe的公开问题；(3)通过对Barak，Raghavenra和Steurer最近的一个结果的量子推广，在具有低门限秩图上的2-局部哈密顿算子.我们的工作涉及两个可能独立感兴趣的新工具。首先，我们证明了一个新的量子版的de Finetti定理，它不需要通常的对称性假设。其次，我们描述了一种分析Lasserre/Parrilo SDP层次在局域量子哈密顿量中的应用的方法。
The local Hamiltonian problem consists of estimating the ground-state energy (given by the minimum eigenvalue) of a local quantum Hamiltonian. It can be considered as a quantum generalization of constraint satisfaction problems (CSPs) and has a key role in quantum complexity theory, being the first and most natural QMA-complete problem known. An interesting regime for the local Hamiltonian problem is that of extensive error, where one is interested in estimating the mean ground-state energy to constant accuracy. The problem is NP-hard by the PCP theorem, but whether it is QMA-hard is an important open question in quantum complexity theory. A positive solution would represent a quantum analogue of the PCP theorem. A key feature that distinguishes quantum Hamiltonians from classical CSPs is that the solutions may involve complicated entangled states. In this paper, we demonstrate several large classes of Hamiltonians for which product (i.e. unentangled) states can approximate the ground state energy to within a small extensive error. First, we show the mere existence of a good product-state approximation for the ground-state energy of 2-local Hamiltonians with one of more of the following properties: (1) super-constant degree, (2) small expansion, or (3) a ground state with sublinear entanglement with respect to some partition into small pieces. The approximation based on degree is a new and surprising difference between quantum Hamiltonians and classical CSPs, since in the classical setting, higher degree is usually associated with harder CSPs. The approximation based on expansion is not new, but the approximation based on low entanglement was previously known only in the regime where the entanglement was close to zero. Since the existence of a low-energy product state can be checked in NP, this implies that any Hamiltonian used for a quantum PCP theorem should have: (1) constant degree, (2) constant expansion, (3) a ``volume law'' for entanglement with respect to any partition into small parts. Second, we show that in several cases, good product-state approximations not only exist, but can be found in deterministic polynomial time: (1) 2-local Hamiltonians on any planar graph, solving an open problem of Bansal, Bravyi, and Terhal, (2) dense k-local Hamiltonians for any constant k, solving an open problem of Gharibian and Kempe, and (3) 2-local Hamiltonians on graphs with low threshold rank, via a quantum generalization of a recent result of Barak, Raghavendra and Steurer. Our work involves two new tools which may be of independent interest. First, we prove a new quantum version of the de Finetti theorem which does not require the usual assumption of symmetry. Second, we describe a way to analyze the application of the Lasserre/Parrilo SDP hierarchy to local quantum Hamiltonians.