Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
The authors establish a theoretical separation between quantum and classical optimization by proving that the Mean-Field Approximate Optimization Algorithm (MF-AOA) fails to find near-optimal solutions on problems exhibiting the Overlap Gap Property (OGP). By mapping MF-AOA to finite-memory Approximate Message Passing (AMP) algorithms, they show this classical dequantization is fundamentally obstructed by clustered solution spaces. Numerical simulations on Max-4-XORSAT confirm that QAOA circumvents the OGP barrier where classical methods fail, marked by a non-differentiable transition from adiabatic to non-adiabatic schedules and super-polynomial depth scaling.
Classical quantum-inspired algorithms hit a hard barrier on clustered optimization landscapes, but true quantum circuits can push past it by abandoning adiabaticity.
In this paper, we prove that the Mean-Field Approximate Optimization Algorithm (MF-AOA), a quantum-inspired classical algorithm of the Quantum Approximate Optimization Algorithm (QAOA), is unable to give arbitrary near optimal solution for problems exhibiting the Overlap Gap Property (OGP). We show this by relating the MF-AOA to finite-memory Approximate Message Passing (AMP) algorithms, which are known to be limited in performance by the OGP. Thus, our paper argues that problems exhibiting the OGP are one such instance where the QAOA can outperform the MF-AOA and AMP algorithms in general. We supplement this by numerically simulating the performance of the QAOA on instances of Max-$4$-XORSAT that exhibit the OGP and find that the QAOA is able to surpass the barrier, while our finite-size scaling analysis favors a super-polynomial over a polynomial depth dependence. In addition, we observe a non-differentiable point in the performance of the QAOA near by the OGP barrier, where the optimal QAOA parameters change from an adiabatic to a non-adiabatic schedule.