# Quantum speedups in solving near-symmetric optimization problems by low-depth QAOA

arXiv: https://arxiv.org/abs/2411.04979 · HTML: https://mlsanity.com/paper/2411.04979/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Nov 2024.

## Built on by (most cited first, 1 of 1)

- [Generalized Probabilistic Approximate Optimization Algorithm](https://mlsanity.com/paper/2507.07420/) (2025)

## Abstract (arXiv)

We present new advances towards achieving exponential quantum speedups for solving optimization problems by low-depth quantum algorithms. Specifically, we focus on families of combinatorial optimization problems that exhibit symmetry and contain planted solutions. We rigorously prove that the 1-step Quantum Approximate Optimization Algorithm (QAOA) can achieve a success probability of Omega(1/√n), and sometimes Omega(1), for finding the exact solution in many cases. This allows us to prove a separation of O(1) quantum queries and Omega(n/log n) classical queries required to find the planted solution in the latter setting. Furthermore, we construct near-symmetric optimization problems by randomly sampling the individual clauses of symmetric problems, and prove that the QAOA maintains a strong success probability in this setting even when the symmetry is broken. Finally, we construct various families of near-symmetric Max-SAT problems and benchmark state-of-the-art classical solvers, discovering instances where all known general-purpose classical algorithms require exponential time. Therefore, our results indicate that low-depth QAOA may achieve an exponential quantum speedup for optimization problems.