skip to main content


Title: Many-body localization enables iterative quantum optimization
Abstract

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.

 
more » « less
Award ID(s):
2037654
PAR ID:
10373213
Author(s) / Creator(s):
; ;
Publisher / Repository:
Nature Publishing Group
Date Published:
Journal Name:
Nature Communications
Volume:
13
Issue:
1
ISSN:
2041-1723
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    The existence of quantum tricriticality and exotic phases are found in a tricritical Dicke triangle (TDT) where three cavities, each one containing an ensemble of three-level atoms, are connected to each other through the action of an artificial magnetic field. The conventional superradiant phase (SR) is connected to the normal phase through first- and second-order boundaries, with tricritical points located at the intersection of such boundaries. Apart from the SR phase, a chiral superradiant (CSR) phase is found by tuning the artificial magnetic field. This phase is characterized by a nonzero photon current and its boundary presents chiral tricritical points (CTCPs). Through the study of different critical exponents, we are able to differentiate the universality class of the CTCP and TCP from that of second-order critical points, as well as find distinctive critical behavior among the two different superradiant phases. The TDT can be implemented in various systems, including atoms in optical cavities as well as the circuit QED system, allowing the exploration of a great variety of critical manifolds.

     
    more » « less
  2. Abstract

    The absence of thermalization in certain isolated many-body systems is of great fundamental interest. Many-body localization (MBL) is a widely studied mechanism for thermalization to fail in strongly disordered quantum systems, but it is still not understood precisely how the range of interactions affects the dynamical behavior and the existence of MBL, especially in dimensionsD > 1. By investigating nonequilibrium dynamics in strongly disorderedD = 2 electron systems with power-law interactions ∝ 1/rαand poor coupling to a thermal bath, here we observe MBL-like, prethermal dynamics forα = 3. In contrast, forα = 1, the system thermalizes, although the dynamics is glassy. Our results provide important insights for theory, especially since we obtained them on systems that are much closer to the thermodynamic limit than synthetic quantum systems employed in previous studies of MBL. Thus, our work is a key step towards further studies of ergodicity breaking and quantum entanglement in real materials.

     
    more » « less
  3. Light-matter interacting systems involving multilevel atoms are appealing platforms for testing equilibrium and dynamical phenomena. Here we explore a tricritical Dicke model, where an ensemble of three-level systems interacts with a single light mode, through two different approaches: a generalized Holstein-Primakoff mapping and a treatment using the Gell-Mann matrices. Both methods are found to be equivalent in the thermodynamic limit. In equilibrium, the system exhibits a rich phase diagram where both continuous and discrete symmetries can be spontaneously broken. We characterize all the different types of symmetries according to their scaling behaviors. Far from the thermodynamic limit, considering just a few tens of atoms, the system already exhibits features that could help characterize both second- and first-order transitions in a potential experiment. Importantly, we show that the tricritical behavior is preserved when dissipation is taken into account. Moreover, the system develops a rich steady-state phase diagram with various regions of bistability, all of them converging at the tricritical point. Having multiple stable normal and superradiant phases opens prospective avenues for engineering interesting steady states by a proper choice of initial states and/or parameter quenching. 
    more » « less
  4. We study interacting fermions in one dimension subject to random, uncorrelated onsite disorder, a paradigmatic model of many‐body localization (MBL). This model realizes an interaction‐driven quantum phase transition between an ergodic and a many‐body localized phase, with the transition occurring in the many‐body eigenstates. We propose a single‐particle framework to characterize these phases by the eigenstates (the natural orbitals) and the eigenvalues (the occupation spectrum) of the one‐particle density matrix (OPDM) in individual many‐body eigenstates. As a main result, we find that the natural orbitals are localized in the MBL phase, but delocalized in the ergodic phase. This qualitative change in these single‐particle states is a many‐body effect, since without interactions the single‐particle energy eigenstates are all localized. The occupation spectrum in the ergodic phase is thermal in agreement with the eigenstate thermalization hypothesis, while in the MBL phase the occupations preserve a discontinuity at an emergent Fermi edge. This suggests that the MBL eigenstates are weakly dressed Slater determinants, with the eigenstates of the underlying Anderson problem as reference states. We discuss the statistical properties of the natural orbitals and of the occupation spectrum in the two phases and as the transition is approached. Our results are consistent with the existing picture of emergent integrability and localized integrals of motion, or quasiparticles, in the MBL phase. We emphasize the close analogy of the MBL phase to a zero‐temperature Fermi liquid: in the studied model, the MBL phase is adiabatically connected to the Anderson insulator and the occupation‐spectrum discontinuity directly indicates the presence of quasiparticles localized in real space. Finally, we show that the same picture emerges for interacting fermions in the presence of an experimentally‐relevant bichromatic lattice and thereby demonstrate that our findings are not limited to a specific model.image

     
    more » « less
  5. Abstract

    Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with near-term quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that bounded-error quantum polynomial time (BQP) ≠ nondeterministic polynomial time (NP), it is necessary to investigate the empirical advantages of QAOA. We identify a computational phase transition of QAOA when solving hard problems such as SAT—random instances are most difficult to train at a critical problem density. We connect the transition to the controllability and the complexity of QAOA circuits. Moreover, we find that the critical problem density in general deviates from the SAT-UNSAT phase transition, where the hardest instances for classical algorithms lies. Then, we show that the high problem density region, which limits QAOA’s performance in hard optimization problems (reachability deficits), is actually a good place to utilize QAOA: its approximation ratio has a much slower decay with the problem density, compared to classical approximate algorithms. Indeed, it is exactly in this region that quantum advantages of QAOA over classical approximate algorithms can be identified.

     
    more » « less