On Information-Theoretic Classical Verification of Quantum Computers

Abstract

Quantum inspired protocols e.g. [AAV13,AG17] attempt to achieve a single-prover interactive protocol where a classical machine can verify quantum computations in an information-theoretically secure manner. We define a family of protocols which seem natural for verifying quantum computations and generalizes such known protocols, namely those of [AAV13,AG17]. We show that any protocol from this family is bound to require an extremely powerful prover, much like the classical protocols of [LFKN92] and [Sha92]. Using our analysis, we also hint at possible ways one might try to realize a protocol where the prover can be weaker, namely a quantum computer (i.e. a BQP machine).

References in corpus (8)

• Unconditionally verifiable blind computation
• Post hoc verification with a single prover
• Post hoc verification of quantum computation
• Robust self-testing of many-qubit states
• Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
• Quantum soundness of the classical low individual degree test
• A Quantum inspired proof of $P^{\#P}\subseteq IP$
• Quantum Systems on Non-$k$-Hyperfinite Complexes: A Generalization of Classical Statistical Mechanics on Expander Graphs