Efficiency of quantum versus classical annealing in non-convex learning problems

Abstract

Quantum annealers aim at solving non-convex optimization problems by exploiting cooperative tunneling effects to escape local minima. The underlying idea consists in designing a classical energy function whose ground states are the sought optimal solutions of the original optimization problem and add a controllable quantum transverse field to generate tunneling processes. A key challenge is to identify classes of non-convex optimization problems for which quantum annealing remains efficient while thermal annealing fails. We show that this happens for a wide class of problems which are central to machine learning. Their energy landscapes is dominated by local minima that cause exponential slow down of classical thermal annealers while simulated quantum annealing converges efficiently to rare dense regions of optimal solutions.

31 pages, 10 figures

References in corpus (9)

• Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Efficient supervised learning in networks with binary synapses
• On quantum mean-field models and their quantum annealing
• Origin of the computational hardness for learning with binary synapses
• Generalization learning in a perceptron with binary synapses
• A solvable model of quantum random optimization problems
• A method to reduce the rejection rate in Monte Carlo Markov Chains

Cited by in corpus (26)

• Efficient partition of integer optimization problems with one-hot encoding
• Scalable Emulation of Sign-Problem$-$Free Hamiltonians with Room Temperature p-bits
• Benchmark test of Black-box optimization using D-Wave quantum annealer
• An Application of Quantum Annealing Computing to Seismic Inversion
• Learning through atypical "phase transitions" in overparameterized neural networks
• Supervised machine learning of ultracold atoms with speckle disorder
• On the role of synaptic stochasticity in training low-precision neural networks
• Possible Ergodic-nonergodic regions in the quantum Sherrington-Kirkpatrick spin glass model and quantum annealing
• Quantum Annealing for Neural Network optimization problems: a new approach via Tensor Network simulations
• Teacher-student learning for a binary perceptron with quantum fluctuations
• On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
• Quantum accelerated approach to the thermal state of classical spin systems with applications to pattern-retrieval in the Hopfield neural network
• On the dynamics of Simulated Quantum Annealing in random Ising chains
• Efficient quantum and simulated annealing of Potts models using a half-hot constraint
• Message-passing algorithm of quantum annealing with nonstoquastic Hamiltonian
• The effect of priors on Learning with Restricted Boltzmann Machines
• From quantum-enhanced to quantum-inspired Monte Carlo
• The Copycat Perceptron: Smashing Barriers Through Collective Learning
• Graph minor embedding can affect sampling degenerate ground states using quantum annealing
• Projective Embedding of Dynamical Systems: uniform mean field equations
• Intrinsic Geometric Vulnerability of High-Dimensional Artificial Intelligence
• Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
• Entanglement-assisted variational algorithm for discrete optimization problems
• Quantum simulations of complex systems
• Optimization of neural networks via finite-value quantum fluctuations
• Interacting Copies of Random Constraint Satisfaction Problems