Quantum Computational Phase Transition in Combinatorial Problems

Understand

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.