← 研踪 PaperTrailarXiv:2611.08858 · v1
Quantum Interactive Proofs of Proximity
首次提交 2026-11-06 09:28
版本更新 2026-11-06 09:28
雷达观测 2026-11-09 10:16
摘要
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 $Π$ and rejects inputs $\varepsilon$-far from $Π$, 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-Ω(1)}$, there exists a property $Π$ in logspace-uniform $\mathbf{NC}$ and a constant $\varepsilon>0$ such that no polynomial-time $\varepsilon$-QIPP for $Π$ 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-Ω(1)}$ yields QIPPs for every logspace-uniform $\mathbf{NC}$ property with total complexity $n^{2/5-Ω(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^{βn}$ property ($0<β<1$) requires linear total QIPP complexity at constant proximity.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-06 09:28 · 最新观测版本
Quantum Interactive Proofs of Proximity
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 $Π$ and rejects inputs $\varepsilon$-far from $Π$, 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-Ω(1)}$, there exists a property $Π$ in logspace-uniform $\mathbf{NC}$ and a constant $\varepsilon>0$ such that no polynomial-time $\varepsilon$-QIPP for $Π$ 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-Ω(1)}$ yields QIPPs for every logspace-uniform $\mathbf{NC}$ property with total complexity $n^{2/5-Ω(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^{βn}$ property ($0<β<1$) requires linear total QIPP complexity at constant proximity.
查看此版本解读 →查看此版本原文 ↗