Équipe de Recherche en Physique de l'Information Quantique


Abstract = {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. },
Author = {David Poulin and Pawel Wocjan},
Date-Added = {2008-09-16 10:33:27 -0400},
Date-Modified = {2010-05-06 13:39:48 -0400},
Eprint = {arXiv:0809.2705},
Journal = {Phys. Rev. Lett.},
Keywords = {Complexity; Quantum simulation},
Local-Url = {PW09b.pdf},
Pages = {130503},
Title = {Preparing ground states of quantum many-body systems on a quantum computer},
Volume = {102},
Year = {2009}}