Zero-temperature quantum annealing bottlenecks in the spin-glass phase

Area of Science:

• Quantum Computing
• Computational Physics
• Optimization

Background:

• Quantum adiabatic annealing is a promising method for solving complex binary optimization problems.
• The algorithm tracks a ground state as it localizes towards the global minimum.
• Bottlenecks occur in regions with small energy gaps to excited states, particularly at phase transitions.

Purpose of the Study:

• To analyze the complexity and bottleneck behavior of quantum adiabatic annealing for binary optimization.
• To investigate the scaling of energy gaps in different phases of the annealing process.
• To rigorously demonstrate these phenomena using specific models.

Main Methods:

• Theoretical analysis of quantum adiabatic annealing.
• Investigation of energy gap scaling within the spin-glass phase.
• Rigorous demonstration using the two-pattern Gaussian Hopfield model.
• Qualitative comparison with the Sherrington-Kirkpatrick model.

Main Results:

• For large problems, complexity is dominated by O(log N) bottlenecks in the spin-glass phase, with a stretched exponential gap scaling.
• For smaller N, the critical point gap, scaling polynomially for second-order phase transitions, becomes the primary limitation.
• The analysis provides a rigorous understanding of performance limitations.

Conclusions:

• The complexity of quantum adiabatic annealing is highly dependent on the problem size and the nature of the energy gap.
• Understanding bottleneck scaling is crucial for designing efficient quantum optimization algorithms.
• The findings offer insights into the practical applicability of quantum annealing for hard optimization tasks.