  Quantum Approximate Optimization algorithm (QAOA) aims to search for
approximate solutions to discrete optimization problems with near-term quantum
computers. As there are no algorithmic guarantee possible for QAOA to
outperform classical computers, without a proof that $BQP\neq NP$, it is
necessary to investigate the empirical advantages of QAOA. We identify a
computational phase transition of QAOA when solving hard problems such as SAT
-- random instances are most difficult to train at a critical problem density.
We connect the transition to the controllability and the complexity of QAOA
circuits. Moreover, we find that the critical problem density in general
deviates from the SAT-UNSAT phase transition, where the hardest instances for
classical algorithm lies. Then, we show that the high problem density region,
which limits QAOA's performance in hard optimization problems ({\it
reachability deficits}), is actually a good place to utilize QAOA: its
approximation ratio has a much slower decay with the problem density, compared
to classical approximate algorithms. Indeed, it is exactly in this region that
quantum advantages of QAOA over classical approximate algorithms can be
identified.
