Pith. sign in

REVIEW 1 cited by

Toward Separating QMA from QCMA with a Classical Oracle

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 2411.01718 v1 pith:P76N2DJ6 submitted 2024-11-04 quant-ph cs.CC

Mark Zhandry This is my paper · ORCID
classification quant-phcs.CC
keywords quantumclassicalapproachclasscomplexityefficientgivenlanguages
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

QMA is the class of languages that can be decided by an efficient quantum verifier given a quantum witness, whereas QCMA is the class of such languages where the efficient quantum verifier only is given a classical witness. A challenging fundamental goal in quantum query complexity is to find a classical oracle separation for these classes. In this work, we offer a new approach towards proving such a separation that is qualitatively different than prior work, and show that our approach is sound assuming a natural statistical conjecture which may have other applications to quantum query complexity lower bounds.

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. QMA vs. QCMA and Pseudorandomness

    quant-ph 2024-11 conditional novelty 8.0 of 10

    Assuming a quantum pseudorandomness conjecture for dense permutation distributions, there exists a classical oracle relative to which QMA differs from QCMA.

Pith tools