Towards a quantum-inspired proof for IP = PSPACE
share
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 (IP) for PreciseBQP where the prover is only assumed to be a PreciseBQP machine, and show that the result can be strengthened to show an IP for NP^PP with a prover which is only assumed to be an NP^PP machine - which was not known before. We also show how the protocol can be used to directly verify 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 IP = PSPACE, as PreciseQMA captures the full PSPACE power.
READ FULL TEXT