Space-bounded quantum interactive proof systems

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

TL;DR

This paper explores what happens when you restrict a quantum verifier to "logspace"—using only a logarithmic number of qubits—within an interactive proof system. The authors discover a surprising "measurement gap": unlike standard quantum computation where intermediate measurements don't add power, in space-bounded interactive proofs, allowing measurements makes the system as powerful as NP, while restricting the verifier to unitary actions keeps it within P.

What Problem Does This Paper Address?

In computational complexity, Interactive Proofs (IP) involve a powerful "prover" trying to convince a resource-constrained "verifier" that a statement is true. We know that with a polynomial-time quantum verifier, these systems are incredibly powerful ($QIP = PSPACE$).

However, we are entering an era of "near-term" quantum devices where memory (qubits) is the scarcest resource. This paper asks: What is the computational power of quantum interactive proofs when the verifier is restricted to logarithmic space?

Specifically, the authors tackle a subtle but vital question: Does it matter if the verifier can perform measurements during the protocol? In standard quantum logspace computation, we know that $BQL$ (with measurements) is equal to $BQUL$ (unitary only). This paper investigates whether that equivalence holds up when a prover is added to the mix.

Methods

The authors define two new complexity classes:

  1. QIPL: Space-bounded quantum interactive proofs where the verifier can perform "pinching" intermediate measurements.
  2. QIPUL: A "unitary" variant where the verifier's actions are restricted to reversible, unitary circuits until the very end.

To characterize these classes, they employ several heavy-hitting theoretical tools:

  • Semi-Definite Programming (SDP): They formulate the maximum acceptance probability of the verifier as an SDP. Since the verifier only uses $O(\log n)$ qubits, the resulting SDP has polynomial dimensions, allowing them to prove upper bounds (like $QIP_UL \subseteq P$).
  • The Turn-Halving Lemma: A technique to parallelize interactive protocols, reducing the number of messages exchanged without losing too much "gap" between a true statement and a false one.
  • Fingerprinting: They adapt classical fingerprinting techniques to show that NP problems (like 3-SAT) can be solved in the $QIPL$ model.

Datasets

Not discussed in the paper. As a theoretical complexity paper, the "data" consists of mathematical proofs and reductions between complexity classes rather than empirical datasets.

Key Insights and Ideas

  • The Power of Pinching: The most striking finding is that intermediate measurements uniquely impact space-bounded interactive proofs. Allowing measurements ($QIPL$) allows the verifier to "force" the prover to send classical information, which helps the verifier check NP-complete problems.
  • Unitary Weakness: Without intermediate measurements ($QIP_UL$), the verifier is stuck in P. This implies that $QIP_UL \subsetneq QIPL$ unless $P = NP$.
  • Zero-Knowledge Collapse: The authors introduce QSZK_UL (Space-bounded Unitary Quantum Statistical Zero-Knowledge). They prove that this class is exactly equal to BQL. In plain English: if you require the proof to be zero-knowledge (leaking no info other than the truth of the statement), the "interaction" becomes useless—the verifier can't learn anything more than they could have computed alone.
  • Constant Message Convergence: If the protocol only involves a constant number of messages (e.g., 3 turns), the distinction between the measurement-based and unitary models disappears.

Key Results

  • $QIPL^{HC} = NP$: A specific subclass of $QIPL$ (with a "high-concentration" condition on successful outcomes) perfectly characterizes the class of problems solvable in non-deterministic polynomial time.
  • $QIP_UL \subseteq P$: Unitary space-bounded verifiers are strictly limited to problems solvable in polynomial time.
  • $QSZK_UL = BQL$: Statistical zero-knowledge in this setting negates the advantage of having a prover.
  • Hierarchy: The paper establishes a clear hierarchy: $SAC^1 \cup BQL \subseteq QIP_UL \subseteq P$.

Limitations and Future Work

  • The General QIPL Case: The authors characterize $QIPL^{HC}$ (high concentration), but the power of general $QIPL$ (where the verifier's measurement outcomes might be highly varied) remains an open question. It is possible it could be even more powerful than NP.
  • Tightening the Bounds: While they show $QIP_UL$ is in P, they haven't yet proven it is equal to a specific known class. Finding a matching lower bound is a natural next step.
  • Multi-Prover Systems: This work focuses on a single prover. Extending these space constraints to systems with multiple non-communicating provers ($MIP$) could reveal even more about the interplay between memory and interaction.

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

Loading related content...

Figure