David Gamarnik

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.

We study the performance of Decoded Quantum Interferometry (DQI) on typical instances of MAX-k-XOR-SAT when the transpose of the constraint matrix is drawn from a standard ensemble of LDPC parity check matrices. We prove that if the decoding step of DQI corrects up to the best known efficient decoding threshold for LDPC codes, then DQI is obstructed by a topological feature of the near-optimal space of solutions known as the overlap gap property (OGP). As the OGP is widely conjectured to exactly characterize the asymptotic performance of state-of-the-art classical algorithms, this result suggests that DQI has no quantum advantage in optimizing unstructured MAX-k-XOR-SAT instances for large k without significant asymptotic advances in efficient LDPC decoders. We also give numerical evidence supporting this conjecture by showing that approximate message passing (AMP)—a classical algorithm conjectured to saturate the OGP threshold—outperforms DQI on a related ensemble of MAX-k-XOR-SAT instances. Finally, we prove that depth-1 QAOA outperforms DQI at sufficiently large k under the same decoding threshold assumption. Our result follows by showing that DQI is approximately Lipschitz under the quantum Wasserstein metric over many standard ensembles of codes. We then prove that MAX-k-XOR-SAT exhibits both an OGP and a related topological obstruction known as the chaos property; this is the first known OGP threshold for MAX-k-XOR-SAT at fixed k, which may be of independent interest. Finally, we prove that both of these topological properties inhibit approximately Lipschitz algorithms such as DQI from optimizing MAX-k-XOR-SAT to large approximation ratio with substantial probability.