On quantum interactive proofs with a laconic prover

Abstract

Interactive proof systems with a laconic prover, studied by Goldreich, Vadhan, and Wigderson (CC, 2002), capture problems verifiable with logarithmic prover communication in the classical setting. For two-message quantum analogs, even a single-bit prover response contains quantum statistical zero-knowledge ($\mathsf{QSZK}$), introduced by Watrous (FOCS 2002). However, restricting the verifier's question to classical public coins collapses the corresponding class to $\mathsf{BQP}$, as shown by Beigi, Shor, and Watrous (ToC, 2011). We further study two-message quantum interactive proof systems with a laconic prover. To this end, we introduce the class ${\mathsf{QIP}}_{\ell \text{-}\mathrm{bit}}(2)$, where $\ell$ is the length of the prover's response, and establish: 1. A natural complete characterization of ${\mathsf{QIP}}_{\ell \text{-}\mathrm{bit}}(2)$ by Multi-State Distinguishability. In particular, Quantum State Distinguishability (QSD) is ${\mathsf{QIP}}_{\mathrm{bit}}$-complete. Since QSD is $\mathsf{QSZK}$-hard, our result places ${\mathsf{QIP}}_{\ell \text{-}\mathrm{bit}}(2)$, for $\ell \ge 2$, in a landscape "just above" $\mathsf{QSZK}$. 2. Easy regimes for ${\mathsf{QIP}}_{\ell \text{-}\mathrm{bit}}(2)$ collapsing to $\mathsf{QSZK}$. We prove that QSD$[a,b]$ (and thus ${\mathsf{QIP}}_{\mathrm{bit}}[a,b]$) is in $\mathsf{QSZK}$ when $a(n)-b(n)\ge 1/O(\log n)$, and combine this with an answer compression from ${\mathsf{QIP}}_{\ell \text{-}\mathrm{bit}}[2,c,s]$ to ${\mathsf{QIP}}_{\mathrm{bit}}$ to obtain another easy regime when $2c>(1+2^{\ell /2})s$. Remarkably, our improved polarization applies to SD and $\mathsf{SZK}$, resolving an open problem in Sahai and Vadhan (JACM, 2003). 3. Quantum public coins also make the interaction useless: $\mathsf{qc}\text{-}\mathsf{QAM}[O(\sqrt{\log n})]$ with constant gap is in $\mathsf{BQP}$, where $\mathsf{qc}\text{-}\mathsf{QAM}[\ell ]$ is a subclass of ${\mathsf{QIP}}_{\ell \text{-}\mathrm{bit}}(2)$ in which the verifier's question is exactly halves of EPR pairs.

66 pages, 4 protocols, 2 algorithms, 3 circuits, 4 tables. v2: Minor changes