A. Nietner

Interactive proofs for verifying (quantum) learning and testing

It is proved that a resource-constrained learner cannot gain any advantage through classical interaction with an untrusted prover, and it is shown that for the vast majority of testing and learning problems, a memory-constrained quantum algorithm cannot overcome its limitations via classical communication with a memory...