  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. Among
others, it allows benchmarking solver performance by a required
time-to-diversity (TTD), a generalization of often used time-to-solution (TTS).
We illustrate this metric by comparing the sampling power of various quantum
annealing strategies. In particular, 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 with respect to both TTS
and TTD for finding rare solutions. Using path-integral Monte Carlo simulations
for up to 1600 qubits, we demonstrate that nonequilibrium driving of quantum
fluctuations, guided by efficient approximate tensor network contractions, can
significantly reduce the fraction of hard instances for random frustrated 2D
spin-glasses with local fields. Specifically, we observe that by creating a
class of algorithmic quantum phase transitions, the diversity of solutions can
be enhanced by up to 40% with the fraction of hard-to-sample instances reducing
by more than 25%.
