Classical verifier can check quantum computation for a language beyond the polynomial hierarchy…
The claim
A classical polynomial-time verifier can verify arbitrary quantum computations for a language outside PH using a public-coin protocol with soundness ≤1/4, relative to a classical oracle
Published as: “Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy”
So what
Demonstrates that, in an oracle world, classical verification of exact quantum computation can exceed the power of the polynomial hierarchy, suggesting limits of relativizing techniques for proving impossibility of such verification.
The five-minute version
The paper constructs a classical oracle and a total unary language that can be decided exactly by a polynomial-time quantum algorithm but lies outside the polynomial hierarchy relative to that oracle, yet admits a public-coin interactive proof with a classical polynomial-time verifier and an efficient quantum honest prover, perfect completeness and soundness error ≤1/4 using at most log n/4 messages. The evidence is a rigorous oracle construction, a switching-lemma-style analysis, and a constant-depth circuit lower bound; the claims are proved relative to the oracle, not unconditionally.
What undercuts it the paper’s own results
- The verification result holds only relative to a constructed classical oracle, not in the unrelativized (real-world) setting.
Stated limits 2
- We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy.
- The oracle stores only the leaves of the recursive construction and does not answer queries that test a proposed internal secret.
What’s new here 4
- Shows a language outside PH (relative to an oracle) that still has a classical verifier with an efficient quantum prover, a first such result.
- Provides a public-coin protocol with perfect completeness and constant-fraction message complexity (≤log n/4).
- Proves a new switching theorem for correlated random restrictions arising from the recursive structure.
- Establishes matching lower bounds on the number of messages needed for any interactive proof of the language.
Artifacts & methods 7
- recursive Fourier sampling variantprimitive
- public-coin interactive proof systemsystem
- switching theorem for correlated restrictionstheory
- constant-depth circuit lower boundtheory
- oracle constructionevaluation
- exact quantum algorithm for secret recoverysystem
- noisy code table extensionsystem