We construct a quantum oracle relative to which $\mathsf{BQP} = \mathsf{QMA}$ but pseudorandom quantum states and pseudorandom unitary transformations exist, a counterintuitive result in light of the fact that pseudorandom states can be "broken" by quantum Merlin-Arthur adversaries. We explain how this nuance arises as the result of a distinction between algorithms that operate on quantum and classical inputs. On the other hand, we show that some computational assumption is likely needed to construct pseudorandom states, by proving that pseudorandom states do not exist if $\mathsf{BQP} = \mathsf{PP}$. We discuss implications of these results for cryptography, complexity theory, and quantum tomography.


翻译:我们构建了一个量子神器, 相对于它, $\ mathsf{BQP} =\ mathsf ⁇ ma} $, 但伪随机量子状态和伪随机单一变异存在, 反直觉的结果是, 伪随机状态可能会被量子Merlin- Arthur对手“ 撕碎 ” 。 我们解释这种细微现象是如何由量子和经典输入的算法之间的区别而产生的。 另一方面, 我们证明, 建立伪随机状态可能需要某种计算假设, 如果 $\ mathsf{BQP} =\ mathsf{PP} 美元, 伪随机状态并不存在。 我们讨论这些结果对加密、 复杂理论 和量子摄影的影响 。

0
下载
关闭预览

相关内容

最新《图理论》笔记书,98页pdf
专知会员服务
74+阅读 · 2020年12月27日
专知会员服务
84+阅读 · 2020年12月5日
【硬核书】群论,Group Theory,135页pdf
专知会员服务
125+阅读 · 2020年6月25日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
计算机 | ICDE 2020等国际会议信息8条
Call4Papers
3+阅读 · 2019年5月24日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
Arxiv
0+阅读 · 2021年5月11日
Arxiv
0+阅读 · 2021年5月8日
Arxiv
0+阅读 · 2021年5月8日
Arxiv
0+阅读 · 2021年5月6日
Arxiv
0+阅读 · 2021年5月5日
Arxiv
0+阅读 · 2021年5月4日
Arxiv
0+阅读 · 2021年5月4日
Arxiv
0+阅读 · 2021年5月3日
VIP会员
相关VIP内容
最新《图理论》笔记书,98页pdf
专知会员服务
74+阅读 · 2020年12月27日
专知会员服务
84+阅读 · 2020年12月5日
【硬核书】群论,Group Theory,135页pdf
专知会员服务
125+阅读 · 2020年6月25日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
计算机 | ICDE 2020等国际会议信息8条
Call4Papers
3+阅读 · 2019年5月24日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
相关论文
Arxiv
0+阅读 · 2021年5月11日
Arxiv
0+阅读 · 2021年5月8日
Arxiv
0+阅读 · 2021年5月8日
Arxiv
0+阅读 · 2021年5月6日
Arxiv
0+阅读 · 2021年5月5日
Arxiv
0+阅读 · 2021年5月4日
Arxiv
0+阅读 · 2021年5月4日
Arxiv
0+阅读 · 2021年5月3日
Top
微信扫码咨询专知VIP会员