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

arXiv: https://arxiv.org/abs/1706.08470 · HTML: https://mlsanity.com/paper/1706.08470/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2017.

## Built on by (most cited first, 8 of 8)

- [Learning through atypical "phase transitions" in overparameterized neural networks](https://mlsanity.com/paper/2110.00683/) (2021)
- [On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks](https://mlsanity.com/paper/2209.14501/) (2022)
- [Quantum HyperNetworks: Training Binary Neural Networks in Quantum Superposition](https://mlsanity.com/paper/2301.08292/) (2023)
- [Quantum Approximate Optimization Algorithm applied to the binary perceptron](https://mlsanity.com/paper/2112.10219/) (2021)
- [The effect of priors on Learning with Restricted Boltzmann Machines](https://mlsanity.com/paper/2412.02623/) (2024)
- [Assessment of image generation by quantum annealer](https://mlsanity.com/paper/2103.08373/) (2021)
- [The Copycat Perceptron: Smashing Barriers Through Collective Learning](https://mlsanity.com/paper/2308.03743/) (2023)
- [Minibatch training of neural network ensembles via trajectory sampling](https://mlsanity.com/paper/2306.13442/) (2023)

## Abstract (arXiv)

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.