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 (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_ℓ−bit(2), where ℓ is the length of the prover's response, and establish: 1. A natural complete characterization of sf QIP_ℓ−bit(2) by Multi-State Distinguishability. In particular, Quantum State Distinguishability (QSD) is sf QIP_bit-complete. Since QSD is sf QSZK-hard, our result places sf QIP_ℓ−bit(2), for ℓ≥ 2, in a landscape "just above" sf QSZK. 2. Easy regimes for sf QIP_ℓ−bit(2) collapsing to sf QSZK. We prove that QSD[a,b] (and thus sf QIP_bit[a,b]) is in sf QSZK when a(n)−b(n)≥ 1/O(log n), and combine this with an answer compression from sf QIP_ℓ−bit[2,c,s] to sf QIP_bit to obtain another easy regime when 2c>(1+2^ℓ/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−sf QAM[O(√(logn))] with constant gap is in sf BQP, where sf qc−sf QAM[ℓ] is a subclass of sf QIP_ℓ−bit(2) in which the verifier's question is exactly halves of EPR pairs.

Interactive proofs for verifying (quantum) learning and testing
Matthias C. Caro, Jens Eisert, Marcel Hinsche +3
Quantum20 Oct 2026Peer-reviewedCC BY 4.0Full textQuantum physics & quantum informationCrossref
Multi-Prover Interactive Proof Systems with Leakage
Vahid R. Asadi, Atsuya Hasegawa, François Le Gall
arXiv5 Jul 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Beyond IP = PSPACE and QIP = PSPACE: Interactive Proofs in Arbitrary Physical Theories
Kishor Bharti
arXiv1 Oct 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Elementary proofs of quantum lower bounds for element distinctness and k-sum
Andris Ambainis, Martins Kokainis
arXiv23 Oct 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
Algebraic Proofs of Quantum Period--TBA Relations
Min-xin Huang
arXiv7 Oct 2026PreprintCC BY 4.0Full textHigh-energy & particle physicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{hu2026quantum,
  title = {{On quantum interactive proofs with a laconic prover}},
  author = {Zihan Hu and Yupan Liu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.39495},
  eprint = {2609.39495},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.39495},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - On quantum interactive proofs with a laconic prover
AU  - Zihan Hu
AU  - Yupan Liu
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2609.39495
UR  - https://arxiv.org/abs/2609.39495
AB  - 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_ℓ−bit(2), where ℓ is the length of the prover's response, and establish: 1. A natural complete characterization of sf QIP_ℓ−bit(2) by Multi-State Distinguishability. In particular, Quantum State Distinguishability (QSD) is sf QIP_bit-complete. Since QSD is sf QSZK-hard, our result places sf QIP_ℓ−bit(2), for ℓ≥ 2, in a landscape "just above" sf QSZK. 2. Easy regimes for sf QIP_ℓ−bit(2) collapsing to sf QSZK. We prove that QSD[a,b] (and thus sf QIP_bit[a,b]) is in sf QSZK when a(n)−b(n)≥ 1/O(log n), and combine this with an answer compression from sf QIP_ℓ−bit[2,c,s] to sf QIP_bit to obtain another easy regime when 2c>(1+2^ℓ/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−sf QAM[O(√(logn))] with constant gap is in sf BQP, where sf qc−sf QAM[ℓ] is a subclass of sf QIP_ℓ−bit(2) in which the verifier's question is exactly halves of EPR pairs.
ER  -

Abstract

Related

Cite