The theoretical discovery of quantum search algorithms demonstrated that quantum computers could significantly outperform classical ones. For example, the quantum Grover algorithm can find a marked item in a completely unordered list -- the proverbial needle in a haystack -- provably faster than any classical algorithm. Practical search problems, however, typically have more structure than existing quantum algorithms exploit. It is an outstanding open question exactly where speed ups can be found, and where they will be unachievable. This research aims to address these questions by drawing inspiration from the physics of disordered systems, where there are many known structural mechanisms which produce slow, or 'glassy', dynamics. The project further aims to elucidate the physical consequences of one of the most dramatic quantum mechanisms for slow dynamics: many-body localization (MBL). Although first postulated over 50 years ago, this mechanism has only recently come into sharp theoretical and experimental focus as large-scale isolated quantum systems such as ultracold atoms, ion traps, and superconducting qubit arrays have been built. It is particularly intriguing as localization prevents the emergence of classical behavior. From an quantum algorithmic point of view, the role localization plays is thus unclear. On the one hand, it leads to very slow dynamics and presumably very slow search behavior. On the other hand, one can only hope to achieve quantum mechanical speed ups in systems which do not behave classically! This suggests that one needs localization to obtain such speed ups. Whether this is true and, if so, how to exploit it are crucial open questions.
Thus, this CAREER award supports theoretical research and educational activities on two interrelated foci: 1) the computational complexity, typical structure and algorithmic approaches to quantum optimization problems; and, 2) the phenomenology of many-body localization (MBL) and its role in quantum computation and glassy dynamics. Theoretical methods include the cavity method, random matrix theory, large-N and many-body perturbation theory while numerical approaches include quantum Monte Carlo, the density matrix renormalization group and large scale diagonalization. Specifically, the PI proposes to investigate the phase diagram and transitions, geometrization and clustering of the configuration space in quantum satisfiability and related classical constraint satisfaction problems. The PI expects this study to aid the development of heuristic quantum algorithms for approximate optimization and landscape exploration. Many-body localization (MBL) constitutes a fundamental breakdown of quantum statistical mechanics in the presence of quenched disorder and protects quantum coherence out of equilibrium. The project addresses foundational questions about the theory of the delocalization transition and the influence of disorder versus quasiperiodic modulation, dimensionality and the range of interactions on localization. It also seeks to apply these ideas to understanding the behavior of quantum annealing applied to NP-hard optimization problems.
This project is jointly funded by the Quantum Information Science (QIS) Program in the Physics Division in the Mathematical and Physical Sciences Directorate, the Condensed Matter and Materials Theory (CMMT) Program in the Division of Materials Research in the Mathematical and Physical Sciences Directorate, and the Algorithmic Foundations (AF) Program in the Computing and Communications Foundations Division in the Computer and Information Science and Engineering Directorate.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
