arXiv:2609.39495
On quantum interactive proofs with a laconic prover
Zihan Hu, Yupan Liu
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 ($\sf QSZK$), introduced by Watrous (FOCS 2002). However, restricting the verifier's question to classical public coins collapses the corresponding class to $\sf 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 ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$, where $\ell$ is the length of the prover's response, and establish: 1. A natural complete characterization of ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ by Multi-State Distinguishability. In particular, Quantum State Distinguishability (QSD) is ${\sf QIP}_{\rm bit}$-complete. Since QSD is $\sf QSZK$-hard, our result places ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$, for $\ell\geq 2$, in a landscape "just above" $\sf QSZK$. 2. Easy regimes for ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ collapsing to $\sf QSZK$. We prove that QSD$[a,b]$ (and thus ${\sf QIP}_{\rm bit}[a,b]$) is in $\sf QSZK$ when $a(n)-b(n)\geq 1/O(\log n)$, and combine this with an answer compression from ${\sf QIP}_{\ell\text{-}{\rm bit}}[2,c,s]$ to ${\sf QIP}_{\rm bit}$ to obtain another easy regime when $2c>(1+2^{\ell/2})s$. Remarkably, our improved polarization applies to SD and $\sf SZK$, resolving an open problem in Sahai and Vadhan (JACM, 2003). 3. Quantum public coins also make the interaction useless: ${\sf qc}\text{-}{\sf QAM}[O(\sqrt{\log{n}})]$ with constant gap is in $\sf BQP$, where ${\sf qc}\text{-}{\sf QAM}[\ell]$ is a subclass of ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ in which the verifier's question is exactly halves of EPR pairs.
AI Summary
The paper studies two-message quantum interactive proofs in which the verifier sends polynomially many qubits and the prover returns only $\ell=O(\log n)$ classical bits. Quantum responses are equivalent up to a factor-two communication overhead via teleportation and superdense coding. It characterizes the resulting class $\mathsf{QIP}_{\ell\text{-bit}}(2)$ by multi-state distinguishability: estimating the optimal probability of identifying a uniformly sampled label among $2^\ell$ efficiently preparable states is complete for the class. For one-bit responses, ordinary quantum state distinguishability (QSD) is complete. The reductions express verifier acceptance as a POVM optimization over subnormalized states and add normalization padding. It also establishes $\mathsf{QSD}[a,b]\in\mathsf{QSZK}$ and classical $\mathsf{SD}[a,b]\in\mathsf{SZK}$ whenever $a-b\geq1/O(\log n)$, covering arbitrary constant thresholds $a>b$ beyond the previous $a^2>b$ regime. The construction approximates trace distance using signed combinations of smoothed Jensen–Shannon divergences, then encodes these as entropy differences. A separate answer-compression construction uses pairwise-independent hashing with quantum side information; its separation condition is $2c>(1+2^{\ell/2})s$, with additional quantitative gap requirements for the resulting $\mathsf{QSZK}$ containment. For quantum-public-coin questions consisting of EPR halves, constant-gap protocols lie in $\mathsf{BQP}$ for $\ell=O(\sqrt{\log n})$. The algorithm combines matrix multiplicative weights, QSVT and normalized trace estimation, with runtime $\operatorname{poly}(n,\ell,1/\Delta)\exp(O(\ell^2/\Delta^6))$. One-bit responses allow inverse-polynomial gaps. Extending this collapse to logarithmic responses and inverse-polynomial gaps remains open, as does polarization for arbitrary inverse-polynomial gaps. The polarization construction incurs an exponential-in-inverse-error normalization loss, which is unavoidable within its approximation family.
Large language model tools were used interactively at all stages of the preparation of this manuscript: from the earliest exploratory research stages to the final exposition and writing steps.
Central claim may not hold: The abstract overstates the answer-compression-based QSZK regime by omitting the response-length bound and quantitative separation required by the body's corollary; strict positivity of 2c−(1+2^{ℓ/2})s alone is insufficient for the supplied proof. The unconditional corollary QIP_bit=co-QIP_bit is not established by the cited argument, because QIP_bit includes inverse-polynomial gaps while the proved QSZK containment covers only inverse-logarithmic or larger gaps.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 66 pages, 4 protocols, 2 algorithms, 3 circuits, 4 tables. v2: Minor changes