Space-bounded quantum interactive proof systems
Yupan Liu | Nagoya University
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^1 ∪ BQL, where 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 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.
(Joint work with François Le Gall, Harumichi Nishimura, and Qisheng Wang, to appear in CCC 2025)
Location
-
QNC 1201
-
-
Meeting ID: 992 9848 9587
Passcode: 153212
-