Technical Summary: On Quantum Interactive Proofs with a Laconic Prover

1. Problem Statement and Motivation

This work investigates two-message quantum interactive proof systems (QIP(2)) with a laconic prover. In this model, a quantum verifier sends a question of polynomial length, but the prover is restricted to sending a response of only logarithmic length ($\ell = O(\log n)$ bits).

The study is motivated by several factors:

• Classical Precedents: In the classical setting, interactive proofs with a laconic prover (where the prover sends $O(\log n)$ bits) have been studied extensively (e.g., Goldreich, Vadhan, and Wigderson, 2002). These models are known to capture the class of Statistical Zero-Knowledge (SZK) problems.
• Quantum Analogues: While general quantum interactive proofs (QIP) are equivalent to PSPACE (Watrous, 2003; Jain, Ji, Upadhyay, and Watrous, 2011), the power of restricted variants like two-message systems with laconic provers remains less understood.
• Public Coins: A known result by Beigi, Shor, and Watrous (2011) established that if the verifier's question consists solely of classical public coins, the class collapses to BQP. This paper explores whether this collapse holds for quantum public coins (where the verifier sends halves of EPR pairs) and investigates the landscape of these systems when the prover's response is restricted.
• Cryptographic Connections: These systems relate to succinct non-interactive protocols with setup, where the verifier's question is moved to a setup phase, leaving only the laconic prover's response online. Understanding their power informs whether statistical soundness can be achieved with succinctness.

2. Methodology and Technical Toolkit

The authors employ a combination of quantum information theory, complexity theory, and advanced quantum algorithmic techniques. Key methodological components include:

• State Distinguishability Formulations: The maximum acceptance probability of a QIP(2) system with a laconic prover is characterized as an optimization problem over Positive Operator-Valued Measures (POVMs) acting on subnormalized states. This is linked to the Multi-State Distinguishability Problem (MultiQSD).
• Holevo–Helstrom and Trace Distance: For binary cases ($\ell=1$), the authors utilize the closed-form Holevo–Helstrom formula to relate acceptance probabilities to trace distances. For general $\ell$, they employ polarization techniques to amplify the gap between completeness and soundness.
• Quantum Jensen–Shannon Divergence (QJS): To prove containment in QSZK for "natural regimes" (where the gap $a-b \ge 1/O(\log n)$), the authors reduce Quantum State Distinguishability (QSD) to the Quantum Entropy Difference (QED) problem. They achieve this by constructing a signed linear combination of QJS divergences between parameterized quantum states that approximates the trace distance. This relies on:
  • Smoothed integral representations of QJS.
  • Efficient uniform polynomial approximations of the absolute value function (using Chebyshev polynomials).
  • Dyadic convex combinations of quantum states.
• Answer Compression via Hashing: To compress an $\ell$-bit response to a single bit, the authors use pairwise-independent hash functions (affine inner products) as randomness extractors. They show that if the prover cannot distinguish the underlying states well, the hash of the prover's label remains nearly uniform even given the quantum side information.
• Quantum Singular Value Transformation (QSVT) and Block-Encoding: For analyzing systems with quantum public coins, the authors use QSVT to implement polynomial transformations of operators (e.g., approximating the absolute value function or the sign function) without explicitly materializing exponentially large matrices.
• Matrix Multiplicative Weights Update (MMWU): For the general case of quantum public coins with $\ell = O(\sqrt{\log n})$, the authors apply the MMWU framework (Arora and Kale, 2007) to approximate the Steering-Game Value. They use relative entropy analysis to bound the number of iterations required, avoiding the exponential time complexity typically associated with MMWU in high dimensions.

3. Key Contributions and Results

3.1 Characterization of QIP$_{\ell\text{-bit}}$(2)

The paper establishes a natural complete characterization of two-message quantum interactive proofs with a laconic prover via the Multi-State Distinguishability Problem (MultiQSD).

• Completeness: For any $\ell(n) = O(\log n)$, the problem of distinguishing an ensemble of $2^\ell$ quantum states (MultiQSD) is QIP$_{\ell\text{-bit}}$-complete.
• Hardness: Specifically, Quantum State Distinguishability (QSD, the case $\ell=1$) is QIP$_{\text{bit}}$-complete.
• Landscape: This result places QIP$_{\ell\text{-bit}}$ (for $\ell \ge 2$) in a complexity landscape "just above" QSZK (Quantum Statistical Zero-Knowledge). Since QSD is QSZK-hard, and QIP$_{\text{bit}}$ contains QSZK, the class QIP$_{\ell\text{-bit}}$ for $\ell \ge 2$ is strictly more powerful than QSZK unless QSZK = QIP$_{\ell\text{-bit}}$.

3.2 Easy Regimes Collapsing to QSZK

The authors identify two regimes where QIP$_{\ell\text{-bit}}$ collapses to QSZK:

1. Natural Regime Polarization: They prove that QSD[$a, b$] $\in$ QSZK whenever the gap satisfies $a(n) - b(n) \ge 1/O(\log n)$. Remarkably, the same improvement in polarizing the distance to the natural regime applies to the classical setting, showing that SD[$a, b$] $\in$ SZK for constant $a > b$. This resolves the first open problem posed in Sahai and Vadhan (2003) regarding the classical Statistical Difference (SD) problem.
   • Significance: This improves upon previous results that required a gap of $a^2 - b \ge 1/\text{poly}(n)$ or weaker bounds.
2. Answer Compression: They establish an answer compression theorem: If the completeness $c$ and soundness $s$ satisfy $c > \frac{1 + 2^{\ell/2}}{2} s$, then QIP$_{\ell\text{-bit}}$[2, $c, s$] $\subseteq$ QIP$_{\text{bit}}$.
   • Combined with the polarization result, this implies that for $\ell \ge 2$, if the gap is sufficiently separated (specifically $c - \frac{1+2^{\ell/2}}{2}s \ge 1/O(\log n)$), the class collapses to QSZK.

3.3 Quantum Public Coins and BQP Containment

The paper investigates the power of quantum public coins (qc-QAM), where the verifier sends halves of EPR pairs.

• Single-bit Case: They prove that qc-QAM[1] = BQP for any inverse-polynomial gap. This strengthens the classical result that classical public coins collapse laconic proofs to BPP.
• General Case: They show that qc-QAM[$O(\sqrt{\log n})$] $\subseteq$ BQP for a constant promise gap.
  • Methodology: This is achieved by estimating the Steering-Game Value using the Matrix Multiplicative Weights Update framework combined with QSVT. The algorithm runs in time $\text{poly}(n, \ell) \exp(O(\ell^2))$, which is polynomial in $n$ when $\ell = O(\sqrt{\log n})$.
  • Implication: This suggests that quantum public coins, even with entanglement, do not provide additional power over BQP for laconic provers within this parameter regime, unlike the general QIP(2) setting.

4. Significance and Claims

The authors claim the following significance for their work:

• Completeness Characterization: They provide the first natural complete problem (MultiQSD) for the class of two-message quantum interactive proofs with a laconic prover, clarifying its position relative to QSZK.
• Resolution of Open Problems: The polarization result for the trace distance in the "natural regime" ($a-b \ge 1/O(\log n)$) resolves the first open problem listed in Sahai and Vadhan (2003) for the classical Statistical Difference (SD) problem and extends the technique to the quantum case.
• Limitations of Quantum Public Coins: The results demonstrate that while quantum public coins (entanglement) are powerful in general interactive proofs, they render the interaction useless (collapsing to BQP) in the laconic setting for specific parameter regimes ($\ell = O(\sqrt{\log n})$ with constant gap).
• Algorithmic Techniques: The work introduces novel applications of QSVT and MMWU to quantum complexity problems involving state discrimination and steering games, particularly in handling exponentially large state spaces without explicit representation.

5. Open Problems

The paper explicitly leaves the following questions open:

• BQP Containment for Larger $\ell$: It is unknown whether qc-QAM[$\ell$] with $\ell = O(\log n)$ and an inverse-polynomial gap is contained in BQP. The current result only covers $\ell = O(\sqrt{\log n})$ with a constant gap.
• Inverse-Polynomial Regime for SZK/QSZK: It remains open whether SD[$a, b$] $\in$ SZK and QSD[$a, b$] $\in$ QSZK hold for the regime where $a(n) - b(n) \ge 1/\text{poly}(n)$. The authors note that their current approach is limited by the normalization factor in their polynomial approximation, which grows exponentially as the gap shrinks.

In summary, this work rigorously maps the complexity landscape of quantum interactive proofs with laconic provers, establishing completeness results, identifying collapse regimes to QSZK and BQP, and introducing advanced algorithmic techniques to analyze these restricted proof systems.