计算机科学 > 计算复杂性
[提交于 2025年7月4日
]
标题: 量子计算中的相关测量:对复杂性景观的影响
标题: Quantum Computation with Correlated Measurements: Implications for the Complexity Landscape
摘要: 2004年,Aaronson引入了复杂度类$\mathsf{PostBQP}$($\mathsf{BQP}$带有后选择)并证明它等于$\mathsf{PP}$。 在本文中,我们定义了一个新的复杂度类,$\mathsf{CorrBQP}$,它是$\mathsf{BQP}$的一种修改,具有执行相关测量的能力,即在寄存器的划分上输出相同值的测量。 我们证明$\mathsf{CorrBQP}$完全等于$\mathsf{BPP}^{\mathsf{PP}}$,使其“略高于”$\mathsf{PP}$。 事实上,我们证明了其他形而上学的修改,如$\mathsf{BQP}$,例如$\mathsf{CBQP}$(即具有克隆任意量子态能力的$\mathsf{BQP}$),也等于$\mathsf{BPP}^{\mathsf{PP}}$。 此外,我们证明了 $\mathsf{CorrBQP}$对经典查询是自低的。 相比之下,如果它在量子查询下是自低的,计数层次结构 ($\mathsf{CH}$) 将会坍缩到 $\mathsf{BPP}^{\mathsf{PP}}$。 最后,我们引入了一个有理次数的变体,该变体下界给出了 $\mathsf{BPP}^{\mathsf{PP}}$的查询复杂度。
文献和引用工具
与本文相关的代码,数据和媒体
alphaXiv (什么是 alphaXiv?)
CatalyzeX 代码查找器 (什么是 CatalyzeX?)
DagsHub (什么是 DagsHub?)
Gotit.pub (什么是 GotitPub?)
Hugging Face (什么是 Huggingface?)
带有代码的论文 (什么是带有代码的论文?)
ScienceCast (什么是 ScienceCast?)
演示
推荐器和搜索工具
arXivLabs:与社区合作伙伴的实验项目
arXivLabs 是一个框架,允许合作伙伴直接在我们的网站上开发和分享新的 arXiv 特性。
与 arXivLabs 合作的个人和组织都接受了我们的价值观,即开放、社区、卓越和用户数据隐私。arXiv 承诺这些价值观,并且只与遵守这些价值观的合作伙伴合作。
有一个为 arXiv 社区增加价值的项目想法吗? 了解更多关于 arXivLabs 的信息.