Skip to content
Preprint

Quantum Interactive Proofs of Proximity

Nov 2026 · 0 citations
Computer Science

Abstract

We initiate the systematic study of quantum interactive proofs of proximity (QIPPs). These are quantum interactive proof systems with sublinear communication, where the verifier accepts inputs in a property $\Pi$ and rejects inputs $\varepsilon$-far from $\Pi$, while only querying the input a sublinear number of times. 1. We show that all logspace-uniform $\mathbf{NC}$ properties admit QIPPs with query, communication and time complexity all $\widetilde{O}(n^{2/5})$. This improves on the best known classical total complexity of $\widetilde{O}(\sqrt n)$, which is optimal in the worst case for polynomial-time verifiers under the PRG assumption of Kalai and Rothblum (CRYPTO, 2015). This resolves an open question of Dall'Agnol, Gur, Roy Moulik, and Thaler (Quantum, 2022) in the affirmative. 2. Assuming the existence of a post-quantum subexponentially secure PRG computable in logspace-uniform $\mathbf{NC}$, we prove that, for every nondecreasing, logspace-computable query bound $q(n)\le n^{1/2-\Omega(1)}$, there exists a property $\Pi$ in logspace-uniform $\mathbf{NC}$ and a constant $\varepsilon>0$ such that no polynomial-time $\varepsilon$-QIPP for $\Pi$ can achieve query complexity $q(n)$ and communication complexity $c(n)$ satisfying $q(n)+c(n)=o(n^{1/3})$. 3. We establish a bi-directional connection between QIPPs for logspace-uniform $\mathbf{NC}$ and query-model QIPs for parity. A QIP for $k$-bit parity with total complexity $k^{2/3-\Omega(1)}$ yields QIPPs for every logspace-uniform $\mathbf{NC}$ property with total complexity $n^{2/5-\Omega(1)}$. Conversely, achieving total complexity $o(n^{2/5})$ within the standard $\mathsf{PVAL}$-based framework requires improving the known query-communication tradeoff for parity. Additionally, we show that almost every size-$2^{\beta n}$ property ($0<\beta<1$) requires linear total QIPP complexity at constant proximity.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.