Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
arXiv:2212.08634 · doi:10.1103/PhysRevA.107.062602
Abstract
Quantum annealing is a contender to solve combinatorial optimization problems based on quantum dynamics. While significant efforts have been undertaken to investigate the quality of the solutions and the required runtimes, much less attention has been paid to understanding the dynamics of quantum annealing and the process leading to the solution during the sweep itself. In this comprehensive study, we investigate various aspects of the quantum annealing dynamics using different approaches. We perform quantum annealing, simulated quantum annealing, and classical annealing on several hundred instances of the Sherrington-Kirkpatrick model with intermediate system sizes up to 22 spins using numerical simulations. We observe qualitative differences between the quantum and classical methods, in particular at intermediate times, where a peak in the fidelity, also known as diabatic bump, appears for hard instances. Furthermore, we investigate the two-point correlation functions, which feature differences at intermediate times as well. At short times, however, the methods are similar again, which can be explained by relating the short-time expansion of quantum annealing to a high-temperature expansion, thus allowing in principle to find the classical solution already at short times, albeit at prohibitive sampling cost.
arXiv commentrevised version: 22 pages, 11 figures
References in corpus (46)
- SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
- The NumPy array: a structure for efficient numerical computation
- Quantum Annealing in the Transverse Ising Model
- Adiabatic Quantum Computing
- The Magnus expansion and some of its applications
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Spin-lattice coupling in frustrated antiferromagnets
- Perspectives of quantum annealing: Methods and implementations
- Mathematical Foundation of Quantum Annealing
- The simplest quantum model supporting the Kibble-Zurek mechanism of topological defect production: Landau-Zener transitions from a new perspective
- What is the Computational Value of Finite Range Tunneling?
- Quantum critical dynamics in a 5000-qubit programmable spin glass
- Anderson localization casts clouds over adiabatic quantum optimization
- Quantum versus Classical Annealing of Ising Spin Glasses
- Transition times in the Landau-Zener model
- Quantum Annealing: An Overview
- Scaling advantage in quantum simulation of geometrically frustrated magnets
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
- Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
- High-order commutator-free exponential time-propagation of driven quantum systems
- Extremal Optimization for Sherrington-Kirkpatrick Spin Glasses
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
- On quantum mean-field models and their quantum annealing
- Adiabatic Theorem for Quantum Spin Systems
- Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs
- Quantum annealing: the fastest route to quantum computation?
- The Power of Adiabatic Quantum Computation with No Sign Problem
- An energetic perspective on rapid quenches in quantum annealing
- The Quest for Solvable Multistate Landau-Zener Models
- Simulated quantum annealing as a simulator of non-equilibrium quantum dynamics
- Quantum Sampling Algorithms for Near-Term Devices
- Collective excitations and marginal stability of quantum Ising spin glasses
- Simulated Quantum Annealing with Two All-to-All Connectivity Schemes
- Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian
- De-Signing Hamiltonians for Quantum Adiabatic Optimization
- Energy gap at first-order quantum phase transitions: An anomalous case
- Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
- Thermal, quantum and simulated quantum annealing: analytical comparisons for simple models
- Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians
- On the hardness of quadratic unconstrained binary optimization problems
- Relation of classical non-equilibrium dynamics and quantum annealing