Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models

The parity mapping provides a geometrically local encoding of the Quantum Approximate Optimization Algorithm (QAOA), at the expense of having a quadratic qubit overhead for all-to-all connected problems. In this work, we benchmark the parity-encoded QAOA on spin-glass models. We address open questions in the scaling of this algorithm. In particular, we show that for fixed number of parity-encoded QAOA layers, the performance or the output energy, vanishes towards zero (the value achieved by random guessing) with problem size $N$ as $N^{-1\mathrm{/}2}$. Our results suggest that the parity-encoded QAOA does not have a promising scaling compared to the standard version of QAOA. We perform tensor-network calculations to confirm our results, and comment on the concentration of optimal QAOA parameters over problem instances.