Sampling diverse near-optimal solutions via algorithmic quantum annealing

Abstract

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%.

13 pages, 6 figures, close to published version

References in corpus (9)

• The density-matrix renormalization group in the age of matrix product states
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Robots that can adapt like animals
• Structural defects in ion crystals by quenching the external potential: the inhomogeneous Kibble-Zurek mechanism
• Adiabatic quantum dynamics of a random Ising chain across its quantum critical point
• Focus on Shortcuts to Adiabaticity
• Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
• Adiabatic dynamics of an inhomogeneous quantum phase transition: the case of z > 1 dynamical exponent
• Fair sampling of ground-state configurations of binary optimization problems

Cited by in corpus (5)

• Energy landscapes of combinatorial optimization in Ising machines
• Limitations of tensor network approaches for optimization and sampling: A comparison to quantum and classical Ising machines
• Inhomogeneous adiabatic preparation of a quantum critical ground state in two dimensions
• Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA
• Recent quantum runtime (dis)advantages