Phase transitions in quantum annealing of an NP-hard problem detected by fidelity susceptibility
Jun Takahashi, Koji Hukushima · Journal of Statistical Mechanics Theory and Experiment · 2019
Abstract Quantum annealing (QA) for the NP-hard maximum independent set problem with a unique solution is studied using the quantum Monte Carlo method. A fraction of the samples exhibit first-order phase transitions in terms of the spin-glass order parameter q . Moreover, while no singularities could be observed for the sample-averaged , a divergence in the sample-averaged fidelity susceptibility is found. Since all of the first-order transitions of q occur with smaller transverse field strength compared to the divergence point of , it is likely that the phase detected by induces the first-order transitions. This suggests that failures of QA due to exponentially small energy gaps are phenomena within this underlying phase.