



01003nas a2200121   4500008004100000245005600041210005600097260001500153520063800168100002000806700001900826856003600845       2015                        eng d00aQuantum vs Classical Proofs and Subset Verification0 aQuantum vs Classical Proofs and Subset Verification  c2015/10/223 aWe study the ability of efficient quantum verifiers to decide properties of exponentially large subsets given either a classical or quantum witness. We develop a general framework that can be used to prove that QCMA machines, with only classical witnesses, cannot verify certain properties of subsets given implicitly via an oracle. We use this framework to prove an oracle separation between QCMA and QMA using an ``in-place'' permutation oracle, making the first progress on this question since Aaronson and Kuperberg in 2007. We also use the framework to prove a particularly simple standard oracle separation between QCMA and AM.1 aFefferman, Bill1 aKimmel, Shelby  uhttp://arxiv.org/abs/1510.06750