Computational difficulty of global variations in the density matrix renormalization group.
Computational difficulty of global variations in the density matrix renormalization group.
复制标题
密度矩阵重整化群中全局变化的计算难度。
DOI：
--
复制
发表时间：
2006
影响因子：
8.6
通讯作者：
J. Eisert
中科院分区：
文献类型：
--
作者：
J. Eisert
密度矩阵重整化群方法可以说是最成功的量子自旋链基态数值求解方法。它相当于迭代地局部优化矩阵积状态，旨在越来越接近真实基态。迄今为止，既缺乏收敛到全局最佳近似的证明，也缺乏对其复杂性的评估。在这里，我们建立了一个关于矩阵积状态近似的计算复杂性的结果：令人惊讶的结果是，当一个人在局部哈密顿算子的几个位置上进行全局优化时，避免局部最优，在最坏的情况下，他会遇到一个计算困难的np困难问题（即使在近似中也很难）。该证明利用了一种将其与二元二次规划联系起来的新方法。我们讨论了描述量子多体系统困难的有趣分支。
The density matrix renormalization group approach is arguably the most successful method to numerically find ground states of quantum spin chains. It amounts to iteratively locally optimizing matrix-product states, aiming at better and better approximating the true ground state. To date, both a proof of convergence to the globally best approximation and an assessment of its complexity are lacking. Here we establish a result on the computational complexity of an approximation with matrix-product states: The surprising result is that when one globally optimizes over several sites of local Hamiltonians, avoiding local optima, one encounters in the worst case a computationally difficult NP-hard problem (hard even in approximation). The proof exploits a novel way of relating it to binary quadratic programming. We discuss intriguing ramifications on the difficulty of describing quantum many-body systems.