Home | About Journal | Web Links | E-mail Alerts | RSS RSS Icon | Browse
Previous Article Next Article

Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems

Source: Phys. Rev. E 84, 061152 (2012); http://dx.doi.org/10.1103/PhysRevE.84.061152

Published 29 December 2011

PACS
  • 75.10.Nr
    Spin-glass and other random models (magnetism)
  • 03.67.Lx
    Quantum computation architectures and implementations
  • 03.67.Ac
    Quantum algorithms, protocols and simulations
  • 64.70.Tg
    Quantum phase transitions
  • YEAR: 2011
PUBLICATION DATA
Publisher:
AIP is a member of CrossRef APS
Itay Hen and A. P. Young
Department of Physics, University of California, Santa Cruz, California 95064, USA
We determine the complexity of several constraint satisfaction problems using the quantum adiabatic algorithm in its simplest implementation. We do so by studying the size dependence of the gap to the first excited state of “typical” instances. We find that, at large sizes N, the complexity increases exponentially for all models that we study. We also compare our results against the complexity of the analogous classical algorithm WalkSAT and show that the harder the problem is for the classical algorithm, the harder it is also for the quantum adiabatic algorithm.
History: Received 1 October 2011; published 29 December 2011
Digital Object Identifier: http://dx.doi.org/10.1103/PhysRevE.84.061152
ADVERTISEMENT