Many-body localization enables iterative quantum optimization

Abstract

We suggest an iterative quantum protocol, allowing to solve optimization problems with a glassy energy landscape. It is based on a periodic cycling around the tricritical point of the many-body localization transition. This ensures that each iteration leads to a non-exponentially small probability to find a lower local energy minimum. The other key ingredient is to tailor the cycle parameters to a currently achieved optimal state (the "reference" state) and to reset them once a deeper minimum is found. We show that, if the position of the tricritical point is known, the algorithm allows to approach the absolute minimum with any given precision in a polynomial time.

arXiv comment7 pages, 5 figures

References in corpus (39)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Metal-insulator transition in a weakly interacting many-electron system with localized single-particle states
• Localization of interacting fermions at high temperature
• Adiabatic Quantum Computing
• The many-body localization phase transition
• Interacting electrons in disordered wires: Anderson localization and low-temperature transport
• Quasiparticle Lifetime in a Finite System: A Non--Perturbative Approach
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Observation of topological phenomena in a programmable lattice of 1,800 qubits
• Anderson localization casts clouds over adiabatic quantum optimization
• Many-body mobility edge in a mean-field quantum spin glass
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• First Order Quantum Phase Transition in Adiabatic Quantum Computation
• From Anderson localization on Random Regular Graphs to Many-Body localization
• Simple Glass Models and their Quantum Annealing
• Reverse annealing for the fully connected $p$-spin model
• Modernizing Quantum Annealing using Local Searches
• Dynamics of reverse annealing for the fully-connected $p$-spin model
• The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
• Reverse quantum annealing of the $p$-spin model with relaxation
• Multiparticle Landau-Zener problem
• Clustering of non-ergodic eigenstates in quantum spin glasses
• Quantum speedup of branch-and-bound algorithms
• Solvable multistate model of Landau-Zener transitions in cavity QED
• Fock-space anatomy of eigenstates across the many-body localisation transition
• Numerical study of metastable states in Ising spin glasses
• Many-body delocalization transition and relaxation in a quantum dot
• Complexity of the Sherrington-Kirkpatrick Model in the Annealed Approximation
• Stability of the quantum Sherrington-Kirkpatrick spin glass model
• Collective excitations and marginal stability of quantum Ising spin glasses
• Quantum ergodicity in the many-body localization problem
• Many body localization-delocalization transition in quantum Sherrington-Kirkpatrick model
• Scrambling and Many-Body Localization in the XXZ-Chain
• Speedup of the Quantum Adiabatic Algorithm using Delocalization Catalysis
• Effects of low-lying excitations on ground-state energy and energy gap of Sherrington-Kirkpatrick model in transverse field

Cited by in corpus (13)

• Mean-Field Approximate Optimization Algorithm
• Cyclic Quantum Annealing: Searching for Deep Low-Energy States in 5000-Qubit Spin Glass
• Tricritical Kibble-Zurek scaling in Rydberg atom ladders
• Continuous-time quantum optimisation without the adiabatic principle
• Adiabatic Bottlenecks in Quantum Annealing and Nonequilibrium Dynamics of Paramagnons
• Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer
• Boosting entanglement growth of many-body localization by superpositions of disorder
• Quantum Annealing with chaotic driver Hamiltonians
• Quantum Hopfield Model with Dilute Memories
• Learning-Driven Annealing with Adaptive Hamiltonian Modification for Solving Large-Scale Problems on Quantum Devices
• Random displacements in critical Rydberg atom arrays
• Quantum-inspired dynamical models on quantum and classical annealers
• Quantum sequel of neural network training