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

arXiv comment13 pages, 6 figures, close to published version

References in corpus (44)

• 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
• Shortcuts to adiabaticity: concepts, methods, and applications
• Robots that can adapt like animals
• Time-dependent variational principle for quantum lattices
• Unifying time evolution and optimization with matrix product states
• Defining and detecting quantum speedup
• Tensor networks for complex quantum systems
• Strong disorder RG approach of random systems
• Lecture Notes of Tensor Network Contractions
• Structural defects in ion crystals by quenching the external potential: the inhomogeneous Kibble-Zurek mechanism
• Two-Dimensional Tensor Product Variational Formulation
• A Cluster Monte Carlo Algorithm for 2-Dimensional Spin Glasses
• Adiabatic quantum dynamics of a random Ising chain across its quantum critical point
• Symmetry Breaking with a Slant: Topological Defects after an Inhomogeneous Quench
• Low-temperature behavior of two-dimensional Gaussian Ising spin glasses
• Unifying Projected Entangled Pair States contractions
• Causality in Condensates: Grey Solitons as Remnants of BEC Formation
• On Phase Ordering Behind the Propagating Front of a Second-Order Transition
• Simple universal models capture all classical spin physics
• Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
• Dynamics of a quantum phase transition in the random Ising model
• Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
• Focus on Shortcuts to Adiabaticity
• Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
• Dynamics of an inhomogeneous quantum phase transition
• Inhomogeneous Kibble-Zurek mechanism: vortex nucleation during Bose-Einstein condensation
• Quantum annealing of the $p$-spin model under inhomogeneous transverse field driving
• Tropical Tensor Network for Ground States of Spin Glasses
• Critical quench dynamics in confined systems
• Universal dynamics of inhomogeneous quantum phase transitions: suppressing defect formation
• Large-Scale, Low-Energy Excitations in the Two-Dimensional Ising Spin Glass
• Tensor Network Contractions for #SAT
• Fast counting with tensor networks
• Domain-wall excitations in the two-dimensional Ising spin glass
• Fast preparation of critical ground states using superluminal fronts
• Inhomogeneous quasi-adiabatic driving of quantum critical dynamics in weakly disordered spin chains
• Adiabatic dynamics of an inhomogeneous quantum phase transition: the case of z > 1 dynamical exponent
• Approximate optimization, sampling and spin-glass droplets discovery with tensor networks
• Quantum phase transition with inhomogeneous driving in the Lechner-Hauke-Zoller model
• Fair sampling of ground-state configurations of binary optimization problems
• Estimating the Density of States of Frustrated Spin Systems
• Engineering non-equilibrium quantum phase transitions via causally gapped Hamiltonians
• Inhomogeneity induced shortcut to adiabaticity in Ising chains with long-range interactions

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