Quantum computational phase transition in combinatorial problems
Quantum computational phase transition in combinatorial problems
复制标题
DOI：
10.1038/s41534-022-00596-2
复制
发表时间：
2021-09
影响因子：
7.6
通讯作者：
Bingzhi Zhang;A. Sone;Quntao Zhuang
中科院分区：
文献类型：
--
作者：
Bingzhi Zhang;A. Sone;Quntao Zhuang
量子近似优化算法（QAOA）旨在利用近期量子计算机搜索离散优化问题的近似解。由于没有算法保证QAOA能够优于经典计算机，在没有证明有界误差量子多项式时间（BQP）优于非确定性多项式时间（NP）的情况下，有必要研究QAOA的经验优势。我们确定QAOA的计算相变时，解决困难的问题，如SAT随机实例是最难在一个关键的问题密度训练。我们连接到QAOA电路的可控性和复杂性的过渡。此外，我们发现临界问题密度一般偏离SAT-UNSAT相变，经典算法的最难的情况下。然后，我们表明，高问题密度区域，这限制了QAOA的性能在硬优化问题（可达性赤字），实际上是一个很好的地方，利用QAOA：其近似比有一个慢得多的衰减与问题密度，相比，经典的近似算法。事实上，正是在这个区域，量子优势QAOA超过经典的近似算法可以确定。
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 bounded-error quantum polynomial time (BQP) ≠ nondeterministic polynomial time (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 algorithms lies. Then, we show that the high problem density region, which limits QAOA’s performance in hard optimization problems (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.