Bounding first-order quantum phase transitions in adiabatic quantum computing

Abstract

In the context of adiabatic quantum computation (AQC), it has been argued that first-order quantum phase transitions (QPTs) due to localisation phenomena cause AQC to fail by exponentially decreasing the minimal spectral gap of the Hamiltonian along the annealing path as a function of the qubit number. The vanishing of the spectral gap is often linked to the localisation of the ground state in a local minimum, requiring the system to tunnel into the global minimum at a later stage of the annealing. Recent methods have been proposed to avoid this phenomenon by carefully designing the involved Hamiltonians. However, it remains a challenge to formulate a comprehensive theory of the effect of the various parameters and the conditions under which QPTs make the AQC algorithm fail. Equipped with concepts from graph theory, in this work we link graph quantities associated to the Hamiltonians along the annealing path with the occurrence of QPTs. These links allow us to derive bounds on the location of the minimal spectral gap along the annealing path, augmenting the toolbox for the analysis of strategies to improve the runtime of AQC algorithms.

arXiv comment14 pages, 7 figures

References in corpus (17)

• Ising formulations of many NP problems
• Adiabatic Quantum Computing
• Quantum Search by Local Adiabatic Evolution
• Anderson localization casts clouds over adiabatic quantum optimization
• First order phase transition in the Quantum Adiabatic Algorithm
• First Order Quantum Phase Transition in Adiabatic Quantum Computation
• First-order transitions and the performance of quantum algorithms in random optimization problems
• Quantum Annealing for Constrained Optimization
• Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
• Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
• Simulating complex quantum networks with time crystals
• Different Adiabatic Quantum Optimization Algorithms for the NP-Complete Exact Cover and 3SAT Problems
• Degeneracy, degree, and heavy tails in quantum annealing
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Elimination of Perturbative Crossings in Adiabatic Quantum Optimization
• Ergodic-localized junctions in periodically-driven systems
• Phase transitions in the frustrated Ising ladder with stoquastic and nonstoquastic catalysts

Cited by in corpus (3)

• Adiabatic Bottlenecks in Quantum Annealing and Nonequilibrium Dynamics of Paramagnons
• Asymptotic Exceptional Steady States in Dissipative Dynamics
• Anti-crossings occurrence as exponentially closing gaps in Quantum Annealing