Complexity, Algorithms, and Applications of Programmable Quantum Many-Body Systems

Abstract

Advances in the programmability of quantum many-body systems have stimulated the development of novel computational and scientific applications. In this dissertation, we address a few fundamental and practical questions on using programmable quantum systems for analog quantum simulations and quantum optimization algorithms. We also design concrete experimental schemes to engineer the many-body dynamics that can be harnessed for these and other applications. On analog quantum simulations, we initiate the rigorous study of the physical resource complexity required to simulate a quantum Hamiltonian by another whose underlying interaction graph is simpler. In particular, we show a surprising result that unlike the classical setting, reducing the graph degree to a constant is impossible in general unless the interaction energy diverges with system size n. Instead, we develop a new construction where such degree-reduction becomes possible using O(poly(n)) interaction energy, which is exponentially better than what was known previously. On quantum optimization, we investigate the properties of a general-purpose Quantum Approximate Optimization Algorithm (QAOA). We develop a parameter-optimization procedure for the QAOA that is exponentially more efficient than standard strategies and reveal a mechanism of the algorithm to exploit non-adiabatic operations. We also analyze the typical-case performance of the QAOA on the Sherrington-Kirkpatrick spin glass problem and find that it can outperform the classical semi-definite programming algorithm. Lastly, we develop efficient and robust methods to experimentally implement many-body dynamics for algorithmic and physics applications. We design several experimental implementations based on neutral atoms with Rydberg interactions, which can be applied to quantum optimization algorithms, preparation of entangled many-body states, and engineering novel interactions between photons.