Efficiency of quantum vs. classical annealing in nonconvex learning problems
Abstract
Quantum annealers are physical quantum devices designed to solve optimization problems by finding low-energy configurations of an appropriate energy function by exploiting cooperative tunneling effects to escape local minima. Classical annealers use thermal fluctuations for the same computational purpose, and Markov chains based on this principle are among the most widespread optimization techniques. The fundamental mechanism underlying quantum annealing consists of exploiting a controllable quantum perturbation to generate tunneling processes. The computational potentialities of quantum annealers are still under debate, since few ad hoc positive results are known. Here, we identify a wide class of large-scale nonconvex optimization problems for which quantum annealing is efficient while classical annealing gets stuck. These problems are of central interest to machine learning.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jan 30, 2018
- Source ID
- 10.1073/pnas.1711456115
Entities
People
- Carlo Baldassi
- Riccardo Zecchina
Organizations
- Bocconi University
- International Centre for Theoretical Physics
- Istituto Nazionale di Fisica Nucleare
- Office of Naval Research