Towards a quantum-inspired proof for IP = PSPACE

Abstract

We explore quantum-inspired interactive proof systems where the prover is limited. Namely, we improve on a result by [AG17] showing a quantum-inspired interactive protocol ($\mathsf{IP}$) for $\mathsf{PreciseBQP}$ where the prover is only assumed to be a $\mathsf{PreciseBQP}$ machine, and show that the result can be strengthened to show an $\mathsf{IP}$ for $\mathsf{N}{\mathsf{P}}^{\mathsf{PP}}$ with a prover which is only assumed to be an $\mathsf{N}{\mathsf{P}}^{\mathsf{PP}}$ machine - which was not known before. We also show how the protocol can be used to directly verify $\mathsf{QMA}$ computations, thus connecting the sum-check protocol by [AAV13] with the result of [AG17, LFKN90]. Our results shed light on a quantum-inspired proof for $\mathsf{IP}=\mathsf{PSPACE}$, as $\mathsf{PreciseQMA}$ captures the full $\mathsf{PSPACE}$ power.

arXiv comment10 pages. Minor changes and corrections compared to v2

References in corpus (10)

• Unconditionally verifiable blind computation
• A Simple Proof that Toffoli and Hadamard are Quantum Universal
• Interactive Proofs For Quantum Computations
• Robust self-testing of many-qubit states
• Non-interactive classical verification of quantum computation
• Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
• Importance of the spectral gap in estimating ground-state energies
• Quantum soundness of the classical low individual degree test
• Quantum Merlin Arthur with Exponentially Small Gap
• Quantum generalizations of the polynomial hierarchy with applications to QMA(2)

Cited by in corpus (2)

• Importance of the spectral gap in estimating ground-state energies
• Information-theoretically-sound non-interactive classical verification of quantum computing with trusted center