Preparing Ground States of Quantum Many-Body Systems on a Quantum Computer

    Authors

    D. Poulin;P. Wocjan

    Abbreviated Journal Title

    Phys. Rev. Lett.

    Keywords

    FRUSTRATION MODEL; SPIN-GLASS; NP; Physics, Multidisciplinary

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

    Journal Title

    Physical Review Letters

    Volume

    102

    Issue/Number

    13

    Publication Date

    1-1-2009

    Document Type

    Article

    Language

    English

    First Page

    4

    WOS Identifier

    WOS:000264888600004

    ISSN

    0031-9007

    Share

    COinS