Standard quantum annealing outperforms adiabatic reverse annealing with decoherence

Abstract

We study adiabatic reverse annealing (ARA) in an open system. In the closed system (unitary) setting, this annealing protocol allows avoidance of first-order quantum phase transitions of selected models, resulting in an exponential speedup compared with standard quantum annealing, provided that the initial state of the algorithm is close in Hamming distance to the target one. Here, we show that decoherence can significantly modify this conclusion: by resorting to the adiabatic master equation approach, we simulate the dynamics of the ferromagnetic $p$-spin model with $p=3$ under independent and collective dephasing. For both models of decoherence, we show that the performance of open system ARA is far less sensitive to the choice of the initial state than its unitary counterpart, and, most significantly, that open system ARA by and large loses its time to solution advantage compared to standard quantum annealing. These results suggest that as a stand-alone strategy, ARA is unlikely to experimentally outperform standard "forward" quantum annealing, and that error mitigation strategies will likely be required in order to realize the benefits of ARA in realistic, noisy settings.

arXiv comment12 pages, 11 figures

References in corpus (68)

• Quantum Annealing in the Transverse Ising Model
• Decoherence Free Subspaces for Quantum Computation
• Adiabatic Quantum Computing
• Noiseless Quantum Codes
• Quantum annealing with more than one hundred qubits
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Search by Local Adiabatic Evolution
• Defining and detecting quantum speedup
• Perspectives of quantum annealing: Methods and implementations
• Bounds for the adiabatic approximation with applications to quantum computation
• Quantum Adiabatic Markovian Master Equations
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• A case study in programming a quantum annealer for hard operational planning problems
• Adiabatic Quantum Computation in Open Systems
• Quantum annealing of the Traveling Salesman Problem
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• Adiabatic approximation in open quantum systems
• Error corrected quantum annealing with hundreds of qubits
• Entanglement in a quantum annealing processor
• Quantum Speedup by Quantum Annealing
• Quantum annealing versus classical machine learning applied to a simplified computational biology problem
• Decoherence in adiabatic quantum computation
• Application of Quantum Annealing to Nurse Scheduling Problem
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Optimal Protocols in Quantum Annealing and QAOA Problems
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
• Thermally assisted adiabatic quantum computation
• Reverse annealing for the fully connected $p$-spin model
• Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
• Experimental determination of Ramsey numbers
• Modernizing Quantum Annealing using Local Searches
• Quantum Annealing Correction with Minor Embedding
• Adiabaticity in open quantum systems
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
• Dynamics of reverse annealing for the fully-connected $p$-spin model
• Benchmarking Quantum Annealing Controls with Portfolio Optimization
• Accuracy vs run time in adiabatic quantum search
• A deceptive step towards quantum speedup detection
• General Adiabatic Evolution with a Gap Condition
• Adiabatic response for Lindblad dynamics
• Reverse quantum annealing of the $p$-spin model with relaxation
• Quantum annealing of the $p$-spin model under inhomogeneous transverse field driving
• Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
• Improving quantum annealing of the ferromagnetic $p$-spin model through pausing
• Nested Quantum Annealing Correction
• Non-ergodic delocalized states for efficient population transfer within a narrow band of the energy landscape
• Quantum annealing with longitudinal bias fields
• Adiabatic Markovian Dynamics
• Reexamination of the evidence for entanglement in the D-Wave processor
• Why and when is pausing beneficial in quantum annealing?
• A dissipative environment may improve the quantum annealing performances of the ferromagnetic p-spin model
• Charged particle tracking with quantum annealing-inspired optimization
• Eigenstate Tracking in Open Quantum Systems
• On the optimal working point in dissipative quantum annealing
• Comparing relaxation mechanisms in quantum and classical transverse-field annealing
• Optimal Control for Closed and Open System Quantum Optimization
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Quantum trajectories for time-dependent adiabatic master equations
• Optimally Stopped Optimization
• Assessment of Quantum Annealing for the Construction of Satisfiability Filters
• Search range in experimental quantum annealing
• Ferromagnetically shifting the power of pausing
• Achieving fair sampling in quantum annealing
• Diagonal Catalysts in Quantum Adiabatic Optimization
• Probing Environmental Spin Polarization with Superconducting Flux Qubits
• Gap-independent cooling and hybrid quantum-classical annealing

Cited by in corpus (12)

• Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
• Dissipative time crystals with long-range Lindbladians
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Counterdiabatic Reverse Annealing
• Initial State Encoding via Reverse Quantum Annealing and h-gain Features
• Deep learning optimal quantum annealing schedules for random Ising models
• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters
• Quantum annealing sampling with a bias field
• Mapping State Transition Susceptibility in Quantum Annealing
• Noise Effects on Diabatic Quantum Annealing Protocols
• Quantum Annealing Algorithms for Estimating Ising Partition Functions