Title: Succinct Arguments for BatchQMA and Friends under 8 rounds
Abstract: We study the problem of minimizing round complexity in the context of succinct classical argument systems for quantum computation. All prior works either require at least 8 rounds of interaction between the quantum prover
and classical verifier, or rely on the idealized quantum random oracle model (QROM). We design:
1. A 4-round public-coin (except for the first message) argument system for batchQMA languages. Under the post-quantum hardness of functional encryption and learn- ing with errors (LWE), we achieve optimal communication complex-
ity (i.e., all messages sizes are independent of batch size). If we only rely on the post-quantum hardness of LWE, then we can make all messages except the verifierâs first message to be independent of the batch size.
2. A 6-round private-coin argument system for monotone policy batchQMA languages, under the post-quantum hardness of LWE. The communication complexity is independent of the batch size as well as the monotone circuit size.
Unlike all prior works, we do not rely on âstate-preservingâ succinct arguments of knowledge (AoKs) for NP for proving soundness. Our main technical contribution is a new approach to prove soundness without rewinding cheating
provers. We bring the notion of straight-line partial extractability to argument systems for quantum computation.
![[Computer Systems Lab]](http://www.cs.wisc.edu/pics/csl_logo.gif){kind=logo}