Computational difficulty of simulation methods: Density Functional Theory, DMRG, and beyond

          @misc{ pirsa_PIRSA:08110022,
            doi = {10.48660/08110022},
            url = {https://pirsa.org/08110022},
            author = {Schuch, Norbert},
            keywords = {Quantum Information},
            language = {en},
            title = {Computational difficulty of simulation methods: Density Functional Theory, DMRG, and beyond },
            publisher = {Perimeter Institute},
            year = {2008},
            month = {nov},
            note = {PIRSA:08110022 see, \url{https://pirsa.org}}
          }
          

Abstract

We analyze how quantum complexity poses bounds to the simulation of quantum systems. While methods as Density Functional Theory (DFT) and the Density Matrix Renormalization Group (DMRG) work very well in practice, essentially nothing on the formal requirements is known. In this talk, we consider these methods from a quantum complexity perspective: First, we discuss DFT which encapsulates the difficulty of solving the Schroedinger equation in a universal functional and show that this functional cannot be efficiently computed unless several complexity classes collapse. Second, we consider DMRG, a method to deal with quantum spin chains, and show that even under reasonable assumptions -- a polynomial gap and matrix product ground states -- finding the ground state is still a computationally hard problem. Beyond pinpointing the limitations of the methods, this helps us to understand under which assumptions we might be able to prove their convergence.