Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems

Jernej Rudi Finžgar, Martin Leib, Elisabeth Wybo

Montanaro and Zhou proved that depth-one Quantum Approximate Optimization Algorithm (QAOA) finds the planted solution of certain near-symmetric constraint satisfaction problems wit…