# Publications

@article{PW09a,

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}}

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}}