Physics – Quantum Physics
Scientific paper
2006-09-07
Phys. Rev. Lett. 97, 260501 (2006)
Physics
Quantum Physics
5 pages, 1 figure, RevTeX, final version
Scientific paper
The density matrix renormalization group (DMRG) 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.
No associations
LandOfFree
Computational Difficulty of Global Variations in the Density Matrix Renormalization Group does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computational Difficulty of Global Variations in the Density Matrix Renormalization Group, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computational Difficulty of Global Variations in the Density Matrix Renormalization Group will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-318024