Space-Bounded Quantum Interactive Proof Systems

The exploration of classical interactive proof systems (IP) was initiated in the 1980s [4, 29]. In these proof systems, the verifier is typically bounded by polynomial time, and $\text{IP}[m]$ represents interactive protocols involving $m$ messages during interactions. Particularly, when the verifier’s messages are merely random bits, these public-coin proof systems are known as Arthur-Merlin proof systems [4]. Shortly thereafter, it was established that any constant-message IP protocol can be parallelized to a two-message public-coin protocol, captured by the class AM, and thus $\text{IP}[O(1)]$ is contained in the second level of the polynomial-time hierarchy [4, 30]. However, IP protocols with a polynomial number of messages have been shown to be exceptionally powerful, as demonstrated by the seminal result $\text{IP}=\text{PSPACE}$ [46, 56]. Consequently, IP protocols with a polynomial number of messages generally cannot be parallelized to a constant number of messages unless the polynomial-time hierarchy collapses.¹¹1The assumption that the polynomial-time hierarchy does not collapse generalizes the conjecture that $\text{P}⊊\text{NP}$.

About fifteen years after the introduction of interactive proof systems (and a model of quantum computation), the study of quantum interactive proof systems (QIP) began [63]. Remarkably, any QIP protocol with a polynomial number of messages can be parallelized to three messages [37]. A quantum Arthur-Merlin proof system was subsequently introduced in [47], and any three-message QIP protocol can be transformed into this form (QMAM). By the late 2000s, the computational power of QIP was fully characterized: The celebrated result $\text{QIP}=\text{PSPACE}$ [35] established that QIP is not more powerful than IP as long as the gap $c-s$ is at least polynomially small. However, when the gap $c-s$ is double-exponentially small, this variant of QIP is precisely characterized by EXP [33]. In the late 2010s, another quantum counterpart of the Arthur-Merlin proof system was considered in [39], where the verifier’s message is either random bits or halves of EPR pairs, leading to a quadrichotomy theorem that classifies the corresponding QIP protocols.

The investigation of (classical) interactive proof systems with space-bounded verifiers started in the late 1980s [16, 8], alongside research on time-bounded verifiers. Notably, by using the fingerprinting lemma [44], Condon and Ladner [10] showed that the class of (private-coin) classical interactive proof systems with logarithmic-space verifiers using $O(\log n)$ random bits exactly characterizes NP. In parallel, public-coin space-bounded classical interactive proofs were explored in the early 1990s [21, 20, 9]. By around 2010, it was established that such space-bounded protocols with $\mathrm{poly}(n)$ public coins precisely characterize P [28].

Space-bounded Merlin-Arthur-type proof systems were also studied in the early 1990s. In particular, when the verifier operates in classical logspace with $O(\log n)$ random bits and has online access to a $\mathrm{poly}(n)$-bit message, the proof system exactly characterizes NP [44]. More recently, restricting the computational power of the honest prover to quantum logspace (BQL) has led to a counterpart classical proof system that exactly characterizes BQL [27].

Although research has been conducted on quantum interactive proofs where the verifier uses quantum finite automata [51, 52, 67], analogous to classical work [16], to our knowledge no prior work has addressed space-bounded counterparts of quantum interactive proofs that align with the circuit-based model defined in [37, 63]. In the case without interaction, space-bounded quantum Merlin-Arthur proof systems have been studied recently. When the verifier has direct access to an $O(\log n)$-qubit message, meaning it can process the message directly in its workspace qubits, this variant (QMAL) is as weak as BQL [17, 19]. However, when the (unitary) verifier has online access to a $\mathrm{poly}(n)$-qubit message, where each qubit in the message state is read-once, this variant is as strong as QMA [24].²²2An exponentially up-scaled quantum counterpart of the space-bounded Merlin-Arthur-type proof system from [44], with classical messages, was also considered in [24]. The variant with unitary quantum polynomial-space verifier, implicitly allowing $\mathrm{poly}(n)$ random bits, precisely corresponds to NEXP.

It is important to note that online and direct access to messages during interactions makes no difference for time-bounded interactive or Merlin-Arthur-type proof systems, whether classical or quantum. This distinction arises from the nature of space-bounded computation.

We introduce space-bounded quantum interactive proof systems and their unitary variant, denoted as QIPL and QIP_UL, respectively. In these proof systems, the verifier $V$ operates in quantum logspace and has direct access to messages during interaction with the prover $P$. Specifically, in a $2l$-turn (message) space-bounded quantum interactive proof system for a promise problem $({ℐ}_{\mathrm{yes}},{ℐ}_{\mathrm{no}})$, this proof system $P\rightleftharpoons V$ consists of the prover’s private register $𝖰$, the message register $𝖬$, and the verifier’s private register $𝖶$. Both $𝖬$ and $𝖶$ are of size $O(\log n)$, with $𝖬$ being accessible to both the prover and the verifier.³³3Our definitions of QIPL and QIP_UL can be straightforwardly extended to the corresponding proof systems with an odd number of messages, as shown in [41, Figure 4.1].

The verifier $V$ maps an input $x\in {ℐ}_{\mathrm{yes}}\cup {ℐ}_{\mathrm{no}}$ to a sequence $(V_1,\mathrm{\cdots },V_{l+1})$, with $V_j$ for $j\in [l]$ representing the verifier’s actions at the $(2j-1)$-th turn, and $V_{l+1}$ representing the verifier’s action just before the final measurement. The primary difference between QIPL and QIP_UL proof systems lies in the verifier’s action $V_j$ for $j\in [l]$:

• $\mathrm{■}$

  In QIPL proof systems, each $V_j$ corresponds to an almost-unitary quantum circuit ${\tilde{V}}_j$ that includes $O(\log n)$ pinching intermediate measurements in the computational basis.⁴⁴4We note that restricting the number of pinching measurements in each verifier turn $V_j$ from polynomial in $n$ to $O(\log n)$ does not cause any loss of generality, provided that the QIPL proof system has a polynomial number of turns. See [41, Remark 3.5] for further details. Each such measurement maps a single-qubit state $\rho$ to ${\sum }_{b\in \{0,1\}}\mathrm{Tr}(|b⟩⟨b|\rho )|b⟩⟨b|$.⁵⁵5Pinching intermediate measurements naturally arise in space-bounded quantum computation, particularly in recent developments on eliminating intermediate measurements in quantum logspace [26, 25]. In this context, the quantum channels that capture the space-bounded computation are unital in the case of qubits. The $O(\log n)$ bound reflects the maximum number of measurement outcomes that can be stored in logspace, aligning with the verifier’s direct access to the message. For convenience, we apply the principle of deferred measurements (e.g., [50, Section 4.4]), transforming the circuit ${\tilde{V}}_j$ into an isometric quantum circuit $V_j$ with a newly introduced environment register ${𝖤}_j$,⁶⁶6An $O(\log n)$-qubit isometric quantum circuit utilizes $O(\log n)$ ancillary gates, with each ancillary gate introducing an ancillary qubit $|0⟩$. For further details, please refer to [41, Definition 2.8]. which is measured at the end of that turn, with the measurement outcome denoted by $u_j$, as illustrated in Figure 1. Furthermore, each environment register ${𝖤}_j$ remains private to the verifier and becomes inaccessible after the round that starts with the verifier’s $j$-th action.

• $\mathrm{■}$

  In QIP_UL proof systems, each $V_j$ is a unitary quantum circuit.

The prover’s actions can be similarly described by unitary quantum circuits. A proof system $P\rightleftharpoons V$ is said to accept if, after the verifier performs $V_{l+1}$ and measures the designated output qubit in the computational basis, the outcome is $1$. Additionally, we require a strong notion of uniformity for the verifier’s mapping: the description of the sequence $(V_1,\mathrm{\cdots },V_{l+1})$ must be computable by a single deterministic logspace Turing machine.⁷⁷7A weaker notion of uniformity only requires that the description of each $V_j$ can be individually computed by a deterministic logspace Turing machine. It is important to note that these distinctions do not arise in the time-bounded setting, as the composition of a polynomial number of deterministic polynomial-time Turing machines can be treated as a single deterministic polynomial-time Turing machine.

Lastly, for QIPL^HC proof systems, we impose an additional restriction on yes instances: the distribution of intermediate measurement outcomes $u=(u_1,\mathrm{\cdots },u_l)$, conditioned on acceptance, must be highly concentrated. More precisely, let $\omega (V){|}^u$ be the contribution of $u$ to $\omega (V)$, where $\omega (V)$ is the maximum acceptance probability of $P\rightleftharpoons V$. Then, there must exist a $u^{\ast }$ such that $\omega (V){|}^{u^{\ast }}\ge c(n)$.

We denote $m$-turn space-bounded quantum interactive proof systems with completeness $c$ and soundness $s$ as ${\text{QIPL}}_m[c,s]$, and their unitary variant as ${\text{QIP}\text{<sub class="ltx\_sub">U</sub>}\text{L}}_m[c,s]$. In particular, we adopt the following notations, which naturally extend to QIP_UL:

In constant-turn scenarios, it is crucial to emphasize that the proof systems ${\text{QIPL}}_{O(1)}[c,s]$ and ${\text{QIP}\text{<sub class="ltx\_sub">U</sub>}\text{L}}_{O(1)}[c,s]$ can directly simulate each other, as the environment registers ${𝖤}_1,\mathrm{\cdots },{𝖤}_{O(1)}$ collectively holds $O(\log n)$ qubits.⁸⁸8This equivalence follows directly from the principle of deferred measurements. However, for constant-turn space-bounded quantum interactive proofs, allowing each verifier action to involve $\mathrm{poly}(n)$ pinching intermediate measurements might increase the proof system’s power beyond the unitary case. This is because current techniques for proving results such as $\text{BQL}=\text{BQ}\text{<sub class="ltx\_sub">U</sub>}\text{L}$ [19, 26, 25] do not directly apply in this context. Therefore, for simplicity, we define ${\text{QIPL}}_{O(1)}[c,s]$ proof systems in which the verifier’s actions are implemented by unitary quantum circuits.

Our first theorem serves as a quantum analog of the classical work by Condon and Ladner [10]:

Interestingly, Theorem 1 suggests that the QIPL^HC model can be viewed as the weakest model that encompasses space-bounded (private-coin) classical interactive proofs, as considered in [10]. Our definitions of QIPL and its subclass QIPL^HC aim to introduce quantum counterparts that include these classical proof systems, ensuring that soundness against classical messages also holds for quantum messages. Similar soundness issues challenged multi-prover scenarios (e.g., proving $\mathrm{𝖬𝖨𝖯}\subseteq {\mathrm{𝖬𝖨𝖯}}^{\ast }$) for nearly a decade [7, 34], while in the single-prover settings (e.g., proving $\text{IP}\subseteq \text{QIP}$), it is typically resolved by measuring the prover’s quantum messages and treating the outcomes as classical messages (e.g., [1, Claim 1]).

However, space-bounded unitary quantum interactive proofs (QIP_UL), which denote the most natural space-bounded counterpart to quantum interactive proofs as defined in [37, 64], do not directly achieve the stated soundness guarantee. Hence, QIP_UL may be computationally weaker than QIPL. Our second theorem characterizes the computational power of QIP_UL:

Theorems 1 and 2 suggest that QIP_UL is indeed weaker than QIPL unless $\text{P}=\text{NP}$. Interestingly, this distinction from the unitary case arises even when each verifier action is slightly more powerful than a unitary quantum circuit. It is also noteworthy that the class ${\text{SAC}}^1$ is equivalent to LOGCFL [59], which contains NL and is contained in ${\text{AC}}^1$.⁹⁹9For more details on the computational power of ${\text{SAC}}^1$ and related complexity classes, see [41, Section 2.4]. Our third theorem, meanwhile, focuses on space-bounded quantum interactive proof systems with a constant number of messages:

To compare with time-bounded classical or quantum interactive proofs, we summarize our three theorems in Table 1. Notably, our two models of space-bounded quantum interactive proofs, QIPL and QIP_UL, demonstrate behavior that is distinct from both:

• $\mathrm{■}$

  For (time-bounded) classical interactive proofs, all proof systems with $m\le O(1)$ (the regime of the last row in Table 1) are contained in the second level of the polynomial-time hierarchy [4, 30], whereas the class of proof systems with $m=\mathrm{poly}(n)$ (the regime of the second and third rows in Table 1) exactly characterizes PSPACE [46, 56].

• $\mathrm{■}$

  For (time-bounded) quantum interactive proofs, all proof systems with parameters listed in Table 1 precisely capture PSPACE [63, 37, 35].

The central intuition underlying Table 1 is that parallelization [37, 36], perhaps the most striking complexity-theoretic property of QIP proof systems, distinguishes QIP_UL from QIPL. Quantum logspace operates within a polynomial-dimensional Hilbert space, remaining computationally weak even with a constant number of interactions, and is (at least) contained in P. In QIP_UL, the verifier’s actions are reversible and dimension-preserving, allowing direct application of parallelization techniques from [36]. In contrast, QIPL and its reversible generalization lack dimension preservation, requiring significantly more than $O(\log n)$ space to parallelize the verifier’s actions, which prevents parallelization.

We also introduce (honest-verifier) space-bounded unitary quantum statistical zero-knowledge, denoted as QSZK_UL_HV. This term refers to a specific form of space-bounded quantum proofs that possess statistical zero-knowledge against an honest verifier. Specifically, a space-bounded unitary quantum interactive proof system possesses this zero-knowledge property if there exists a quantum logspace simulator that approximates the snapshot states (“the verifier’s view”) on the registers $𝖬$ and $𝖶$ after each turn of this proof system, where each state approximation must be very close (“indistinguishable”) to the corresponding snapshot state with respect to the trace distance.

Our definition QSZK_UL_HV serves as a space-bounded variant of honest-verifier (unitary) quantum statistical zero-knowledge, denoted by QSZK_HV, as introduced in [62]. Our fourth theorem establishes that the statistical zero-knowledge property completely negates the computational advantage typically gained through the interaction:

In addition to QSZK_UL_HV, we can define QSZK_UL in line with [65], particularly considering space-bounded unitary quantum statistical zero-knowledge against any verifier (rather than an honest verifier). Following this definition, $\text{BQL}\subseteq \text{QSZK}\text{<sub class="ltx\_sub">U</sub>}\text{L}\subseteq \text{QSZK}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_serif">U</span></sub>}\text{L}\text{<sub class="ltx\_sub">HV</sub>}$. Interestingly, Theorem 4 serves as a direct space-bounded counterpart to $\text{QSZK}=\text{QSZK}\text{<sub class="ltx\_sub">HV</sub>}$ [65].

The intuition behind Theorem 4 is that the snapshot states after each turn capture all the essential information in the proof system, such as allowing optimal prover strategies to be “recovered” from these states [48, Section 7]. In space-bounded scenarios, space-efficient quantum singular value transformation [42] enables fully utilizing this information.

Finally, we emphasize that our consideration of this zero-knowledge property is purely complexity-theoretic. A full comparison with other notions of (statistical) zero-knowledge is beyond this scope. For more on classical and quantum statistical zero-knowledge, see [58] and [60, Chapter 5].

We begin by outlining three basic properties of space-bounded (unitary) quantum interactive proof systems, which are dependent on the parameters $c(n)$, $s(n)$, and $m(n)$:

Achieving perfect completeness for QIPL and QIP_UL proof systems, particularly Theorem 51, can be adapted from the techniques used in QIP proof systems [60, Section 4.2.1] (or [37, Section 3]) by adding two additional turns. However, there are important subtleties to consider when establishing the other properties in Theorem 5.

We demonstrate Theorem 4 by introducing a QSZK_UL_HV-complete problem:

We begin by informally defining the promise problem Individual Product State Distinguishability, denoted by $\text{IndivProdQSD}[k(n),\alpha (n),\delta (n)]$, where the parameters satisfy $\alpha (n)-k(n)\cdot \delta (n)\ge 1/\mathrm{poly}(n)$ and $1\le k(n)\le \mathrm{poly}(n)$. This problem considers two $k$-tuples of $O(\log n)$-qubit quantum states, denoted by ${\sigma }_1,\mathrm{\cdots },{\sigma }_k$ and ${\sigma }_1^{\prime },\mathrm{\cdots },{\sigma }_k^{\prime }$, where the purifications of these states can be prepared by corresponding polynomial-size unitary quantum circuits acting on $O(\log n)$ qubits. For yes instances, these two $k$-tuples are “globally” far, satisfying

While for no instances, each pair of corresponding states in these $k$-tuples are close, satisfying

Then we show that (1) the complement of IndivProdQSD, $\overline{\text{IndivProdQSD}}$, is QSZK_UL_HV-hard; and (2) IndivProdQSD is in BQL, which is contained in QSZK_UL_HV by definition.