Space-bounded quantum interactive proof systems

François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang

Abstract

We introduce two models of space-bounded quantum interactive proof systems, ${\sf QIPL}$ and ${\sf QIP_{\rm U}L}$. The ${\sf QIP_{\rm U}L}$ model, a space-bounded variant of quantum interactive proofs (${\sf QIP}$), restricts verifier actions to unitary circuits. In contrast, ${\sf QIPL}$ allows logarithmically many pinching intermediate measurements per verifier action, making it the weakest model that encompasses the classical model of Condon and Ladner. We characterize the computational power of these classes, showing that while ${\sf QIP_{\rm U}L}$ is contained in ${\sf P}$, ${\sf QIPL}$ can solve ${\sf NP}$ problems. We also prove that space-bounded unitary quantum statistical zero-knowledge (${\sf QSZK_{\rm U}L}$) is exactly equal to ${\sf BQL}$, implying that the statistical zero-knowledge property negates the computational advantage typically gained from interaction.

Introduction

In computational complexity, Interactive Proofs (IP) involve a powerful prover attempting to convince a resource-constrained verifier of a statement's truth. While polynomial-time quantum verifiers are known to be extremely powerful (${\sf QIP} = {\sf PSPACE}$), the constraints of near-term quantum hardware motivate the study of space-bounded models. This paper investigates the computational power of quantum interactive proofs when the verifier is restricted to logarithmic space (logspace).

A central question in this domain is the role of intermediate measurements. In standard quantum logspace computation, allowing measurements (${\sf BQL}$) does not increase power over the unitary-only model (${\sf BQ_{\rm U}L}$). However, this research demonstrates that this equivalence breaks down in the presence of an interactive prover.

Defining the Models: $QIPL$ vs. $QIP_UL$

The authors define two primary complexity classes to explore this "measurement gap":

  1. ${\sf QIPL}$: Space-bounded quantum interactive proofs where the verifier can perform "pinching" intermediate measurements.
  2. ${\sf QIP_{\rm U}L}$: A unitary variant where the verifier's actions are restricted to reversible, unitary circuits until the final measurement.
Schematic of a space-bounded quantum interactive proof system (${\sf QIPL}$) showing interaction between Prover ($Q$), Message ($M$), and Verifier ($W$), including intermediate measurements $E_i$.

The inclusion of intermediate measurements in ${\sf QIPL}$ allows the verifier to "force" the prover to provide classical information, a capability that proves crucial for solving complex problems like 3-SAT.

Main Complexity Results

The study establishes a clear hierarchy and characterization for these classes based on the number of messages exchanged and the "gap" between acceptance probabilities for true and false statements.

Summary of complexity results for various space-bounded quantum interactive proof models under different message counts and gap conditions.

Key findings include:

  • The Power of Measurements: When the number of messages is polynomial, ${\sf QIPL}$ (specifically the high-concentration variant ${\sf QIPL^{HC}}$) is equivalent to ${\sf NP}$. This shows that intermediate measurements uniquely empower space-bounded interactive proofs.
  • Unitary Limitations: In contrast, ${\sf QIP_{\rm U}L}$ is contained within ${\sf P}$ and contains ${\sf SAC}^1 \cup {\sf BQL}$. This implies ${\sf QIP_{\rm U}L} \subsetneq {\sf QIPL}$ unless ${\sf P} = {\sf NP}$.
  • Constant Message Convergence: If the protocol is restricted to a constant number of messages, the distinction between measurement-based and unitary models disappears, with both residing in ${\sf NC}$.

Zero-Knowledge and Interaction Collapse

The authors also explore space-bounded unitary quantum statistical zero-knowledge (${\sf QSZK_{\rm U}L}$). They prove a "collapse" result: ${\sf QSZK_{\rm U}L} = {\sf BQL}$. This indicates that if a proof is required to be zero-knowledge (leaking no information beyond the statement's validity), the interaction with the prover becomes computationally useless; the verifier can achieve the same result independently.

Conclusion and Future Directions

This work highlights that pinching intermediate measurements are a fundamental resource in space-bounded quantum interaction, unlike in standard quantum computation. Future research may focus on characterizing the general ${\sf QIPL}$ class without high-concentration assumptions, tightening the bounds for ${\sf QIP_{\rm U}L}$, and extending these constraints to multi-prover systems (${\sf MIP}$).

Summary updated

Abstract

We introduce two models of space-bounded quantum interactive proof systems, ${\sf QIPL}$ and ${\sf QIP_{\rm U}L}$. The ${\sf QIP_{\rm U}L}$ model, a space-bounded variant of quantum interactive proofs (${\sf QIP}$) introduced by Watrous (CC 2003) and Kitaev and Watrous (STOC 2000), restricts verifier actions to unitary circuits. In contrast, ${\sf 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 ${\sf QIPL}$ and ${\sf QIP_{\rm U}L}$. When the message number $m$ is polynomially bounded, ${\sf QIP_{\rm U}L} \subsetneq {\sf QIPL}$ unless ${\sf P} = {\sf NP}$: - ${\sf QIPL}$ contains ${\sf NP}$ and is contained in ${\sf SBP}$, which is a subclass of ${\sf AM}$. - ${\sf QIP_{\rm U}L}$ is contained in ${\sf P}$ and contains ${\sf SAC}^1 \cup {\sf BQL}$, where ${\sf SAC}^1$ 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 ${\sf BQL}={\sf BQ_{\rm U}L}$. We also introduce space-bounded unitary quantum statistical zero-knowledge (${\sf QSZK_{\rm U}L}$), a specific form of ${\sf QIP_{\rm U}L}$ proof systems with statistical zero-knowledge against any verifier. This class is a space-bounded variant of quantum statistical zero-knowledge (${\sf QSZK}$) defined by Watrous (SICOMP 2009). We prove that ${\sf QSZK_{\rm U}L} = {\sf BQL}$, implying that the statistical zero-knowledge property negates the computational advantage typically gained from the interaction.
BibTeX
@article{gall2024space,
  author = {François Le Gall and Yupan Liu and Harumichi Nishimura and Qisheng Wang},
  title = {{Space-bounded quantum interactive proof systems}},
  journal = {Electron. Colloquium Comput. Complex.},
  year = {2024},
  url = {https://openreview.net/forum?id=4CCfp7F6yR},
}
Figure