Send to

Choose Destination
Phys Rev Lett. 2009 Apr 3;102(13):130503. Epub 2009 Apr 3.

Preparing ground States of quantum many-body systems on a quantum computer.

Author information

Département de Physique, Université de Sherbrooke, Sherbrooke, Québec, Canada.


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 quantum particles, demonstrating that a quantum computer can prepare the ground state of a quantum system as efficiently as it does for classical systems.

Supplemental Content

Full text links

Icon for American Physical Society
Loading ...
Support Center