Reverse Quantum Annealing Assisted by Forward Annealing

Abstract

Quantum annealers conventionally use forward annealing to generate heuristic solutions. Reverse annealing can potentially generate better solutions but necessitates an appropriate initial state. Ways to find such states are generally unknown or highly problem dependent, offer limited success, and severely restrict the scope of reverse annealing. We use a general method that improves the overall solution quality and quantity by feeding reverse annealing with low-quality solutions obtained from forward annealing. An experimental demonstration of solving the graph coloring problem using the D-Wave quantum annealers shows that our method is able to convert invalid solutions obtained from forward annealing to at least one valid solution obtained after assisted reverse annealing for 57% of 459 random Erdos–Rényi graphs. Our method significantly outperforms random initial states, obtains more unique solutions on average, and widens the applicability of reverse annealing. Although the average number of valid solutions obtained drops exponentially with the problem size, a scaling analysis for the graph coloring problem shows that our method effectively extends the computational reach of conventional forward annealing using reverse annealing.

Keywords

• reverse annealing
• forward annealing
• graph coloring