AI & ML
A slightly improved upper bound for quantum statistical zero-knowledge
arXiv math.IT0 views
arXiv:2512.11597v3 Announce Type: replace-cross Abstract: The complexity class Quantum Statistical Zero-Knowledge ($\mathsf{QSZK}$), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound $\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}$, which was simplified following the inclusion $\mathsf{QIP(2)} \subseteq \mathsf{PSPACE}$ established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, $\mathsf{QIP(2)}$ denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and $\text{co-}\mathsf{QIP(2)}$ denotes the complement of $\mathsf{QIP(2)}$. We slightly improve this upper bound to $\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}$ with a quantum linear-space honest prover. Specifically, the honest prover uses space linear in the size of the transcript of the original $\mathsf{QSZK}$ proof system. A similar improvement also applies to the upper bound for the non-interactive variant $\mathsf{NIQSZK}$. Our main techniques are algorithmic versions of the Holevo-Helstrom measurement and the Uhlmann transform, both implementable in quantum linear space, implying polynomial-time complexity in the state dimension, using the recent space-efficient quantum singular value transformation of Le Gall, Liu, and Wang (CC, 2026). We also establish that our linear-space bounds for these two tasks are near-optimal under the counting version of the Satisfiability Hypothesis (#SH).
Source:https://arxiv.org/abs/2512.11597PreviousCaMBRAIN: Real-time, Continuous EEG Inference with Causal State Space ModelsNextSemifields and rank-metric codes from Drinfeld modules
Related posts
The Songless Archive Is a Better Listening Log Than a Playlist
0dev.to
AI makes it easier to understand the whole project
0dev.to
ChatGPT Has No Secret Codes. These Features Are What Help
0dev.to
How to Check a Freelancer's AI Work Before You Pay Them
0dev.to
I scanned 277 public MCP servers. Here's what 90% of them miss.
0dev.to

The JSON Parsed. Is It Right? How to Score LLM Data Extraction
0dev.to