A slightly improved upper bound for quantum statistical zero-knowledge

arXiv:2512.11597 · quant-ph, cs.CC, cs.IT, math.IT · Submitted 2025-12-12 · Read on arXiv

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

Where the paper says it

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).

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

Where the paper says it

3: Corollary 1. p. 3

Where the paper says it

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.

This means 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. p. 3
Where the paper says it

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.

Furthermore, a non-interactive variant called NIQSZK is also shown to be in qq-QAM with a quantum linear-space (and thus single-exponentialtime) honest prover. p. 3
Where the paper says it

3 also yields the following: Corollary 1. NIQSZK is in qq-QAM with a quantum linear-space (and thus single-exponentialtime) honest prover.

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

Where the paper says it

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.

The algorithmic Uhlmann transform is used for GapF2Est ∈ QIP(2) with a quantum linear-space honest prover. p. 6
Where the paper says it

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 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

Where the paper says it

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).

Specifically, a degree d′ = O(d) is kept explicit to distinguish the space-efficient version. p. 5
Where the paper says it

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.

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

Where the paper says it

3: Corollary 1. QSZK is in QIP(2) ∩ co-QIP(2) with a quantum linear-space (and thus singleexponential-time) honest prover.

Similarly, Corollary 1. p. 3
Where the paper says it

The main result of this work follows directly from combining Theorems 1. 3: Corollary 1.

5 shows that NIQSZK is in qq-QAM with a quantum linear-space (and thus single-exponentialtime) honest prover. p. 3
Where the paper says it

3 also yields the following: Corollary 1. NIQSZK is in qq-QAM with a quantum linear-space (and thus single-exponentialtime) honest prover.

These inclusions are viewed as transformations from one class of quantum interactive proof systems to another class with distinct structural features. p. 4
Where the paper says it

systems (e. , proof systems with the statistical zero-knowledge property) to another class with distinct structural features (e.

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

Where the paper says it

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?

Another intriguing question is whether the classical bounds for QSZK and NIQSZK could be improved to any subclass of PSPACE. p. 7
Where the paper says it

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?

A third open question focuses on whether the honest prover’s strategy in any two-message quantum interactive proof system can be approximately implemented in quantum linear space. p. 7
Where the paper says it

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?

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

Where the paper says it

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.

It also discusses the distinction between their results and the general case, suggesting that combining existing methods still requires at least quadratic quantum space. p. 3
Where the paper says it

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.

The work is situated within a broader context of complexity classes such as PSPACE [Wat02, JUW09, JJUW11]. p. 7
Where the paper says it

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.

It also touches upon notions of honest-prover efficiency, contrasting the current results with the requirement for quadratic quantum space in general two-message quantum interactive proof systems. p. 7
Where the paper says it

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?

The paper also notes that a stability result of the Uhlmann transform, referred to as “robust rigidity”, has been recently investigated. p. 8
Where the paper says it

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].

Closeness testing problems based on the trace distance

The paper establishes new bounds for closeness testing problems. Corollary 4. p. 3

Where the paper says it

The main result of this work follows directly from combining Theorems 1. 3: Corollary 1.

9 shows that for any efficiently computable functions α(n) and β(n) satisfying α 2(n) − β(n) ≥ 1/O(log n), QSC[β(n), α(n)] is in QIP(2) with a quantum O(n′) space honest prover. p. 9
Where the paper says it

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.

This result is derived by constructing a new pair of quantum states ρ'0 and ρ'1 whose purifications are also efficiently preparable and for which either T(ρ'0, ρ'1) ≤ 1/6 or T(ρ'0, ρ'1) ≥ 5/6.

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

Where the paper says it

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.

This result is achieved by using the algorithmic Uhlmann transform U˜⋆ from Theorem 4. p. 8
Where the paper says it

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].

5, which is implementable in quantum single-exponential time and linear space. p. 5
Where the paper says it

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 .

The paper concludes that the resulting bound for F2Est[α(n), β(n)] satisfies c(n) = α(n) − 2-n and s(n) = β(n). p. 4
Where the paper says it

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.

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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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

Related papers