We discuss the problem of finite-horizon dynamic programming (DP) on a quantum computer. We introduce a query model for studying quantum and classical algorithms for solving DP problems, and provide example oracle constructions for the travelling salesperson problem, the minimum set-cover problem, and the edit distance problem. We formulate open questions regarding quadratic quantum speedups for DP and discuss their implications. We then prove lower bounds for the query complexity of quantum algorithms and classical randomized algorithms for DP, and show that no greater-than-quadratic speedup can be achieved for solving DP problems.


翻译:我们在量子计算机上讨论量子计算机的有限等离子动态编程问题。 我们引入了用于研究量子算法和经典算法以解决DP问题的查询模式, 并为流动销售人员问题、 最小集覆盖问题和编辑距离问题提供示例神器结构。 我们为 DP 提出有关四面体量子加速的开放问题, 并讨论其影响。 然后, 我们证明量子算法和典型的DP 随机算法的查询复杂性的下限, 并表明在解决DP 问题时, 无法实现比二次体化更快的速度 。

0
下载
关闭预览

相关内容

【硬核书】Linux核心编程|Linux Kernel Programming,741页pdf
专知会员服务
78+阅读 · 2021年3月26日
【经典书】贝叶斯编程,378页pdf,Bayesian Programming
专知会员服务
244+阅读 · 2020年5月18日
强化学习最新教程,17页pdf
专知会员服务
171+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
187+阅读 · 2019年10月10日
《自然》(20190829出版)一周论文导读
科学网
6+阅读 · 2019年8月30日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
《科学》(20190426出版)一周论文导读
科学网
5+阅读 · 2019年4月27日
《自然》(20190221出版)一周论文导读
科学网
6+阅读 · 2019年2月23日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
【推荐】视频目标分割基础
机器学习研究会
9+阅读 · 2017年9月19日
Arxiv
0+阅读 · 2021年9月26日
Arxiv
0+阅读 · 2021年9月24日
VIP会员
相关资讯
《自然》(20190829出版)一周论文导读
科学网
6+阅读 · 2019年8月30日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
《科学》(20190426出版)一周论文导读
科学网
5+阅读 · 2019年4月27日
《自然》(20190221出版)一周论文导读
科学网
6+阅读 · 2019年2月23日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
【推荐】视频目标分割基础
机器学习研究会
9+阅读 · 2017年9月19日
Top
微信扫码咨询专知VIP会员