Reproduce “Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Atul Mantri
The authors define a recursive oracle problem whose node value is selected by a hidden encoded address. An exact quantum algorithm recovers that address, while a classical verifier checks a prover’s claim through random recursive tests. For the constructed oracle and valid instances, the protocol has perfect completeness and soundness at most one quarter, yet no fixed level of the polynomial hierarchy decides the language.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.