Many-body localization enables iterative quantum optimization

Hanteng Wang, Hsiu-Chung Yeh, Alex Kamenev

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


Many discrete optimization problems are exponentially hard due to the underlying glassy landscape. This means that the optimization cost exhibits multiple local minima separated by an extensive number of switched discrete variables. Quantum computation was coined to overcome this predicament, but so far had only a limited progress. Here we suggest a quantum approximate optimization algorithm which is based on a repetitive cycling around the tricritical point of the many-body localization (MBL) transition. Each cycle includes quantum melting of the glassy state through a first order transition with a subsequent reentrance through the second order MBL transition. Keeping the reentrance path sufficiently close to the tricritical point separating the first and second order transitions, allows one to systematically improve optimization outcomes. The running time of this algorithm scales algebraically with the system size and the required precision. The corresponding exponents are related to critical indexes of the continuous MBL transition.

Original languageEnglish (US)
Article number5503
JournalNature communications
Issue number1
StatePublished - Dec 2022

Bibliographical note

Funding Information:
This work was supported by the NSF grant DMR-2037654. We are grateful to Vadim Smelyanskiy for the valuable discussions.

Publisher Copyright:
© 2022, The Author(s).


Dive into the research topics of 'Many-body localization enables iterative quantum optimization'. Together they form a unique fingerprint.

Cite this