Quantum Depth in the Random Oracle Model
Quantum Depth in the Random Oracle Model
复制标题
随机预言模型中的量子深度
DOI：
10.1145/3564246.3585153
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Waldner, Hendrik
中科院分区：
文献类型：
--
作者：
Arora, Atul Singh;Coladangelo, Andrea;Coudron, Matthew;Gheorghiu, Alexandru;Singh, Uttam;Waldner, Hendrik
结合经典计算，对浅层量子电路的计算能力进行了全面的刻画。具体地说，对于一类搜索问题，我们证明了相对于随机预言，下列语句成立：(A)BPPQNCBPP≠BQP。这驳斥了Jozsa在随机预言模型中的猜想。结果，这通过用密码散列函数替换先知，在类之间提供了第一个可实例化的分离，产生了解决Aaronson在量子计算中的十个半宏大挑战之一的解决方案。(B)BPPQNC⊈QNCBPAND QNCBPP⊈BPPQNC。这表明经典计算和浅层量子计算之间存在着微妙的相互作用。事实上，对于第二种分离，我们证明，对于某些问题，在单个浅量子电路中执行自适应测量的能力比在没有自适应测量的情况下执行多项式多项式浅量子电路的能力更有用。我们还证明了BPPQNCare和BPPQNCare都严格包含在BPPQNCBPP中。(C)存在量子深度协议的两消息证明。这样的协议允许经典验证者有效地证明证明者必须执行某个最小量子深度的计算。我们的量子深度证明可以用Yamakawa和Zhandry最近的量子构造的证明来实例化。
We give a comprehensive characterisation of the computational power of shallow quantum circuits combined with classical computation. Specifically, for classes of search problems, we show that the following statements hold, relative to a random oracle:(a)BPPQNCBPP≠BQP. This refutes Jozsa’s conjecture in the random oracle model. As a result, this gives the first instantiatable separation between the classes by replacing the oracle with a cryptographic hash function, yielding a resolution to one of Aaronson’s ten semi-grand challenges in quantum computing.(b)BPPQNC⊈QNCBPPandQNCBPP⊈BPPQNC. This shows that there is a subtle interplay between classical computation and shallow quantum computation. In fact, for the second separation, we establish that, for some problems, the ability to perform adaptive measurements in a single shallow quantum circuit, is more useful than the ability to perform polynomially many shallow quantum circuits without adaptive measurements. We also show thatBPPQNCandBPPQNCare both strictly contained inBPPQNCBPP.(c) There exists a 2-message proof of quantum depth protocol. Such a protocol allows a classical verifier to efficiently certify that a prover must be performing a computation of some minimum quantum depth. Our proof of quantum depth can be instantiated using the recent proof of quantumness construction by Yamakawa and Zhandry.
登录
查看更多内容
相对于随机预言的电路深度
影响因子：
0.5
作者：
Peter Bro Miltersen
通讯作者：
Peter Bro Miltersen
关于后量子世界中顺序工作证明的安全性
DOI：
10.4230/lipics.itc.2021.22
发表时间：
2021
期刊：
2nd Conference on Information-Theoretic Cryptography (ITC 2021
影响因子：
--
作者：
Blocki, J;Lee, S;Zhou, S.
通讯作者：
Zhou, S.
DOI：
10.1007/978-3-030-26951-7_9
发表时间：
2019-08
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Mark Zhandry
通讯作者：
Mark Zhandry
无需结构即可验证的量子优势
DOI：
--
发表时间：
2022
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Takashi Yamakawa;Mark Zhandry
通讯作者：
Mark Zhandry
关于压缩预言机技术和顺序工作证明的后量子安全性
DOI：
--
发表时间：
2020
期刊：
IACR Cryptology ePrint Archive
影响因子：
--
作者：
Kai;S. Fehr;Yu;Tai
通讯作者：
Tai