Quick Navigation

Topics

Quantum Circuit Design Gate Engineering Quantum Simulation Quantum State Preparation Representation Quantum Entropy Information Measures

A slightly improved upper bound for quantum statistical zero-knowledge

arXiv
Authors: François Le Gall, Yupan Liu, Qisheng Wang

Year

2025

Paper ID

36633

Status

Preprint

Abstract Read

~2 min

Abstract Words

166

Citations

N/A

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 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 co-mathsf{QIP(2)} denotes the complement of mathsf{QIP(2)}. We slightly improve this upper bound to mathsf{QIP(2)} cap co-mathsf{QIP(2)} with a quantum linear-space honest prover. A similar improvement also applies to the upper bound for the non-interactive variant mathsf{NIQSZK}. Our main techniques are an algorithmic version 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, to appear).

Why This Paper Matters

  • This paper contributes to the Quantum Simulation research area in the Quantum Articles archive.
  • It adds a 2025 reference point for readers tracking recent quantum research.
  • The complexity class Quantum Statistical Zero-Knowledge mathsfQSZK, introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper...

Paper Tools

Become a member to use research tools

Sign in to open papers, visit source links, share, cite, compare, copy DOI links, request category corrections, and build your reading list.

Show Paper arXiv Publisher Share Cite This Paper Copy URL Compare Copy DOI Add to Reading List Category Correction Request

References & Citation Signals

Local Citation Graph (Related-Paper Links)

Current Paper #36633 #68426 On the Approximate Non-Determin... #68474 Concentration-Free Quantum Kern... #68471 von Neumann measurement and qua... #68466 Uncloneable Encryption from Dec...

External citation index: OpenAlex citation signal

Community Reactions

Quick sentiment from readers on this paper.

Score: 0
Likes: 0 Dislikes: 0

Sign in to react to this paper.

Discussion & Reviews (Moderated)

Average Rating: 0.0 / 5 (0 ratings)

No written reviews yet.