Efficiency of quantum versus classical annealing in non-convex learning problems
arXiv:1706.08470 · doi:10.1073/pnas.1711456115
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.
arXiv comment31 pages, 10 figures
References in corpus (27)
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing and Analog Quantum Computation
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Defining and detecting quantum speedup
- On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
- Anderson localization casts clouds over adiabatic quantum optimization
- Quantum versus Classical Annealing of Ising Spin Glasses
- Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
- Learning by message-passing in networks of discrete synapses
- The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
- Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
- Efficient supervised learning in networks with binary synapses
- Quantum fluctuations can promote or inhibit glass formation
- On quantum mean-field models and their quantum annealing
- Origin of the computational hardness for learning with binary synapses
- Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
- Generalization learning in a perceptron with binary synapses
- A solvable model of quantum random optimization problems
- Learning may need only a few bits of synaptic precision
- A Max-Sum algorithm for training discrete neural networks
- Thermal, quantum and simulated quantum annealing: analytical comparisons for simple models
- A tentative replica theory of glassy Helium 4
- 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-ProblemFree 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