Diversity measure for discrete optimization: Sampling rare solutions via algorithmic quantum annealing

Sampling a diverse set of high-quality solutions for hard optimization problems is of great practical relevance in many scientific disciplines and applications, such as artificial intelligence and operations research. One of the main open problems is the lack of ergodicity, or mode collapse, for typical stochastic solvers based on Monte Carlo techniques leading to poor generalization or lack of robustness to uncertainties. Currently, there is no universal metric to quantify such performance deficiencies across various solvers. Here, we introduce a new diversity measure for quantifying the number of independent approximate solutions for NP-hard optimization problems.

To test this metric, we compare the sampling power of various quantum annealing strategies, as applied to random frustrated 2D spin systems with local fields. Using Path-Integral Monte Carlo simulations, we show that the inhomogeneous quantum annealing schedules can redistribute and suppress the emergence of topological defects by controlling space-time separated critical fronts, leading to an advantage over standard quantum annealing schedules for finding rare solutions; quantified by Time-To-Diversity.