Simple proof of equivalence between adiabatic quantum computation and the circuit model

ORAL

Abstract

We prove the equivalence between adiabatic quantum computation and quantum computation in the standard circuit model. An explicit adiabatic computation procedure is given that generates a ground state from which the answer can be extracted. The amount of time needed is evaluated by computing the gap. We show that the procedure is computationally efficient.

*We gratefully acknowledge support from the David and Lucile Packard Foundation, Research Innovation Grant No. R10815, and NSF Grant No. PHY99-07949 (to A.M.), NSF Grant No. CCF-0523675, and ARO-QA Grant No. W911NF-05-1-0440 (to D.A.L).

–

Authors

  • Ari Mizel

    • Pennsylvania State University
    • Penn State University
    • Department of Physics, The Pennsylvania State University, University Park, PA

  • Daniel Lidar

    • University of Southern California

  • Morgan Mitchell

    • Institut de Ci\`encies Fot\`oniques