Leo Zhou

The Quantum Approximate Optimization Algorithm (QAOA) is a general purpose quantum algorithm designed for combinatorial optimization. We analyze its expected performance and prove concentration properties at any constant level (number of layers) on ensembles of random combinatorial optimization problems in the infinite size limit. These ensembles include mixed spin models and Max-q-XORSAT on sparse random hypergraphs. Our analysis can be understood via a saddle-point approximation of a sum-over-paths integral. This is made rigorous by proving a generalization of the multinomial theorem, which is a technical result of independent interest. We then show that the performance of the QAOA at constant levels for the pure q-spin model matches asymptotically the ones for Max-q-XORSAT on random sparse Erdos-Renyi hypergraphs and every large-girth regular hypergraph. Through this correspondence, we establish that the average-case value produced by the QAOA at constant levels is bounded away from optimality for pure q-spin models when q >= 4 and is even. This limitation gives a hardness of approximation result for quantum algorithms in a new regime where the whole graph is seen.

Abstract The Quantum Approximate Optimization Algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization problems whose performance can only improve with the number of layers p. While QAOA holds promise as an algorithm that can be run on near-term quantum computers, its computational power has not been fully explored. In this work, we study the QAOA applied to the Sherrington-Kirkpatrick (SK) model, which can be understood as energy minimization of n spins with all-to-all random signed couplings. There is a recent classical algorithm by Montanari that, assuming a widely believed conjecture, can be tailored to efficiently find an approximate solution for a typical instance of the SK model to within (1-epsilon) times the ground state energy. We can only hope to match its performance with the QAOA. Our main result is a novel technique that allows us to evaluate the typical-instance energy of the QAOA applied to the SK model. We produce a formula for the expected value of the energy, as a function of the 2p QAOA parameters, in the infinite size limit that can be evaluated on a computer with O(16^p) complexity. We evaluate the formula up to p=12, and find that the QAOA at p=11 outperforms the standard semidefinite programming algorithm. Moreover, we show concentration: With probability tending to one as n goes to infinity, measurements of the QAOA will produce strings whose energies concentrate at our calculated value. As an algorithm running on a quantum computer, there is no need to search for optimal parameters on an instance-by-instance basis since we can determine them in advance. What we have here is a new framework for analyzing the QAOA, and our techniques can be of broad interest for evaluating its performance on more general problems where classical algorithms may fail.

Abstract A universal family of Hamiltonians can be used to simulate any local Hamiltonian by encoding its full spectrum as the low-energy subspace of a Hamiltonian from the family. Many spin-lattice model Hamiltonians---such as Heisenberg or XY interaction on the 2D square lattice---are known to be universal. However, the known encodings can be very inefficient, requiring interaction strengths that scales exponentially with system size if the original Hamiltonian have complex, possibly all-to-all connectivity. In this work, we provide an efficient construction by which these universal families are in fact ``strongly'' universal; this means that the required interaction strengths as well as all other resources scale polynomially, regardless of the connectivity of the original Hamiltonian. This exponential improvement over previous constructions based on perturbative gadgets is achieved by combining the tools of quantum phase-estimation algorithm and circuit-to-Hamiltonian transformation in a non-perturbative way that only incurs polynomial overhead. Furthermore, we show that 1D Hamiltonians with nearest-neighbor interaction of 8-dimensional particles on a line are also strongly universal Hamiltonian simulators. Our results demonstrate that analog quantum simulation of general Hamiltonians can be made efficient for all target local Hamiltonians; this has potential application for future quantum technologies.