Pith. sign in

REVIEW 1 cited by

Quantum vs Classical Proofs and Subset Verification

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

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

arxiv 1510.06750 v2 pith:OABSN4FQ submitted 2015-10-22 quant-ph cs.CC

Bill Fefferman , Shelby Kimmel This is my paper · ORCID
classification quant-phcs.CC
keywords oracleclassicalframeworkproveqcmaquantumgivenproperties
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. MicroCrypt Assumptions with Quantum Input Sampling and Pseudodeterminism: Constructions and Separations

    quant-ph 2025-05 conditional novelty 7.0 of 10

    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.

Pith tools