Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimization

Abstract

Quantum hardware and quantum-inspired algorithms are becoming increasingly popular for combinatorial optimization. However, these algorithms may require careful hyperparameter tuning for each problem instance. We use a reinforcement learning agent in conjunction with a quantum-inspired algorithm to solve the Ising energy minimization problem, which is equivalent to the Maximum Cut problem. The agent controls the algorithm by tuning one of its parameters with the goal of improving recently seen solutions. We propose a new Rescaled Ranked Reward (R3) method that enables stable single-player version of self-play training that helps the agent to escape local optima. The training on any problem instance can be accelerated by applying transfer learning from an agent trained on randomly generated problems. Our approach allows sampling high-quality solutions to the Ising problem with high probability and outperforms both baseline heuristics and a black-box hyperparameter optimization approach.

arXiv commentSubmitted to ICML 2020. 9 pages, 3 pdf figures. V2: fixed acknowledgements

References in corpus (14)

• A Quantum Approximate Optimization Algorithm
• Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
• Learning Combinatorial Optimization Algorithms over Graphs
• A Learned Representation For Artistic Style
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• Device Placement Optimization with Reinforcement Learning
• Learning to Perform Local Rewriting for Combinatorial Optimization
• Destabilization of local minima in analog spin systems by correction of amplitude heterogeneity
• Learning Heuristics over Large Graphs via Deep Reinforcement Learning
• Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization
• Emulating the coherent Ising machine with a mean-field algorithm
• Exploratory Combinatorial Optimization with Reinforcement Learning
• Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero