Computational phase transition in Quantum Approximate Optimization Algorithm -- the difference between hard and easy

Quantum Approximate Optimization algorithm (QAOA) is one of the candidates to achieve a near-term quantum advantage. As QAOA seems only capable of solving optimization problems, there is a folklore that QAOA cannot see the difference between easy problems such as 2-SAT and hard problems such as 3-SAT -- although 2-SAT is in the polynomial-time (P) class, its optimization version is also nondeterministic polynomial-time (NP)-hard. In this paper, we show that the folklore is not true. We find a computational phase transition in QAOA when solving a variant of 3-SAT -- the amplitude of gradient and the success probability achieve their minimum at the well-known SAT-UNSAT phase transition. On the contrary, for 2-SAT, such a phenomena is absent at SAT-UNSAT phase transition and the success probability is unity for a reasonable circuit depth. In solving the NP-hard optimization versions of SAT, we identify quantum advantages over a classical approximate algorithm at quite a shallow depth of p=4 for the problem size of $n=10$.