## New Research In

### Physical Sciences

### Social Sciences

#### Featured Portals

#### Articles by Topic

### Biological Sciences

#### Featured Portals

#### Articles by Topic

- Agricultural Sciences
- Anthropology
- Applied Biological Sciences
- Biochemistry
- Biophysics and Computational Biology
- Cell Biology
- Developmental Biology
- Ecology
- Environmental Sciences
- Evolution
- Genetics
- Immunology and Inflammation
- Medical Sciences
- Microbiology
- Neuroscience
- Pharmacology
- Physiology
- Plant Biology
- Population Biology
- Psychological and Cognitive Sciences
- Sustainability Science
- Systems Biology

# Efficiency of quantum vs. classical annealing in nonconvex learning problems

Edited by William Bialek, Princeton University, Princeton, NJ, and approved January 2, 2018 (received for review June 26, 2017)

## Significance

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.

## Abstract

Quantum annealers aim at solving nonconvex optimization problems by exploiting cooperative tunneling effects to escape local minima. The underlying idea consists of 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 nonconvex 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 are dominated by local minima that cause exponential slowdown of classical thermal annealers while simulated quantum annealing converges efficiently to rare dense regions of optimal solutions.

## Footnotes

↵

^{1}C.B. and R.Z. contributed equally to this work.- ↵
^{2}To whom correspondence may be addressed. Email: carlo.baldassi{at}unibocconi.it or riccardo.zecchina{at}unibocconi.it.

Author contributions: C.B. and R.Z. designed research, performed research, contributed new reagents/analytic tools, analyzed data, and wrote the paper.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission.

This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1711456115/-/DCSupplemental.

- Copyright © 2018 the Author(s). Published by PNAS.

This open access article is distributed under Creative Commons Attribution-NonCommercial-NoDerivatives License 4.0 (CC BY-NC-ND).

## References

- ↵
- Ray P,
- Chakrabarti BK,
- Chakrabarti A

- ↵
- ↵
- ↵
- Farhi E, et al.

- ↵
- ↵
- Moore C,
- Mertens S

- ↵
- Born M,
- Fock V

- ↵
- Landau L

- ↵
- ↵
- Altshuler B,
- Krovi H,
- Roland J

- ↵
- Bapst V,
- Foini L,
- Krzakala F,
- Semerjian G,
- Zamponi F

- ↵
- Santoro GE,
- Martoňák R,
- Tosatti E,
- Car R

- ↵
- Martoňák R,
- Santoro GE,
- Tosatti E

- ↵
- Heim B,
- Rønnow TF,
- Isakov SV,
- Troyer M

- ↵
- Rønnow TF, et al.

- ↵
- ↵
- ↵
- Langbein W, et al.

- ↵
- Baldassi C,
- Ingrosso A,
- Lucibello C,
- Saglietti L,
- Zecchina R

- ↵
- Baldassi C, et al.

- ↵
- Baldassi C,
- Ingrosso A,
- Lucibello C,
- Saglietti L,
- Zecchina R

- ↵
- Baldassi C,
- Gerace F,
- Lucibello C,
- Saglietti L,
- Zecchina R

- ↵
- Krauth W,
- Mézard M

- ↵
- ↵
- ↵
- Biroli G,
- Zamponi F

- ↵
- Hubara I,
- Courbariaux M,
- Soudry D,
- El-Yaniv R,
- Bengio Y

- ↵
- Courbariaux M,
- Bengio Y,
- David JP

- ↵
- MacKay DJ

- ↵
- ↵
- Aaronson S

- ↵
- ↵
- Huang H,
- Kabashima Y

- ↵
- Horner H

- ↵
- Bapst V,
- Semerjian G

- ↵
- Bapst V,
- Semerjian G

- ↵
- Baldassi C

- ↵
- Baldassi C,
- Braunstein A,
- Brunel N,
- Zecchina R

- ↵
- ↵
- Keskar NS,
- Mudigere D,
- Nocedal J,
- Smelyanskiy M,
- Tang PTP

- ↵
- Bottou L,
- Curtis FE,
- Nocedal J

- ↵
- ↵
- Baldassi C

- ↵
- Baldassi C,
- Braunstein A

- ↵
- Schneider BI,
- Guan X,
- Bartschat K

## Citation Manager Formats

## Sign up for Article Alerts

## Article Classifications

- Physical Sciences
- Computer Sciences