Classical Verification of Quantum Computations with Efficient Verifier

Understand

In this paper, we extend the protocol of classical verification of quantum computations (CVQC) recently proposed by Mahadev to make the verification efficient.

• Our result is obtained in the following three steps: $\bullet$ We show that parallel repetition of Mahadev's protocol has negligible soundness error.
• This gives the first constant round CVQC protocol with negligible soundness error.
• In this part, we only assume the quantum hardness of the learning with error (LWE) problem similar to the Mahadev's work.