A slightly improved upper bound for quantum statistical zero-knowledge
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.
Kai: We're looking at the paper: "A slightly improved upper bound for quantum statistical zero-knowledge".
Paper summary: Kai: So we're looking at this paper here titled "A slightly improved upper bound for quantum statistical zero-knowledge." Basically, they're taking the class Quantum Statistical Zero-Knowledge, or QSZK. This is a complexity class defined by promise problems that have a single prover and allow for an interactive proof system with statistical zero-knowledge properties.
Mira: That sounds like it involves proving something is true without revealing any extra information about the secret data, beyond just the fact that it's true > It builds on earlier work where they showed QSZK was in QIP two intersected with co-QIP two, which was a bit simplified because of a result by Jain, Upadhyay and Watrous in two thousand nine > <ref:2512.11597#pg1>
Lev: That QIP two intersection co-QIP two is the standard upper bound for this class, but usually that implies a certain space overhead for the honest prover > So what are they trying to do here?
Kai: They're claiming a slight improvement. They've shown that QSZK is in QIP two intersected with co-QIP two with an honest prover that uses quantum linear space > And it even applies to the non-interactive version called NIQSZK, showing it's in qq QAM with a linear space honest prover >
Mira: That means the space complexity for that honest prover is linear in the size of the transcript from the original QSZK proof system > Which is a step up because usually you're dealing with exponential time or space overhead depending on how you look at it >
Lev: Linear space for an honest prover sounds promising when you think about running this on real hardware, but what's the cost of that linear space compared to what we need for a standard two-message quantum interactive proof system?
Kai: The paper says their main techniques involve algorithmic versions of the Holevo Helstrom measurement and the Uhlmann transform > They use these tools, which they claim are implementable in quantum linear space > This is tied into using a space efficient quantum singular value transformation framework >
Mira: That framework allows them to implement those measurements and transforms in that linear space, but it's important to remember they explicitly keep the degree of that approximation, called d prime, as being O of d > So it's a space efficient version specifically >
Lev: Implementing things in linear space is good for theoretical bounds, but how does that translate to something we can actually build? Does the overhead from this linear space honest prover really land where we expect it to?
Paper summary: Kai: They show that because of these techniques, the resulting bound for F2Est alpha n beta n satisfies a constant function c of n equal to alpha n minus two to the n and a space s of n equal to beta n > So for that specific closeness testing problem, the space is bounded by that linear term >
Mira: That final result connects this back to closeness testing problems, showing bounds for QSC alpha beta with a quantum O of n prime space honest prover > Which they derive by constructing new quantum states rho zero and rho one whose preparations are also efficiently preparable >
Lev: So we've seen how the space is bounded for these specific problems, but what about the broader context? What does this mean when you look at general two-message quantum interactive proof systems?
Kai: The paper mentions that this linear space honest prover result is a contrast to the general case where you need quadratic quantum space for those two-message systems > It contrasts with the requirement for quadratic quantum space in a more general setting >
Mira: That means we're seeing an improvement over what was previously known when combining existing methods, suggesting that just putting old techniques together doesn't automatically give you the best complexity class results > The authors point out that combining existing methods still requires at least quadratic quantum space >
Lev: So, for practical purposes on hardware, does this linear space honest prover mean anything tangible for scaling up these types of proofs?
Kai: It suggests that for QSZK and NIQSZK specifically, the overhead is manageable because the space scales linearly with the size of your input transcript > That's a different scaling behavior than what we see in more general two-message systems >
Mira: Exactly, it shows that for these particular zero-knowledge problems, we can achieve a better structural placement in complexity classes like QIP two intersected with co-QIP two > It's about finding the right tools to get a better complexity class fit for the problem structure >
Lev: So, what’s the next step here? Are there any open questions they raised about pushing these bounds even further?
Kai: They did raise a few things. One is whether the quantum upper bound for QSZK could be improved to a subclass defined by public coins quantum interactive proof systems > That's exploring different ways to define the proof system itself >
Paper summary: Mira: And another one they ask is whether classical bounds for QSZK and NIQSZK could be improved to any subclass of PSPACE > That would be a significant step if we can get those down further than current classical knowledge allows >
Lev: The third question they bring up is about implementing the honest prover's strategy in any two-message quantum interactive proof system in quantum linear space approximation > It’s about the feasibility of simulating these complex strategies efficiently on real hardware, that's a very concrete engineering concern >
Kai: So, to wrap up this part, what this paper does is tighten the upper bound for QSZK and NIQSZK by showing they fit into QIP two intersected with co-QIP two with an honest prover that stays linear in the transcript size > It uses algorithmic versions of measurements and transforms implemented in quantum linear space >
Mira: It shows how specific tools, like the space efficient quantum singular value transformation framework, can yield these results > And it sets a new benchmark for what we can achieve with these kinds of proofs when you consider their inherent structure >
Lev: It's a solid technical step forward because it gives us a better understanding of the space requirements for verifying statistical zero-knowledge properties in the quantum setting > It’s about understanding the overhead that really lands on your real hardware setup >
Kai: Yeah, so if you're thinking about building or testing systems related to statistical zero-knowledge, this paper gives you a clearer picture of what space complexity you can expect for these proof systems > It points toward linear space being achievable in certain honest prover scenarios >
Mira: It suggests that the structure of the problem matters a lot when we look at which complexity classes apply and how much overhead we need to account for > That's the big picture here about relating theory to what's actually possible >
Lev: Right, so for someone building something, it tells you that while linear space is better than quadratic space in some cases, you still have to be careful about the exact assumptions on the prover strategy and the specific problem you are tackling >
Kai: That's right. So we've covered what this paper claims about QSZK and NIQSZK, how they relate to QIP two intersected with co-QIP two, and what it means for our understanding of proof system overhead >
Conclusion: Kai: So we're wrapping up this discussion on "A slightly improved upper bound for quantum statistical zero-knowledge." The authors are showing that they can get better bounds for these kinds of zero-knowledge proofs than what was previously known.
Mira: They found a way to put this class into QIP two intersected with co-QIP two, but they managed to do it with a quantum linear space honest prover. That means the space needed scales linearly with how big the original proof transcript gets.
Lev: Linear space is good for theory, but we gotta think about what that actually means when you try to run it on real hardware. It suggests a much more manageable overhead than some of those general two-message quantum interactive proof systems usually require.
Kai: Exactly, Lev. So the paper shows that by using these specific tools and approximations, like the singular value transformation framework, we can achieve this linear scaling for QSZK and even its non-interactive cousin NIQSZK.
Mira: It really highlights how much the structure of the problem matters here. It's not just a general bound; it's about finding a specific way to approximate those measurements that lets you keep the space complexity low.
Lev: And that leads to some interesting questions they raise, like whether we can get even better bounds by looking at different types of proof systems, or if we can improve the classical bounds down to something like PSPACE.
Kai: Right. It’s showing us where the current limits are and what kind of structural improvements we need to make in our tools to push those complexity class boundaries further.
François Le Gall, Yupan Liu, Qisheng Wang
Graduate School of Mathematics, Nagoya University · School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne · School of Computer Science, Shanghai Jiao Tong University
quant-ph, cs.CC, cs.IT, math.IT
Submitted: 2025-12-12
Updated: 2026-11-18
Comments: 37 pages, 2 figures, 3 protocols. v3: Added near-optimality results for our linear-space bounds under #SH, along with minor changes. v2: Minor changes, including revisions to the proofs of Theorems 3.4, 4.5, and Corollary 4.9. This work supersedes Section 5 of arXiv:2308.05079v2
Journal ref: Proceedings of the 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026), pp. 12:1-12:20, 2026
DOI: 10.4230/LIPIcs.MFCS.2026.12
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 85/100
The gist: A slightly improved upper bound for quantum statistical zero-knowledge establishes that QSZK is in QIP(2)∩co-QIP(2) with a quantum linear-space honest prover…
Key concepts
- QSZK
- Quantum Statistical Zero-Knowledge is a problem where a prover can convince a verifier of certain information without revealing the underlying secret data. This paper focuses on finding better complexity bounds for this specific quantum proof system.
- QIP(2)∩co-QIP(2)
- This is a complexity class that describes problems solvable by quantum interactive proof systems and their complements. Placing QSZK in this class means it can be verified through an interactive process where the verifier has limited computational power, and the prover's resources are bounded.
- Quantum Linear Space
- This refers to a resource bound for a quantum computer, meaning the amount of auxiliary quantum memory used by the honest prover is proportional to the size of the input. A linear space bound implies that even though quantum algorithms can be powerful, this specific proof system requires relatively little extra memory compared to exponential space.
- QSVT
- The Quantum Singular Value Transformation (QSVT) framework is a technique used to implement complex quantum operations efficiently. In this paper, it allows for implementing measurements and transforms in quantum linear space by using polynomial approximations, which keeps the state dimension manageable.
Terminology
Summary
A slightly improved upper bound for quantum statistical zero-knowledge establishes that QSZK is in QIP(2)∩co-QIP(2) with a quantum linear-space honest prover, which represents a slight improvement over previous bounds. p. 0 A slightly improved upper bound for quantum statistical
zero-knowledge
François Le Gall∗1
, Yupan Liu†2,1, and Qisheng Wang‡3
1Graduate School of Mathematics, Nagoya University
2School of Computer and Communication Sciences, École Polytechnique Fédérale de
Lausanne
3School of Computer Science, Shanghai Jiao Tong University
Abstract
The complexity class Quantum Statistical Zero-Knowledge (QSZK), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper
bound QIP(2) ∩ co-QIP(2), which was simplified following the inclusion QIP(2) ⊆ PSPACE
established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, 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-QIP(2) denotes the complement of QIP(2).Where the paper says it
Pruning redundant reasoning tokens
The main result of this work follows directly from combining Theorems 1.2 and 1.3, showing that QSZK is in QIP(2)∩co-QIP(2) with a quantum linear-space (and thus singleexponential-time) honest prover. p. 3 3:
Corollary 1. p. 3 The main result of this work follows directly from
combining Theorems 1. 3:
Corollary 1. QSZK is in QIP(2) ∩ co-QIP(2) with a quantum linear-space (and thus singleexponential-time) honest prover. More precisely, the space complexity of the honest prover in the
resulting QIP(2) ∩ co-QIP(2) proof system is linear in the size of the transcript in the original
QSZK proof system. 3 also yields the following:
Corollary 1. NIQSZK is in qq-QAM with a quantum linear-space (and thus single-exponentialtime) honest prover.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
How the training signal is built
The paper introduces two key techniques to achieve these bounds: algorithmic versions of the Holevo–Helstrom measurement and the Uhlmann transform, both implementable in quantum linear space. The algorithmic Holevo–Helstrom measurement is used for GapQSD ∈ QIP(2) with a quantum linearspace honest prover. p. 5 1 Algorithmic Holevo–Helstrom measurement
As discussed in Section 1. 2, the honest prover’s strategy underlying GapQSD ∈ QIP(2) is
the Holevo–Helstrom measurement {Π0, Π1}, where Π1 := I − Π0. 2 Algorithmic Uhlmann transform
As discussed in Section 1. 2, the honest prover’s strategy for GapF2Est ∈ QIP(2) is given
by the Uhlmann transform Φ⋆(·) = U⋆(·)U
†
⋆ .Where the paper says it
Where the paper says it
Where the gains come from
The core of the improvement lies in using space-efficient polynomial approximations, specifically the space-efficient quantum singular value transformation (QSVT) framework. This framework allows for implementing these measurements and transforms in quantum linear space, implying polynomial-time complexity in the state dimension. p. 0 A similar improvement also applies to the upper bound
for the non-interactive variant 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,
to appear). 3, we rely on space-efficient polynomial approximations Pd
′ from [LLW25], which can be computed simultaneously in poly(d) time and O(log d)
space, yielding 2
O(n)
time and O(n) space. Here, the original degree d comes from the timeefficiently computable polynomials [GSLW19], and the new degree d
′ = O(d) is kept explicit to
distinguish the space-efficient version.Where the paper says it
Where the paper says it
Implications for QSZK and NIQSZK
The results lead to several important implications for related problems. Corollary 1.4 states that QSZK is in QIP(2)∩co-QIP(2) with a quantum linear-space (and thus singleexponential-time) honest prover. p. 3 3:
Corollary 1. QSZK is in QIP(2) ∩ co-QIP(2) with a quantum linear-space (and thus singleexponential-time) honest prover. The main result of this work follows directly from
combining Theorems 1. 3:
Corollary 1. 3 also yields the following:
Corollary 1. NIQSZK is in qq-QAM with a quantum linear-space (and thus single-exponentialtime) honest prover. systems (e. , proof systems with the statistical zero-knowledge property) to another class with
distinct structural features (e.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Further open problems
The paper discusses several open questions regarding further improvements. One question concerns whether the quantum upper bound for QSZK could be improved to a subclass of QIP(2) defined in terms of “public coins” quantum interactive proof systems. p. 7 Since the best known
upper bound for the classical counterpart SZK is AM ∩ coAM, as established in [For87, AH91],
this inclusion naturally motivates the following question:
(a) Could the quantum upper bound for QSZK be improved to a subclass of QIP(2) defined
in terms of “public coins” quantum interactive proof systems [MW05, KLN19], such as
qq-QAM ∩ co-qq-QAM? A more intriguing question concerns the classical upper bound for QSZK, whose best known
bound is PSPACE and is believed “almost certainly can be improved” in [Wat02, Section 7]:
(b) Could the classical upper bounds for QSZK and NIQSZK be improved to any subclass of
PSPACE? Since the best known
upper bound for the classical counterpart SZK is AM ∩ coAM, as established in [For87, AH91],
this inclusion naturally motivates the following question:
(a) Could the quantum upper bound for QSZK be improved to a subclass of QIP(2) defined
in terms of “public coins” quantum interactive proof systems [MW05, KLN19], such as
qq-QAM ∩ co-qq-QAM? A more intriguing question concerns the classical upper bound for QSZK, whose best known
bound is PSPACE and is believed “almost certainly can be improved” in [Wat02, Section 7]:
(b) Could the classical upper bounds for QSZK and NIQSZK be improved to any subclass of
PSPACE? 10
Noting that the notion of honest-prover efficiency in our results (Theorems 1. 3)
appears specifically tailored for two-message quantum interactive proof systems, the distinction
between our results and the general case suggests the following question:
(c) Could the honest prover’s strategy in any two-message quantum interactive proof system be
approximately implemented in quantum linear space, meaning that the space complexity
of the algorithmic implementation scales linearly with the number of qubits on which the
verifier’s message-preparing circuit acts?Where the paper says it
Where the paper says it
Where the paper says it
Related works
The paper relates its findings to several related areas. It compares the upper bound for QSZK to the best known classical bound AM ∩ coAM. p. 2 In particular, an intermediate step proving QIP(2) ⊆ PSPACE in [JUW09] immediately simplified
the state-of-the-art upper bound for QSZK to
QSZK ⊆ QIP(2) ∩ co-QIP(2). By contrast, the best known upper bound for the classical counterpart SZK is AM ∩ coAM,
as proven in [For87, AH91], where AM denotes the class of problems admitting two-message
classical interactive proof systems in which the first message (from the verifier) consists solely of
(public) random coins. Moreover, the corresponding time complexity is
exponentially improved with respect to the state dimension. 4
This distinction appears fundamental and challenging to close: even combining the SDPbased approach of [MY23] with the space-efficient QSVT from [LLW25] still requires at least
quantum quadratic space to approximately implement the honest prover’s strategy in the general
case. A more intriguing question concerns the classical upper bound for QSZK, whose best known
bound is PSPACE and is believed “almost certainly can be improved” in [Wat02, Section 7]:
(b) Could the classical upper bounds for QSZK and NIQSZK be improved to any subclass of
PSPACE? As noted at the beginning of this section, the classical upper bound PSPACE for complexity
classes ranging from QSZK to QIP [Wat02, JUW09, JJUW11] is obtained via NC(poly) algorithms for the corresponding problems. 10
Noting that the notion of honest-prover efficiency in our results (Theorems 1. 3)
appears specifically tailored for two-message quantum interactive proof systems, the distinction
between our results and the general case suggests the following question:
(c) Could the honest prover’s strategy in any two-message quantum interactive proof system be
approximately implemented in quantum linear space, meaning that the space complexity
of the algorithmic implementation scales linearly with the number of qubits on which the
verifier’s message-preparing circuit acts? As a consequence, our resulting time complexity is 2
O(n) = poly(N), while theirs is
2
p(n) = Nq(n)
for some functions p(n) and q(n) := p(n)/n that are both polynomial in n. Beyond the algorithmic perspective, it is worth noting that a stability result of the Uhlmann
transform, referred to as “robust rigidity”, has been recently investigated in [BMY26].Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Closeness testing problems based on the trace distance
The paper establishes new bounds for closeness testing problems. Corollary 4. p. 3 The main result of this work follows directly from
combining Theorems 1. 3:
Corollary 1. For b ∈ {0, 1}, let ρb denote the quantum state obtained by
applying Qb to the initial state |0⟩
⊗n and tracing out the non-output qubits. Let α(n) and β(n)
be efficiently computable functions.Where the paper says it
Where the paper says it
Conclusion on complexity bounds
The final results provide slightly improved upper bounds for specific problems. Theorem 4.7 shows that F2Est[α(n), β(n)] is in QIP(2) with a quantum O(n′) space honest prover. p. 0 Here, 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-QIP(2) denotes the complement of QIP(2). We slightly improve this upper bound to QIP(2)∩co-QIP(2) with a quantum linear-space
honest prover. As a consequence, our resulting time complexity is 2
O(n) = poly(N), while theirs is
2
p(n) = Nq(n)
for some functions p(n) and q(n) := p(n)/n that are both polynomial in n. Beyond the algorithmic perspective, it is worth noting that a stability result of the Uhlmann
transform, referred to as “robust rigidity”, has been recently investigated in [BMY26]. 6 (Informal version of Theorem 3. For quantum states ρ0 and ρ1 specified in
GapQSD, whose purifications can be prepared by n-qubit polynomial-size quantum circuits Q0
and Q1, the Holevo–Helstrom measurement {Π0, Π1} can be approximately implemented in quantum single-exponential time and linear space with additive error 2
−n
. From this perspective, the notion of
linearity should be defined in terms of the underlying proof system, which motivates our choice
to measure it by the transcript of the original proof system, whose size has the same order as
the verifier’s message length in the resulting two-message proof systems. 2 Revisiting the upper bound QIP(2) ∩ co-QIP(2)
Before explaining the proofs of Theorems 1.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Quantum Statistical Zero-Knowledge (QSZK) systems can be implemented with an honest prover that uses space linear in the size of the transcript of a QSZK proof system, leading to a quantum singleexponential time complexity for specific two-message interactive proof systems.
-
The algorithmic Holevo–Helstrom measurement can be implemented in quantum singleexponential time and linear space with an additive error of 2 to the power of minus n for GapQSD, which implies that GapQSD is in QIP(2) with a quantum O(n prime) space honest prover.
-
The algorithmic Uhlmann transform can be implemented in quantum singleexponential time and linear space with an additive error of 2 to the power of minus n for GapF2Est, which implies that GapF2Est is in QIP(2) with a quantum O(n prime) space honest prover.
-
The resulting QSZK class can be characterized as being in QIP(2) intersect co-QIP(2), with the space complexity of the honest prover being linear in the size of the transcript in the original QSZK proof system.
-
Non-interactive quantum statistical zero-knowledge (NIQSZK) can be implemented with a quantum linear space honest prover, leading to a qq-QAM containment where the space complexity is linear in the size of the transcript.
Abstract
The complexity class Quantum Statistical Zero-Knowledge, introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound co-, which was simplified following the inclusion established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, 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- denotes the complement of. We slightly improve this upper bound to co- with a quantum linear-space honest prover. Specifically, the honest prover uses space linear in the size of the transcript of the original proof system. A similar improvement also applies to the upper bound for the non-interactive variant. 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).
Sources
- A Polynomial Quantum Algorithm for Approximating the Jones Polynomial
- Simulating Hamiltonian dynamics with a truncated Taylor series
- Unitary Complexity and the Uhlmann Transformation Problem
- The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
- Local transformations of bipartite entanglement are rigid
- New Results on Quantum Property Testing
- Increasing the power of the verifier in Quantum Zero Knowledge
- A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting
- Cryptographic Distinguishability Measures for Quantum Mechanical States
- A Complete Characterization of Unitary Quantum Space
- Towards a quantum-inspired proof for IP = PSPACE
- Improved Quantum Algorithms for Fidelity Estimation
- Quantum Logspace Computations are Verifiable
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
- QIP = PSPACE
- Two-message quantum interactive proofs are in PSPACE
- Tutorial on the Quantikz Package
- Quantum measurements and the Abelian Stabilizer Problem
- Using Entanglement in Quantum Multi-Prover Interactive Proofs
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements