Unraveling Quantum Annealers using Classical Hardness

Area of Science:

• Quantum Computing
• Computational Physics
• Optimization Theory

Background:

• Programmable quantum annealers, such as D-Wave chips, offer potential speedups for optimization problems.
• Distinguishing quantum annealers from classical thermal systems remains a challenge.
• Spin-glass theory identifies 'temperature chaos' as a cause of computational intractability.

Purpose of the Study:

• To develop a method for quantifying quantum annealer performance on temperature-chaotic problems.
• To investigate the role of quantum effects in potential speedups.
• To experimentally assess the D-Wave Two chip's performance.

Main Methods:

• Devised a general method to quantify quantum annealer performance on problems with varying temperature chaos.
• Experimentally studied the D-Wave Two chip using this method.
• Compared quantum annealer performance against analogous classical algorithms.

Main Results:

• The D-Wave Two chip's performance scaled unfavorably compared to classical algorithms on tested problems.
• Identified and quantified several classical effects that may obscure quantum behavior.
• Found no evidence of quantum speedup in the experimental setup.

Conclusions:

• Quantum annealers may not inherently outperform classical algorithms on all optimization problems.
• Classical effects can significantly influence and potentially mask quantum behavior.
• Further research is needed to understand the true capabilities and limitations of quantum annealing.