Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-167 | 11th February 2025 16:38

Space-bounded quantum interactive proof systems

RSS-Feed




Revision #1
Authors: François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang
Accepted on: 11th February 2025 16:38
Downloads: 14
Keywords: 


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 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 $\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}$ contains $\mathbf{NP}$ and is contained in $\mathbf{SBP}$, which is a subclass of $\mathbf{AM}$.

- $\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 (pinching) 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.



Changes to previous version:

The high-concentration condition is removed from the definition of QIPL, with the new upper bound being SBP.


Paper:

TR24-167 | 31st October 2024 04:49

Space-bounded quantum interactive proof systems


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