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.
翻译:Qantum Apject Apractimization 算法(QAOA)旨在寻找短期量子计算机离散优化问题的近似解决办法。由于QAOA无法为QAOA提供算法保障,使其优于古典计算机,而没有证明$BP\neq NP$的证明,有必要调查QAOA的经验优势。我们确定QAOA在解决SAT等难题时的计算阶段过渡阶段 -- -- 随机事例在关键问题密度方面最难培训。我们把转换与QAOA电路的可控性和复杂性联系起来。此外,我们发现,由于QAOA的临界问题密度总体上不同于SAT-UNSAT阶段的过渡,而典型算法最难的则是这种过渡。然后,我们表明,高问题密度地区限制了QAOA在硬优化问题中的性能(~可达性赤字 }),实际上是一个利用QAAAA的好地方:与问题密度相比,其近似比率的衰败得慢得多,与QA的近似性算法是这个区域。