arXiv:0910.1378 Abstract | arXiv Analytics

arXiv:0910.1378 [cond-mat.stat-mech]Abstract References Reviews Resources

First order phase transition in the Quantum Adiabatic Algorithm

A. P. Young, S. Knysh, V. N. Smelyanskiy

Published 2009-10-07, updated 2010-01-19Version 2

We simulate the quantum adiabatic algorithm (QAA) for the exact cover problem for sizes up to N=256 using quantum Monte Carlo simulations incorporating parallel tempering. At large N we find that some instances have a discontinuous (first order) quantum phase transition during the evolution of the QAA. This fraction increases with increasing N and may tend to 1 for N -> infinity.

Comments: 5 pages, 3 figures. Replaced with published version; two figures slightly changed and some small changes to the text

Journal: Phys. Rev. Lett. 104, 020502 (2010)

DOI: 10.1103/PhysRevLett.104.020502

Categories: cond-mat.stat-mech, cond-mat.dis-nn, quant-ph

Subjects: 03.67.Ac, 03.67.Lx, 64.70.Tg, 75.10.Nr

Keywords: first order phase transition, quantum adiabatic algorithm, carlo simulations incorporating parallel, monte carlo simulations incorporating, simulations incorporating parallel tempering

Tags: journal article

Related articles: Most relevant | Search more

arXiv:1109.6872 [cond-mat.stat-mech] (Published 2011-09-30, updated 2011-12-29)

Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems

Itay Hen, A. P. Young

arXiv:cond-mat/0204349 (Published 2002-04-16, updated 2002-06-26)