Metraipolis › archive › dc_e465e35151ce
On quantum interactive proofs with a laconic prover — arXiv:2609.39495
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.39495
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T13:43:29.630Z
- SHA-256 of the archived text
f05d7538ea961363001724ff52bae0d19571c257c9f1e97878d35ea18cc0bf3f- Stable URL of this page
https://metraipolis.com/documento/dc_e465e35151ce
How to cite
On quantum interactive proofs with a laconic prover — arXiv:2609.39495 — arXiv (en), https://arxiv.org/abs/2609.39495 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e465e35151ce (Metraipolis archive dc_e465e35151ce, sha256 f05d7538ea961363001724ff52bae0d19571c257c9f1e97878d35ea18cc0bf3f)
BibTeX
@misc{dce465e35151ce,
title = {On quantum interactive proofs with a laconic prover — arXiv:2609.39495},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.39495},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e465e35151ce; sha256 f05d7538ea961363001724ff52bae0d19571c257c9f1e97878d35ea18cc0bf3f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.39495. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-10-01 in cs.CR).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC); Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2609.39495 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T13:16:25.265Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).