Abstract

One of the major ongoing debates on the future of quantum annealers pertains to their robustness against the decohering effects of finite temperature and interactions with the environment. We argue that even in an ideal setting of very low temperatures and in the absence of a decohering environment, quantum annealers may find it challenging to solve optimization problems significantly faster than state-of-the-art heuristic classical algorithms. Here, we study the performance of the quantum adiabatic algorithm (QAA) on a variety of constraint satisfaction problems by examining the size dependence of the minimum energy gap during the evolution of the QAA. We do so by employing Quantum Monte Carlo schemes as these allow us to study these problems at much larger scales than exact methods would allow. We find that in all cases a quantum phase transition occurs and the minimum gap decreases …

Date

2015

Authors

I Hen, AP Young

Source

The European Physical Journal Special Topics

Volume

224

Issue

1

Pages

63-73

Publisher

Springer Berlin Heidelberg