Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy 待解读
新用户看这篇论文该怎么开始
- 先点「赞助解读」，AI 会把论文转成可直接执行的行动清单。
- 看完“可执行改进行动”后，可快速决定是否值得立项。
- 用上面的卡片内容直接发给团队，减少重复阅读。
摘要
It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size $2^{\mathrm{poly}(n)}$ changes its output with probability above $2^{-Ω(n)}$ when the answer of a random instance is flipped by changing a single leaf.
分析报告
暂无报告。点击“分析”开始生成。
个性化解读 与社区共享解读不同
用自己的话告诉 AI 你想要什么样的解读（比如"用大白话讲给非专业人士听"、"重点分析对我们团队 RAG 系统的可迁移性"），生成一份只属于你自己的版本；生成后也可以选择设为"愿意共享"，被更多人看到、点赞。