Preparing ground states of quantum many-body systems on a quantum computer

The simulation of quantum many-body systems is a notoriously hard problem in condensed matter physics, but it could easily be handled by a quantum computer [4,1]. There is however one catch: while a quantum computer can naturally implement the dynamics of a quantum system --- i.e. solve Schr\"odinger's equation --- there was until now no general method to initialize the computer in a low-energy state of the simulated system. We present a quantum algorithm [5] that can prepare the ground state and thermal states of a quantum many-body system in a time proportional to the square-root of its Hilbert space dimension. This is the same scaling as required by the best known algorithm to prepare the ground state of a classical many-body system on a quantum computer [3,2]. This provides strong evidence that for a quantum computer, preparing the ground state of a quantum system is in the worst case no more difficult than preparing the ground state of a classical system. \begin{thebibliography}{1} \bibitem{AT03b} {\sc D.~Aharonov and A.~Ta-Shma}, {\em Adiabatic quantum state generation and statistical zero knowledge}, Proc. 35th Annual ACM Symp. on Theo. Comp., (2003), p.~20. \bibitem{B82a} {\sc F.~Barahona}, {\em On the computational complexity of ising spin glass models}, J. Phys. A. Math. Gen., 15 (1982), p.~3241. \bibitem{BBBV97a} {\sc C.~H. Bennett, E.~Bernstein, G.~Brassard, and U.~Vazirani}, {\em Strengths and weaknessess of quantum computing}, SIAM J. Comput., 26 (1997), pp.~1510--1523, quant-ph/9701001. \bibitem{Llo96b} {\sc S.~Lloyd}, {\em Universal quantum simulators}, Science, 273 (1996), pp.~1073--1078. \bibitem{PW08a} {\sc D.~Poulin and P.~Wocjan}, {\em Preparing ground states of quantum many-body systems on a quantum computer}, 2008, arXiv:0809.2705. \end{thebibliography}