Efficiency of quantum versus classical annealing in non-convex learning problems
This addresses the problem of slow optimization in non-convex learning for researchers and practitioners, though it appears incremental as it builds on known quantum annealing concepts.
The paper tackled the challenge of identifying non-convex optimization problems where quantum annealing is efficient while classical thermal annealing fails, showing that for a wide class of machine learning problems, quantum annealing converges efficiently to optimal solutions while classical methods suffer exponential slowdown.
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.