Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Logical Characterization of Quantum Statistical Zero-Knowledge (QSZK)

В. Г. Найденко

Published Jan 1, 2026• 0 citations
Publisher
DOI
10.13140/rg.2.2.19647.06562

Related papers

Statistical Zero Knowledge and quantum one-way functions

Elham Kashefi, Iordanis Kerenidis

arXiv:quant-ph/0511266•Theoretical Computer Science•Mar 13, 2007•24 citations

Non-interactive Quantum Perfect and Statistical Zero-Knowledge

Hirotada Kobayashi

Lecture notes in computer science•Jan 1, 2003•46 citations

Limits on the power of quantum statistical zero-knowledge

John Watrous

In this paper we propose a definition for (honest verifier) quantum statistical zero-knowledge interactive proof systems and study the resulting complexity class, which we denote QSZK/sub HV/. We prove several facts regarding this class, including: the following problem is a complete promise problem for QSZKHV: given instructions for preparing two mixed quantum states, are the states close together or far apart in the trace norm metric? This problem is a quantum generalization of the complete promise problem of Sahai and Vadhan (1997) for (classical) statistical zero-knowledge; QSZK/sub HV/ is closed under complement; QSZK/sub HV//spl sube/PSPACE. (At present it is not known if arbitrary quantum interactive proof systems can be simulated in PSPACE even for one-round proof systems); any polynomial-round honest verifier quantum statistical zero-knowledge proof system can be simulated by a two-message (i.e., one-round) honest verifier quantum statistical zero-knowledge proof system. Similarly, any polynomial-round honest verifier quantum statistical zero-knowledge proof system can be simulated by a three-message public-coin honest verifier quantum statistical zero-knowledge proof system. These facts establish close connections between classical statistical zero-knowledge and our definition for quantum statistical zero-knowledge, and give some insight regarding the effect of this zero-knowledge restriction on quantum interactive proof systems. The relationship between our definition and possible definitions of general (i.e., not necessarily honest) quantum statistical zero-knowledge are also discussed.

Annual Symposium on Foundations of Computer Science•Jun 26, 2003•141 citations

Space-Bounded Quantum Interactive Proof Systems

Le Gall, François, Liu, Yupan, Nishimura, Harumichi +1 more

We introduce two models of space-bounded quantum interactive proof systems, QIPL and QIP_{U}L. The QIP_{U}L model, a space-bounded variant of quantum interactive proofs (QIP) introduced by Watrous (CC 2003) and Kitaev and Watrous (STOC 2000), restricts verifier actions to unitary circuits. In contrast, QIPL allows logarithmically many pinching intermediate measurements per verifier action, making it the weakest model that encompasses the classical model of Condon and Ladner (JCSS 1995). We characterize the computational power of QIPL and QIP_{U}L. When the message number m is polynomially bounded, QIP_{U}L ⊊ QIPL unless P = NP: - QIPL^HC, a subclass of QIPL defined by a high-concentration condition on yes instances, exactly characterizes NP. - QIP_{U}L is contained in P and contains SAC¹ ∪ BQL, where SAC¹ denotes problems solvable by classical logarithmic-depth, semi-unbounded fan-in circuits. However, this distinction vanishes when m is constant. Our results further indicate that (pinching) intermediate measurements uniquely impact space-bounded quantum interactive proofs, unlike in space-bounded quantum computation, where BQL = BQ_{U}L. We also introduce space-bounded unitary quantum statistical zero-knowledge (QSZK_{U}L), a specific form of QIP_{U}L proof systems with statistical zero-knowledge against any verifier. This class is a space-bounded variant of quantum statistical zero-knowledge (QSZK) defined by Watrous (SICOMP 2009). We prove that QSZK_{U}L = BQL, implying that the statistical zero-knowledge property negates the computational advantage typically gained from the interaction.

arXiv:2410.23958•Leibniz international proceedings in informatics•Oct 31, 2024•3 citations

Quantum statistical zero-knowledge

John Watrous

In this paper we propose a definition for (honest verifier) quantum statistical zero-knowledge interactive proof systems and study the resulting complexity class, which we denote QSZK. We prove several facts regarding this class that establish close connections between classical statistical zero-knowledge and our definition for quantum statistical zero-knowledge, and give some insight regarding the effect of this zero-knowledge restriction on quantum interactive proof systems.

arXiv:quant-ph/0202111•Feb 20, 2002•34 citations

General Properties of Quantum Zero-Knowledge Proofs

Hirotada Kobayashi

arXiv:0705.1129•Springer eBooks•Feb 25, 2008•44 citations
In this paper we propose a definition for (honest verifier) quantum statistical zero-knowledge interactive proof systems and study the resulting complexity class, which we denote QSZK/sub HV/. We prove several facts regarding this class, including: the following problem is a complete promise problem for QSZKHV: given instructions for preparing two mixed quantum states, are the states close together or far apart in the trace norm metric? This problem is a quantum generalization of the complete promise problem of Sahai and Vadhan (1997) for (classical) statistical zero-knowledge; QSZK/sub HV/ is closed under complement; QSZK/sub HV//spl sube/PSPACE. (At present it is not known if arbitrary quantum interactive proof systems can be simulated in PSPACE even for one-round proof systems); any polynomial-round honest verifier quantum statistical zero-knowledge proof system can be simulated by a two-message (i.e., one-round) honest verifier quantum statistical zero-knowledge proof system. Similarly, any polynomial-round honest verifier quantum statistical zero-knowledge proof system can be simulated by a three-message public-coin honest verifier quantum statistical zero-knowledge proof system. These facts establish close connections between classical statistical zero-knowledge and our definition for quantum statistical zero-knowledge, and give some insight regarding the effect of this zero-knowledge restriction on quantum interactive proof systems. The relationship between our definition and possible definitions of general (i.e., not necessarily honest) quantum statistical zero-knowledge are also discussed.
We introduce two models of space-bounded quantum interactive proof systems, QIPL and QIP_{U}L. The QIP_{U}L model, a space-bounded variant of quantum interactive proofs (QIP) introduced by Watrous (CC 2003) and Kitaev and Watrous (STOC 2000), restricts verifier actions to unitary circuits. In contrast, QIPL allows logarithmically many pinching intermediate measurements per verifier action, making it the weakest model that encompasses the classical model of Condon and Ladner (JCSS 1995). We characterize the computational power of QIPL and QIP_{U}L. When the message number m is polynomially bounded, QIP_{U}L ⊊ QIPL unless P = NP: - QIPL^HC, a subclass of QIPL defined by a high-concentration condition on yes instances, exactly characterizes NP. - QIP_{U}L is contained in P and contains SAC¹ ∪ BQL, where SAC¹ denotes problems solvable by classical logarithmic-depth, semi-unbounded fan-in circuits. However, this distinction vanishes when m is constant. Our results further indicate that (pinching) intermediate measurements uniquely impact space-bounded quantum interactive proofs, unlike in space-bounded quantum computation, where BQL = BQ_{U}L. We also introduce space-bounded unitary quantum statistical zero-knowledge (QSZK_{U}L), a specific form of QIP_{U}L proof systems with statistical zero-knowledge against any verifier. This class is a space-bounded variant of quantum statistical zero-knowledge (QSZK) defined by Watrous (SICOMP 2009). We prove that QSZK_{U}L = BQL, implying that the statistical zero-knowledge property negates the computational advantage typically gained from the interaction.