Role of Classical Hardness for Quantum Annealers

The D-Wave Two chip presumably exploits quantum annealing effects to solve optimization problems. Whether D-wave's quantum annealer is capable of achieving real speedup over classical thermal annealers is a matter of investigation. In this context, specifically of importance is the question of how well quantum annealers perform on instances with rugged free-energy landscapes for which simulated annealing methods are expected to fail. I will describe attempts to identify very hard D-Wave-specific instances exhibiting ``temperature chaos'' by means of state-of-the-art methods (multi spin coding, parallel tempering simulations and stochastic time-series analysis), and present results pertaining to the performance of classical algorithms and the D-wave Two chip on these.