Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Simulation of many-body quantum systems on a classical computer usually requires resources growing exponentially with the size of the system. In order to make a practical simulation possible, approximate numerical algorithms such as DMRG, quantum Monte Carlo, or the coupled cluster method have been developed. Although these algorithms work quite well in practice, it is not known whether they are efficient in the complexity-theoretic sense, that is, whether their worst case running time grows only polynomially with the number of spins and the required precision. In my talk I will outline the main ideas of the complexity-theoretic approach to quantum Hamiltonian problems and review the progress achieved during the last years. In the second part of the talk I will describe the coupled cluster method that permits simulation of weakly-interacting spin systems and a random walk algorithm for simulating quantum adiabatic evolution with frustration-free Hamiltonians avoiding the "sign problem". Both algorithms are efficient in the complexity-theoretic sense.