Many-body localization enables iterative quantum optimization

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. There are several proposals for quantum algorithms solving optimisation problems, but so far none of them has provided a clear speedup. Here, the authors propose an iterative protocol featuring periodic cycling around the tricritical point of a many-body localization transition.