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$.


翻译:QAOA似乎只能够解决优化问题,因此,QAOA不能看到2SAT等简单问题与3SAT等棘手问题之间的差别 -- -- 虽然2SAT是多米时间(P)级的,但其优化版也是非决定性的多球时间(NP)硬(NP)。在本文中,我们显示民俗是不真实的。当解决3SAT的变种时,我们在QAOA中发现一个计算阶段的过渡 -- -- 梯度和成功概率在众所周知的SAT-UNSAT阶段过渡阶段达到最低。相反,对于2SAT来说,这种现象在SAT-UNSAT阶段的过渡中并不存在,成功概率是合理电路深度的统一。在解决NP-硬化的SAT版本时,我们发现在QAAAA中,在相当浅的P=4的质深P=10美元(美元)的典型算法上,有定量优势。

0
下载
关闭预览

相关内容

专知会员服务
141+阅读 · 2021年3月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
灾难性遗忘问题新视角:迁移-干扰平衡
CreateAMind
17+阅读 · 2019年7月6日
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2021年11月17日
Arxiv
7+阅读 · 2020年6月29日
Arxiv
6+阅读 · 2018年4月24日
VIP会员
相关资讯
灾难性遗忘问题新视角:迁移-干扰平衡
CreateAMind
17+阅读 · 2019年7月6日
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员