论文标题
关于非标准量子甲壳的力量
On the power of nonstandard quantum oracles
论文作者
论文摘要
我们研究设计甲骨文时的选择如何影响相对于此甲骨文定义的量子特性测试问题的复杂性。我们将常规图表编码为可逆函数$ f $，并在不同的甲骨文模型中呈现$ f $。我们首先给出一个单QMA协议，以测试是否在$ F $中编码的图有一个小的断开子集。然后，我们使用表示理论来表明，没有经典的证人可以帮助量子验证者有效地确定相对于就地的甲骨文。也许令人惊讶的是，对标准甲骨文的简单修改也可以防止量子验证者有效地确定此问题，即使可以访问无限的证人。
We study how the choices made when designing an oracle affect the complexity of quantum property testing problems defined relative to this oracle. We encode a regular graph of even degree as an invertible function $f$, and present $f$ in different oracle models. We first give a one-query QMA protocol to test if a graph encoded in $f$ has a small disconnected subset. We then use representation theory to show that no classical witness can help a quantum verifier efficiently decide this problem relative to an in-place oracle. Perhaps surprisingly, a simple modification to the standard oracle prevents a quantum verifier from efficiently deciding this problem, even with access to an unbounded witness.
