On quantum interactive proofs with a laconic prover

AI summary

Overview

Research area: Quantum complexity theory — specifically two-message quantum interactive proof systems in which the prover is restricted to a very short ("laconic") answer, and the resulting complexity classes are compared with quantum statistical zero-knowledge (QSZK), BQP, and their classical counterparts.

Technical level: Advanced. The paper is written for readers comfortable with quantum interactive proofs, POVMs, trace distance, von Neumann entropy, and standard complexity-class containments.

Scope: The paper defines the class QIP_{ℓ-bit}(2) (a two-message quantum interactive proof with an ℓ-bit classical prover response), characterizes it via multi-state distinguishability, identifies regimes where it collapses to QSZK, and shows that quantum public coins make the interaction useless.

What This Paper Is About

Interactive proofs with a laconic prover, introduced by Goldreich, Vadhan, and Wigderson (CC 2002), study what can be verified when the prover sends only logarithmic (or even a single bit of) communication. In the quantum two-message setting, Watrous (FOCS 2002) observed that a one-bit prover response already suffices to capture QSZK, but Beigi, Shor, and Watrous (ToC 2011) showed that if the verifier's question is restricted to classical public coins, the class collapses all the way to BQP.

This paper asks what happens in between: how much power does a two-message quantum proof retain as a function of the length ℓ of the prover's classical answer, which parameter regimes collapse to QSZK, and whether quantum public coins (halves of EPR pairs) are as useless as classical ones.

Key Contributions

1. A complete characterization of QIP_{ℓ-bit}(2). The authors introduce QIP_{ℓ-bit}(2), where ℓ is the length of the prover's response, and prove that for every positive integer-valued ℓ(n) ≤ O(log n), the class is exactly characterized by the Multi-State Distinguishability problem (MultiQSD_{2^ℓ}); in particular, Quantum State Distinguishability (QSD) is QIP_bit-complete.

2. Polarization of trace distance and total variation distance in the natural regime. They prove QSD[a,b] ∈ QSZK and SD[a,b] ∈ SZK whenever a(n) − b(n) ≥ 1/O(log n), which resolves the first open problem posed in Sahai and Vadhan (JACM, 2003) and is the first approach to bypass the oblivious black-box polarization barrier of Holenstein and Renner (Corollary 2), which permits polarization for fixed thresholds only when a² > b.

3. Answer compression from ℓ bits to one bit. They show QIP_{ℓ-bit}[2,c,s] ⊆ QIP_bit[1/2 + c/2^{ℓ+1}, 1/2 + (1+2^{ℓ/2})s/2^{ℓ+2}] whenever c > ((1+2^{ℓ/2})/2)·s, a quantum analogue of a Goldreich–Vadhan–Wigderson theorem (Theorem 3.4) that covers a strictly larger parameter regime.

4. Quantum public coins trivialize laconic interaction. They prove qc-QAM[ℓ,c,s] ⊆ BQP for ℓ(n) ≤ O(√log n) whenever the promise gap Δ(n) = c(n) − s(n) ≥ Ω(1), strengthening the classical-public-coin collapse of Beigi, Shor, and Watrous (Theorem 5.1) to the quantum public-coin setting.

Main Findings

• QIP_{ℓ-bit} sits "just above" QSZK. Because QSD is QIP_bit-complete and QSD is QSZK-hard (Watrous, FOCS 2002), the authors place QIP_{ℓ-bit}(2) for ℓ ≥ 2 in a landscape "just above" QSZK; the completeness result also supplies the QIP_bit-hardness matching the known inclusion QSZK ⊆ QIP_bit (Beigi–Shor–Watrous, Section 5).

• MultiQSD is the natural complete problem. MultiQSD[ℓ,a,b] asks whether the optimal success probability MSucc(Q) = max over POVMs {E_r} of (1/2^ℓ) Σ_{r ∈ {0,1}^ℓ} Tr(E_r ρ_r) is at least a or at most b; for ℓ = 1 this reduces to (1 + TD(ρ_0,ρ_1))/2 via the Holevo–Helstrom measurement, and it recovers the classical Generalized Statistical Difference problem (GSD) of Goldreich–Vadhan–Wigderson when the states are diagonal.

• One-bit proofs equal QSZK. For c(n) − s(n) ≥ 1/O(log n), QIP_bit[c,s] ⊆ QSZK and IP_bit[c,s] ⊆ SZK, informally giving QIP_bit = QSZK and improving Goldreich–Vadhan–Wigderson (Theorem 3.1); the classical implication SD[a,b] ∈ SZK for constant a > b resolves the first open problem in Sahai–Vadhan (JACM, 2003).

• Easy regimes for ℓ ≥ 2 collapse to QSZK. For ℓ(n) ≤ ⌊log log n⌋, if c(n) − ((1+2^{ℓ(n)/2})/2)·s(n) ≥ 2^{ℓ(n)}/O(log n), then QIP_{ℓ-bit}[2,c,s] ⊆ QSZK.

• Strictly wider compression regime than the classical analogue. The compression theorem applies to ℓ = 2, c = 1, and s = 3/5, parameters that violate the requirement s < 2^{−ℓ/2} in Goldreich–Vadhan–Wigderson (Theorem 3.4).

• Quantum public coins are useless for laconic provers. For ℓ(n) ≤ O(√log n) and Δ(n) ≥ Ω(1), qc-QAM[ℓ,c,s] ⊆ BQP, with the underlying quantum algorithm efficient whenever ℓ²/Δ⁶ = O(log n); in the single-bit case qc-QAM[1] ⊆ BQP holds for all Δ(n) ≥ 1/poly(n). Here qc-QAM[ℓ] is the subclass of QIP_{ℓ-bit}(2) in which the verifier's question consists solely of halves of EPR pairs.

• Classical responses are without loss of generality. Using teleportation and superdense coding, any ℓ-qubit quantum response can be simulated by a 2ℓ-bit classical response and vice versa, preserving completeness and soundness — the same reasoning behind QIP = qcc-QAM (KLN19).

• No empirical or numerical evaluation. The paper reports no experiments, datasets, benchmarks, or model implementations; all results are complexity-theoretic theorems and inclusions.

Methodology in Plain English

The authors translate "how powerful is a two-message quantum proof with a short answer?" into an optimization problem. Because the prover returns only a classical string r ∈ {0,1}^ℓ, its strategy is a POVM {M_r}, and the maximum acceptance probability of a verifier V is ω(V) = max over POVMs of Σ_r Tr(M_r X_r), where each X_r is a subnormalized state produced by running the verifier against the fixed answer r.

• Completeness (hardness). They pad the operators {X_r} into normalized, efficiently preparable states {ρ_r} so that the optimal discrimination probability of the padded ensemble is an affine function of ω(V), namely ((2^ℓ − 1)/2^ℓ)·ω(V) + 1. The padding uses a carefully chosen μ_r that assigns each classical label a maximum weight of exactly 1/2^ℓ, so the padding contributes a fixed amount regardless of the traces p_r = Tr(X_r). For ℓ = 1 they instead use the closed-form Holevo–Helstrom expression ω(V) = (Tr(X_0) + Tr(X_1) + ‖X_0 − X_1‖₁)/2 and build two states with trace distance exactly ω(V).

• Answer compression. To shrink ℓ bits to one bit, they replace "guess the ℓ-bit label r" with "guess a single-bit label h_{u,v}(r) = ⟨u,r⟩ ⊕ v" for a pairwise independent hash, building two normalized states ρ_0 and ρ_1 from the 2^ℓ subnormalized states. For yes instances a successful guess of r yields the correct bit; for no instances they invoke the fact that pairwise independent hash families are strong randomness extractors even with quantum side information (TSSR11, Theorem 6). This yields ω(V)/2^ℓ ≤ TD(ρ_0,ρ_1) ≤ ((1+2^{ℓ/2})/2^{ℓ+1})·ω(V).

• Polarization in the natural regime. Their warm-up routes QSD through the quantum Jensen–Shannon divergence QJS and the Quantum Entropy Difference problem QED. A parameterized family ρ_{j,λ} = ((1+λ)/2)ρ_j + ((1−λ)/2)ρ_{1−j} gives the bounds λ²/(2 ln 2)·TD² ≤ QJS₂(ρ_{0,λ},ρ_{1,λ}) ≤ λ²/(2 ln 2(1−λ²))·TD, with the upper bound proved by differentiating along the smoothing path, using operator monotonicity of the logarithm, and integrating. To break the a² > b barrier they encode a signed linear combination of QJS terms — using entropy additivity, with negative coefficients implemented by swapping components between the two constructed states — approximating TD to additive error ε and then subtracting a threshold and normalizing. The scalar core is a uniform approximation of |x| by Σ_j c_j Φ(λ_j x), with Φ(x) = 1 − H₂((1+x)/2), coefficients obtained from a Vandermonde system using the expansion of Φ, then rounded to dyadic numbers. The blow-up is controlled by ‖c‖₁ ≤ 2^{O(1/ε)}, giving gap g(n) = ε(n)/Υ ≥ Δ·2^{−O(1/Δ)} and remaining inverse-polynomial as long as Δ(n) ≥ 1/O(log n).

• Public coins. They define a steering game in which Alice and Bob share m EPR pairs, Alice measures her halves with a POVM {M_r} and sends the outcome r; the steering-game value is a complete problem for qc-QAM[ℓ], which they then collapse into BQP.

Why This Matters

The paper sharpens a striking asymmetry in complexity theory: quantum interactive proofs parallelize to three messages (KW00), whereas the classical analogue would collapse the polynomial-time hierarchy, and yet two-message quantum proofs with short answers seem to hover just above QSZK unless the verifier's coins are made public. It also produces the first polarization technique that escapes the oblivious black-box barrier of Holenstein and Renner, a barrier that constrained all prior classical polarization approaches (Sahai–Vadhan; BDRV19).

Potential applications (all theoretical implications of the results, not demonstrated implementations in the paper):

• Succinct non-interactive protocols with setup. The authors explicitly motivate the model by moving the verifier's question into a setup phase and leaving only the laconic response online; their results probe whether succinctness and statistical soundness can coexist at the cost of an instance-independent setup, before relaxing soundness to computational.
• Quantum statistical zero-knowledge protocol design. The equivalence QIP_bit = QSZK and the QSZK containments identify which short-answer proof systems can be re-cast as zero-knowledge protocols.
• Quantum state discrimination and certification. MultiQSD is a standard quantum information primitive whose optimal success probability has a semidefinite-programming formulation (EMV03), connecting proof-system power to state-discrimination tasks.
• Guiding expectations for quantum-coin-based protocols. The qc-QAM ⊆ BQP collapse warns protocol designers that replacing classical public coins with EPR halves does not buy extra verification power in the laconic regime.

Industry relevance: chiefly for teams designing quantum-safe cryptographic protocols, verifiable delegation of quantum computation, and succinct proof systems, where knowing which setup assumptions are provably useless prevents wasted protocol complexity. There is no hardware, software, or benchmark component.

Future Directions

• Pin down QIP_{ℓ-bit} for ℓ ≥ 2. The results place QIP_{ℓ-bit}(2) for ℓ ≥ 2 "just above" QSZK, but the exact relation between QIP_{ℓ-bit} for ℓ ≥ 2 and QSZK or QIP_bit is not resolved; only restricted regimes collapse.
• Remove the Ω(1) promise gap and the O(√log n) bound. The qc-QAM ⊆ BQP collapse requires Δ(n) ≥ Ω(1) (efficiency needs ℓ²/Δ⁶ = O(log n)), with the single-bit case handling Δ(n) ≥ 1/poly(n); extending the collapse to small gaps and larger ℓ is left open.
• Push polarization past 1/O(log n). The gap g(n) ≥ Δ·2^{−O(1/Δ)} stops being inverse-polynomial once Δ drops below 1/O(log n); improving the doubly exponential dependence on 1/Δ, and extending the threshold from a > b to wider regimes, remain open.
• Extend the MultiQSD characterization beyond logarithmic answers. The completeness theorem is stated for ℓ(n) ≤ O(log n); behavior for longer prover responses is not established.

Target Audience

Complexity theorists and quantum information researchers working on interactive proofs, zero-knowledge, and state discrimination; cryptographers interested in the foundations of succinct non-interactive arguments with setup; and graduate students who already know POVMs, trace distance, and standard complexity classes and want a precise map of what short quantum proofs can and cannot verify. Readers seeking experimental results, implementations, or numerical benchmarks will find none here.

Authors’ 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&gt;(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.