Classical Verification of Quantum Computations – QIP 2019 Keynote

Is it possible for an efficient classical verifier (a BPP machine) to verify the output of an efficient quantum prover (a BQP machine)?

The answer is Yes. Researchers show that a classical polynomial time verifier (a BPP machine) can interact with an efficient quantum prover (a BQP machine) in order to verify BQP computations. They rely on the additional assumption that the verifier may use post-quantum cryptography that the BQP prover cannot break. They rely on quantum secure classical encryption schemes, such as those based on the learning with errors problem. These schemes can be used to encrypt classical bits (or quantum states) in a way in which an efficient quantum machine cannot extract any information.

This was the QIP 2019 Keynote subject. However, this is only presenting the Arxiv paper and two other late 2018 talks. It is answering questions about determining if a quantum computer has done something quantum and helping answering if Quantum supremacy has been achieved. Quantum supremacy is when quantum computers clearly beat regular computers.

The core of their construction is a measurement protocol, an interactive protocol between an efficient quantum prover and a classical verifier which is used to force the prover to behave as the verifier’s trusted measurement device. To formalize the idea of a measurement protocol, they now describe its completeness and soundness conditions, beginning with a small amount of necessary notation. In our measurement protocol, an honest prover constructs an n qubit quantum state ρ of his choice, and the verifier would like each qubit to be measured in either the standard basis or the Hadamard basis.

They use trapdoor function families. They are ideal families initially and then approximations of these function families are used.