Quantum computational phase transition in combinatorial problems

This paper investigates the empirical advantages of the Quantum Approximate Optimization Algorithm (QAOA) by identifying a computational phase transition when solving hard problems like SAT. The authors connect this transition to QAOA circuit controllability and complexity, showing that the quantum critical problem density deviates from the classical SAT-UNSAT phase transition. They demonstrate that the high problem density region, while limiting QAOA's performance in terms of reachability deficits, offers a quantum advantage over classical approximate algorithms due to a slower decay of the approximation ratio with problem density.

Bingzhi Zhang, Akira Sone, Quntao Zhuang