Impossibility of succinct quantum proofs for collision-freeness
Impossibility of succinct quantum proofs for collision-freeness
复制标题
不可能用简洁的量子证明来证明无碰撞性
DOI：
--
复制
发表时间：
2011
影响因子：
1
通讯作者：
S. Aaronson
中科院分区：
文献类型：
--
作者：
S. Aaronson
我们证明了任何决定函数f：[n] → [n]是置换还是远离置换的量子算法都必须对f进行Ω（n1/3/w）查询，即使该算法被给予支持f是置换的w-量子比特量子证据。这意味着存在着一个神谕A，这样SZKA就可以解释QMAA，回答了作者八年前的一个公开问题。事实上，我们表明，相对于一些甲骨文，SZK是不是在计数类A0 PP定义的Vyalyi。这个证明是碰撞问题的量子下限的一个相当简单的扩展。
We show that any quantum algorithm to decide whether a function f : [n] → [n] is a permutation or far from a permutation must make Ω (n1/3/w) queries to f, even if the algorithm is given a w-qubit quantum witness in support of f being a permutation. This implies that there exists an oracle A such that SZKA ⊄ QMAA, answering an eight-year-old open question of the author. Indeed, we show that relative to some oracle, SZK is not in the counting class A0PP defined by Vyalyi. The proof is a fairly simple extension of the quantum lower bound for the collision problem.