Paper 2026/390

Succinct Arguments for BatchQMA and Friends under 6 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 lan- guages. Our results come in two flavors: (a) Under the post-quantum hardness of functional encryption and learning with errors (LWE), we achieve optimal communication complexity (i.e., all message sizes are independent of batch size). (b) Under the post-quantum hardness of LWE, we achieve optimal communication com- plexity except for the verifier’s first message. 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. One of our main technical contributions is a new approach to prove soundness without rewind- ing cheating provers. We bring the notion of straight-line partial extractability to argument systems for quantum computation. All previous works crucially relied on rewinding cheating provers, thus needed “state-preserving” succinct arguments of knowledge (AoKs) for NP to prove soundness.

Note: This is the full version of the CRYPTO 2025 paper with a slightly different title -- Succinct Arguments for BatchQMA and Friends under 8 Rounds.