Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
arXiv:1812.02569 · doi:10.1103/PhysRevA.98.062309
Abstract
The standard quantum annealing algorithm tries to approach the ground state of a classical system by slowly decreasing the hopping rates of a quantum random walk in the configuration space of the problem, where the on-site energies are provided by the classical energy function. In a quantum reinforcement algorithm, the annealing works instead by increasing gradually the strength of the on-site energies according to the probability of finding the walker on each site of the configuration space. Here, by using the path-integral Monte Carlo simulations of the quantum algorithms, we show that annealing via reinforcement can significantly enhance the success probability of the quantum walker. More precisely, we implement a local version of the quantum reinforcement algorithm, where the system wave function is replaced by an approximate wave function using the local expectation values of the system. We use this algorithm to find solutions to a prototypical constraint satisfaction problem (XORSAT) close to the satisfiability to unsatisfiability phase transition. The study is limited to small problem sizes (a few hundreds of variables), nevertheless, the numerical results suggest that quantum reinforcement may provide a useful strategy to deal with other computationally hard problems and larger problem sizes even as a classical optimization algorithm.
arXiv comment18 pages, 4 figures
References in corpus (34)
- Quantum algorithm for solving linear systems of equations
- Ising formulations of many NP problems
- A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum random walks - an introductory overview
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Shortcuts to adiabaticity by counter-diabatic driving
- Feedback-control of quantum systems using continuous state-estimation
- Simulating quantum computation by contracting tensor networks
- Experimental signature of programmable quantum annealing
- Inverse statistical problems: from the inverse Ising problem to data science
- Minimizing irreversible losses in quantum systems by local counter-diabatic driving
- Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- Anderson localization casts clouds over adiabatic quantum optimization
- Clustering of solutions in the random satisfiability problem
- Quantum Optimization of Fully-Connected Spin Glasses
- Adiabatic tracking of quantum many-body dynamics
- Learning by message-passing in networks of discrete synapses
- Clusters of solutions and replica symmetry breaking in random k-satisfiability
- Simplest random K-satisfiability problem
- The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- Exact solutions for diluted spin glasses and optimization problems
- On the freezing of variables in random constraint satisfaction problems
- First-order transitions and the performance of quantum algorithms in random optimization problems
- Efficient Quantum State Estimation by Continuous Weak Measurement and Dynamical Control
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations
- Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
- Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
- Optimization by a quantum reinforcement algorithm
- Sign problem in the Bethe approximation
- Statistical physics approach to graphical games: local and global interactions