An Efficient Algorithm for approximating 1D Ground States Export

@article{citeulike:6017307, abstract = {The most commonly used algorithm for approximating ground states of 1D quantum systems is the Density Matrix Renormalization Group approach (DMRG). DMRG works very well in practice, but there is no proved guarantee for when it works, and it is easy to come up with counter examples in which it gets stuck in a local minimum. In this paper we describe an efficient classical algorithm which finds a good approximation of the ground state of a one dimensional quantum system, under the condition that such a good approximation exists by a Matrix Product State (MPS) of constant bond dimension (BD). In case the guarantee is only for a good approximation by an MPS of logarithmic BD, the algorithm becomes somewhat less efficient: it will take quasi-polynomial time to find the approximation. The assumption that the BD is small seems to hold for many interesting physical systems. We note that if the bound on the BD is polynomial, a polynomial time algorithm is unlikely to exist, since it is known that the problem of finding such approximations is NP-complete.}, archivePrefix = {arXiv}, author = {Aharonov, Dorit and Arad, Itai and Irani, Sandy}, citeulike-article-id = {6017307}, citeulike-linkout-0 = {http://arxiv.org/abs/0910.5055}, citeulike-linkout-1 = {http://arxiv.org/pdf/0910.5055}, day = {27}, eprint = {0910.5055}, month = {Oct}, posted-at = {2009-10-28 02:42:29}, priority = {2}, title = {An Efficient Algorithm for approximating 1D Ground States}, url = {http://arxiv.org/abs/0910.5055}, year = {2009} }

TY - JOUR ID - citeulike:6017307 L3 - citeulike-article-id:6017307 N2 - The most commonly used algorithm for approximating ground states of 1D quantum systems is the Density Matrix Renormalization Group approach (DMRG). DMRG works very well in practice, but there is no proved guarantee for when it works, and it is easy to come up with counter examples in which it gets stuck in a local minimum. In this paper we describe an efficient classical algorithm which finds a good approximation of the ground state of a one dimensional quantum system, under the condition that such a good approximation exists by a Matrix Product State (MPS) of constant bond dimension (BD). In case the guarantee is only for a good approximation by an MPS of logarithmic BD, the algorithm becomes somewhat less efficient: it will take quasi-polynomial time to find the approximation. The assumption that the BD is small seems to hold for many interesting physical systems. We note that if the bound on the BD is polynomial, a polynomial time algorithm is unlikely to exist, since it is known that the problem of finding such approximations is NP-complete. TI - An Efficient Algorithm for approximating 1D Ground States AU - Aharonov, Dorit AU - Arad, Itai AU - Irani, Sandy PY - 2009/Oct/27/ UR - http://arxiv.org/abs/0910.5055 ER -