Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-167 | 31st October 2024 04:49

Space-bounded quantum interactive proof systems

RSS-Feed

Abstract:

We introduce two models of space-bounded quantum interactive proof systems, $\mathbf{QIPL}$ and $\mathbf{QIP_\mathrm{U}L}$. The $\mathbf{QIP_\mathrm{U}L}$ model, a space-bounded variant of quantum interactive proofs ($\mathbf{QIP}$) introduced by Watrous (CC 2003) and Kitaev and Watrous (STOC 2000), restricts verifier actions to unitary circuits. In contrast, $\mathbf{QIPL}$ allows logarithmically many intermediate measurements per verifier action (with a high-concentration condition on yes instances), making it the weakest model that encompasses the classical model of Condon and Ladner (JCSS 1995).

We characterize the computational power of $\mathbf{QIPL}$ and $\mathbf{QIP_\mathrm{U}L}$. When the message number $m$ is polynomially bounded, $\mathbf{QIP_\mathrm{U}L}$ is strictly contained in $\mathbf{QIPL}$ unless $\mathbf{P} = \mathbf{NP}$:

- $\mathbf{QIPL}$ exactly characterizes $\mathbf{NP}$.

- $\mathbf{QIP_\mathbf{U}L}$ is contained in $\mathbf{P}$ and contains $\mathbf{SAC}^1 \cup \mathbf{BQL}$, where $\mathbf{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 intermediate measurements uniquely impact space-bounded quantum interactive proofs, unlike in space-bounded quantum computation, where $\mathbf{BQL}=\mathbf{BQ_\mathrm{U}L}$.

We also introduce space-bounded unitary quantum statistical zero-knowledge ($\mathbf{QSZK_\mathrm{U}L}$), a specific form of $\mathbf{QIP_\mathrm{U}L}$ proof systems with statistical zero-knowledge against any verifier. This class is a space-bounded variant of quantum statistical zero-knowledge ($\mathbf{QSZK}$) defined by Watrous (SICOMP 2009). We prove that $\mathbf{QSZK_\mathrm{U}L} = \mathbf{BQL}$, implying that the statistical zero-knowledge property negates the computational advantage typically gained from the interaction.



ISSN 1433-8092 | Imprint