"Phase transition in Quantum Annealing for Maximum Independent Set problems"


Jun Takahashi (Univ. of Tokyo)


There has been several attempts to figure out what is the main obstacle for computing NP-complete problems using quantum annealing (quantum adiabatic computation). While numerical calculations have revealed that quantum annealing most likely takes exponential time to calculate NP-complete problems, there hasn' It been an established physical picture of the obstacle. Different scenarios such as avoided crossings, Anderson localization, or spin glass transitions have been discussed. We use the stochastic series expansion method (SSE) to analyze the transition in quantum annealing for a particular NP-complete problem. We look at several quantities such as the spin glass order parameter, fidelity susceptibility, and the energy gap, and discuss the consistencies with different scenarios.

Designed by CSS.Design Sample