Classical verifier checks a beyond-PH quantum language via an oracle
Original title: Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy
The public-coin protocol has perfect completeness and soundness error at most 1/4, with near-optimal message count.
Relative to a classical oracle, the paper shows a classical polynomial-time verifier can check a language outside the polynomial hierarchy that quantum polynomial time decides exactly. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables, and the oracle stores only the leaves. A new switching theorem handles the correlated restrictions used in the proof.
Unconfirmed: The result is relative to an oracle, not an unconditional classical verifier.
- No computational assumptions are used beyond the chosen oracle.
- Message and query counts can match any unbounded polynomial-time bound.
- The quantum algorithm recovers every secret exactly.
- For tall instances, huge constant-depth circuits barely notice a flipped leaf.
From the original article
1 min read at arxiv.orgIt is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time.
By Atul Mantri · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.