Reverse annealing for the fully connected $p$-spin model

Abstract

Reverse annealing is a variant of quantum annealing that starts from a given classical configuration of spins (qubits). In contrast to the conventional formulation, where one starts from a uniform superposition of all possible states (classical configurations), quantum fluctuations are first increased and only then decreased. One then reads out the state as a proposed solution to the given combinatorial optimization problem. We formulate a mean-field theory of reverse annealing using the fully-connected ferromagnetic $p$-spin model, with and without random longitudinal fields, and analyze it in order to understand how and when reverse annealing is effective at solving this problem. We find that the difficulty arising from the existence of a first-order quantum phase transition, which leads to an exponentially long computation time in conventional quantum annealing, is circumvented in the context of this particular problem by reverse annealing if the proximity of the initial state to the (known) solution exceeds a threshold. Even when a first-order transition is unavoidable, the difficulty is mitigated due to a smaller jump in the order parameter at a first-order transition, which implies a larger rate of quantum tunneling. This is the first analytical study of reverse annealing and paves the way toward a systematic understanding of this relatively unexplored protocol in a broader context.

arXiv comment22 pages, 12 figures

References in corpus (14)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Adiabatic Quantum Computing
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Annealing and Analog Quantum Computation
• Mathematical Foundation of Quantum Annealing
• Quantum annealing with antiferromagnetic fluctuations
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• Modernizing Quantum Annealing using Local Searches
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet
• Quantum algorithm for energy matching in hard optimization problems
• Relation between quantum fluctuations and the performance enhancement of quantum annealing in a nonstoquastic Hamiltonian

Cited by in corpus (79)

• Perspectives of quantum annealing: Methods and implementations
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• Support vector machines on the D-Wave quantum annealer
• Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
• Dynamics of reverse annealing for the fully-connected $p$-spin model
• Reverse quantum annealing of the $p$-spin model with relaxation
• Counterdiabatic driving in the quantum annealing of the $p$-spin model: a variational approach
• Quantum annealing of the $p$-spin model under inhomogeneous transverse field driving
• Improving quantum annealing of the ferromagnetic $p$-spin model through pausing
• Reverse Annealing for Nonnegative/Binary Matrix Factorization
• Quantum annealing with longitudinal bias fields
• Travel time optimization on multi-AGV routing by reverse annealing
• Finding spin-glass ground states using quantum walks
• Calibration of flux crosstalk in large-scale flux-tunable superconducting quantum circuits
• An energetic perspective on rapid quenches in quantum annealing
• Genetic optimization of quantum annealing
• Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
• Dissipative phase transitions in the fully-connected Ising model with $p$-spin interaction
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Variationally Scheduled Quantum Simulation
• Advanced anneal paths for improved quantum annealing
• Greedy parameter optimization for diabatic quantum annealing
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Many-body localization enables iterative quantum optimization
• Breakdown of the weak coupling limit in quantum annealing
• Out-of-equilibrium dynamics arising from slow round-trip variations of Hamiltonian parameters across quantum and classical critical points
• Multifractal phase in the weighted adjacency matrices of random Erdös-Rényi graphs
• A double-slit proposal for quantum annealing
• Counterdiabatic Reverse Annealing
• Noise Dynamics of Quantum Annealers: Estimating the Effective Noise Using Idle Qubits
• Achieving fair sampling in quantum annealing
• Phase Transitions of the Maximum Likelihood Estimates in the $p$-Spin Curie-Weiss Model
• Customized quantum annealing schedules
• Initial State Encoding via Reverse Quantum Annealing and h-gain Features
• Deep learning optimal quantum annealing schedules for random Ising models
• Effectiveness of quantum annealing for continuous-variable optimization
• Anatomy of the eigenstates distribution: a quest for a genuine multifractality
• Diagonal Catalysts in Quantum Adiabatic Optimization
• Cyclic Quantum Annealing: Searching for Deep Low-Energy States in 5000-Qubit Spin Glass
• VanQver: The Variational and Adiabatically Navigated Quantum Eigensolver
• Performance enhancement of quantum annealing under the Lechner-Hauke-Zoller scheme by non-linear driving of the constraint term
• Efficient population transfer via non-ergodic extended states in quantum spin glass
• Dynamics of Order Parameters of Non-stoquastic Hamiltonians in the Adaptive Quantum Monte Carlo Method
• Track clustering with a quantum annealer for primary vertex reconstruction at hadron colliders
• Particle Track Classification Using Quantum Associative Memory
• Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms
• Phase transitions in the frustrated Ising ladder with stoquastic and nonstoquastic catalysts
• Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem
• Diagnosing First and Second Order Phase Transitions with Probes of Quantum Chaos
• Demonstration of long-range correlations via susceptibility measurements in a one-dimensional superconducting Josephson spin chain
• The quantum annealing gap and quench dynamics in the exact cover problem
• Quantum annealing sampling with a bias field
• Continuous-time quantum optimisation without the adiabatic principle
• Discriminating Non-Isomorphic Graphs with an Experimental Quantum Annealer
• Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer
• Zeno-effect Computation: Opportunities and Challenges
• Nonstoquastic catalyst for bifurcation-based quantum annealing of ferromagnetic $p$-spin model
• Quantum annealer accelerates the variational quantum eigensolver in a triple-hybrid algorithm
• Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments
• Mapping State Transition Susceptibility in Quantum Annealing
• Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
• Deep Unfolded Local Quantum Annealing
• Reverse quantum annealing assisted by forward annealing
• Hardness-dependent quantum adiabatic schedules for the maximum-independent-set problem
• Fighting Exponentially Small Gaps by Counterdiabatic Driving
• Quantum Hopfield Model with Dilute Memories
• Limit theorems for dependent combinatorial data, with applications in statistical inference
• Effect of Quantum Statistics on Computational Power of Atomic Quantum Annealers
• Inferring the Dynamics of the State Evolution During Quantum Annealing
• The anomalously slow dynamics of inhomogeneous quantum annealing
• Noise Effects on Diabatic Quantum Annealing Protocols
• Analog Errors in Quantum Annealing: Doom and Hope
• Quantum Annealing Algorithms for Estimating Ising Partition Functions
• Mixed phases in feedback Ising models
• Robust phase estimation of the ground-state energy without controlled time evolution on a quantum device
• Reducing quantum annealing biases for solving the graph partitioning problem
• Replica approach to the generalized Rosenzweig-Porter model