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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi></mml:math> as <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>N</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>&amp;#x2212;</mml:mo><mml:mn>1</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msup></mml:math>. 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.