REVIEW 1 cited by
Quantum vs Classical Proofs and Subset Verification
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
We 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.
Forward citations
Cited by 1 Pith paper
-
MicroCrypt Assumptions with Quantum Input Sampling and Pseudodeterminism: Constructions and Separations
Quantum input sampling turns several MicroCrypt primitives into equivalent weak forms, and black-box separations show these forms are strictly weaker than uniform-sampling primitives.
Discussion (0). Continue with ORCID to comment.