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

 Titre Preparing ground states of quantum many-body systems on a quantum computer Type de publication Journal Article Nouvelles publications 2009 Auteurs Poulin D, Wocjan P Journal Physical Review Letters Volume 102 Pagination 130503 Mots clés Complexity, Quantum simulation Résumé Preparing the ground state of a system of interacting classical particles is an NP-hard problem. Thus, there is in general no better algorithm to solve this problem than exhaustively going through all $N$ configurations of the system to determine the one with lowest energy, requiring a running time proportional to $N$. A quantum computer, if it could be built, could solve this problem in time $\sqrt N$. Here, we present a powerful extension of this result to the case of interacting {\em quantum} particles, demonstrating that a quantum computer can prepare the ground state of a quantum system as efficiently as it does for classical systems.