It is a long-standing open question to construct a classical oracle relative to which BQP/qpoly $\neq$ BQP/poly or QMA $\neq$ QCMA. In this paper, we construct classically-accessible classical oracles relative to which BQP/qpoly $\neq$ BQP/poly. Here, classically-accessible classical oracles are oracles that can be accessed only classically even for quantum algorithms. Based on a similar technique, we also show an alternative proof for separation of QMA and QCMA relative to a distributional quantumly-accessible classical oracles, which was recently shown by Natarajan and Nirkhe.

翻译：这是一个长期存在的开放问题，即构造相对于一个经典预言机而言BQP/qpoly $\neq$ BQP/poly或QMA $\neq$ QCMA 。在本文中，我们构造出了相对于经典预言机而言仅能在经典上访问的经典预言机，相对于它们，BQP/qpoly $\neq$ BQP/poly。其中，可在经典算法下被访问的经典预言机是指甚至对于量子算法也只能以经典方式访问的预言机。基于类似的技术，我们还展示了Natarajan和Nirkhe最近证明的一种基于分布式量子访问下的经典预言机的QMA和QCMA的分离的一种替代证明方法。