Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
arXiv:2202.10908 · doi:10.1103/PhysRevA.106.012418
Abstract
Providing an optimal path to a quantum annealing algorithm is key to finding good approximate solutions to computationally hard optimization problems. Reinforcement is one of the strategies that can be used to circumvent the exponentially small energy gaps of the system in the annealing process. Here a time-dependent reinforcement term is added to the Hamiltonian in order to give lower energies to the most probable states of the evolving system. In this study, we take a local entropy in the configuration space for the reinforcement and apply the algorithm to a number of easy and hard optimization problems. The reinforced algorithm performs better than the standard quantum annealing algorithm in the quantum search problem, where the optimal parameters behave very differently depending on the number of solutions. Moreover, the reinforcements can change the discontinuous phase transitions of the mean-field p-spin model () to a continuous transition. The algorithm's performance in the binary perceptron problem is also superior to that of the standard quantum annealing algorithm, which already works better than a classical simulated annealing algorithm.
arXiv comment28 pages, 12 figures
References in corpus (51)
- Quantum Annealing in the Transverse Ising Model
- Adiabatic Quantum Computing
- Quantum Annealing and Analog Quantum Computation
- Shortcuts to adiabaticity by counter-diabatic driving
- Feedback-control of quantum systems using continuous state-estimation
- Measurement-based quantum control of mechanical motion
- Experimental signature of programmable quantum annealing
- Minimizing irreversible losses in quantum systems by local counter-diabatic driving
- Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
- Anderson localization casts clouds over adiabatic quantum optimization
- Reverse Quantum Annealing Approach to Portfolio Optimization Problems
- A different kind of quantum search
- Hamiltonian complexity
- Adiabatic tracking of quantum many-body dynamics
- Learning by message-passing in networks of discrete synapses
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
- 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
- Efficient supervised learning in networks with binary synapses
- Reverse annealing for the fully connected -spin model
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- First-order transitions and the performance of quantum algorithms in random optimization problems
- Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass
- Efficient Quantum State Estimation by Continuous Weak Measurement and Dynamical Control
- A Coherent Quantum Annealer with Rydberg Atoms
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- Dynamics of reverse annealing for the fully-connected -spin model
- On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations
- Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet
- On quantum mean-field models and their quantum annealing
- Accuracy vs run time in adiabatic quantum search
- Efficiency of quantum versus classical annealing in non-convex learning problems
- Shortcuts to adiabaticity for quantum annealing
- Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
- Quantum phase transitions in fully connected spin models: an entanglement perspective
- Quantum annealing with longitudinal bias fields
- Storage capacity in symmetric binary perceptrons
- Finding spin-glass ground states using quantum walks
- Quantum annealing with ultracold atoms in a multimode optical resonator
- The Power of Adiabatic Quantum Computation with No Sign Problem
- An energetic perspective on rapid quenches in quantum annealing
- Relation between quantum fluctuations and the performance enhancement of quantum annealing in a nonstoquastic Hamiltonian
- Finding a marked node on any graph by continuous-time quantum walk
- Fixed-Point Adiabatic Quantum Search
- Ground States of Fermionic lattice Hamiltonians with Permutation Symmetry
- Sign problem in the Bethe approximation
- Optimization by a quantum reinforcement algorithm
- Quantum search using non-Hermitian adiabatic evolution
- Statistical physics approach to graphical games: local and global interactions
- Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm