Efficiency of quantum vs. classical annealing in nonconvex learning problems

DOI10.1073/PNAS.1711456115MaRDI QIDQ4967423zbMATH OpenOpenAlexWikidataFDO

Authors Carlo Baldassi, Riccardo Zecchina

Publication date 3 July 2019

Published in Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1706.08470

Mathematics Subject Classification ID

Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Quantum equilibrium statistical mechanics (general) (82B10) Applications of design theory to circuits and networks (94C30)

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.

Recommendations

• Quantum annealing learning search for solving QUBO problems
• Convergence theorems for quantum annealing
• Quantum annealing and related optimization methods
• A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing
• Theory versus practice in annealing-based quantum computing
• Classical simulated annealing using quantum analogues
• Extended quantum annealing and quantum algorithms for optimization and thermodynamics of classical systems
• Optimization and quantum annealing
• scientific article; zbMATH DE number 5824031
• Quantum annealing of hard problems

Cited in

(5)

• Quantum annealing learning search for solving QUBO problems
• Projective embedding of dynamical systems: uniform mean field equations
• Quantum annealing for neural network optimization problems: a new approach via tensor network simulations
• The effect of priors on learning with restricted Boltzmann machines
• Finding the right path: statistical mechanics of connected solutions in constraint satisfaction problems

This page was built for publication: Efficiency of quantum vs. classical annealing in nonconvex learning problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4967423)