Separating QMA from QCMA with a classical oracle
John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, and Mark Zhandry
我们构建了一个经典的神谕,证明在相对化的设置中,由具有量子见证(QMA)的高效量子验证器可决定的语言集严格大于那些只能访问经典见证(QCMA)的可决定语言。 我们构建的分离经典神谕是对于我们硬币光谱固有的一个决策问题 - 神谕描述了布尔超立方体的两个子集,计算任务是决定是否存在一个量子态,其标准基础测量分布在一个子集上得到了很好的支持,而其傅里叶基础测量分布在其他子集上得到了很好的支持。 这相当于估计通过成员资格查询可以访问的两个集合之间的“Forrelation”矩阵的光谱规范。 我们的下界源于一个简单的观察,即具有经典见证的查询算法可以多次运行,从分布中生成许多样本,而量子见证是“一次使用”的对象。 该观察结果使我们能够减少证明QCMA下界,以证明采样硬度结果不会同时证明QMA下限。 为了证明QCMA的采样硬度结果,我们观察到,通过用玻色子表达问题,可以压缩对神谕的量子访问 - 压缩神谕技术的新“第二次量化”视角,这可能是独立的兴趣。 利用这种对采样问题的压缩视角,我们证明了采样硬度结果,完成了证明。
We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decidable with access only to a classical witness (QCMA). The separating classical oracle we construct is for a decision problem we coin spectral Forrelation – the oracle describes two subsets of the boolean hypercube, and the computational task is to decide if there exists a quantum state whose standard...