CS Paper Radar

Quantum Interactive Proofs of Proximity

Kenan Wood

cs.CC ·submitted 2026-11-06 01:28 UTC · v1
theoryhot direction

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 $Π$ 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.

Closest papers

Nearest neighbours by meaning across the whole index.

Quantum Advantage has Few Complexity Implications

cs.CC quant-phcs.CR ·2026-11-03 ·Eli Goldin, Alex Lombardi, Tomoyuki Morimae
similarity 0.71
Abstract

We consider the complexity implications of proofs of quantumness and (quantum verifier) oblivious state preparation. We show that both of these objects can coexist with the easiness of nondeterministic computation. That is, we give evidence that proofs of quantumness can exist when $\mathsf{P} = \mathsf{NP}$ and that (quantum verifier) oblivious state preparation can exist when $\mathsf{BQP} = \mathsf{QCMA}$. In particular, we give a classical oracle relative to which (1) $\mathsf{P}^\mathcal{O} = \mathsf{NP}^\mathcal{O}$ (2) $\mathsf{BQP}^\mathcal{O} = \mathsf{PSPACE}^\mathcal{O}$ (3) Proofs of quantumness exist. In particular, there exists a language in $\mathsf{IP}^\mathcal{O} \subseteq \mathsf{BQP}^\mathcal{O}$ which is hard on average against $\mathsf{P}^\mathcal{O}/poly$. We give a unitary oracle such that (1) $\mathsf{BQP}^\mathcal{O} = \mathsf{QCMA}^\mathcal{O}$ (2) Quantum verifier oblivious state preparation exists. These oracle separations directly imply a number of related consequences. For example, our first result implies that proofs of quantumness cannot be used to construct classical or quantum cryptography with a relativizing proof. Our second result implies that quantum computation/classical communication oblivious transfer cannot be used to construct post-quantum one-way functions with a relativizing proof.

0.24

Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy

cs.CC quant-phcs.CR ·2026-10-27 ·Atul Mantri
theory similarity 0.69
Abstract

It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size $2^{\mathrm{poly}(n)}$ changes its output with probability above $2^{-Ω(n)}$ when the answer of a random instance is flipped by changing a single leaf.

0.30

On quantum interactive proofs with a laconic prover

cs.CC quant-phcs.CR ·2026-09-30 ·Zihan Hu, Yupan Liu
theory similarity 0.68
Abstract · 66 pages, 4 protocols, 2 algorithms, 3 circuits, 4 tables. v2: Minor changes

Interactive proof systems with a laconic prover, studied by Goldreich, Vadhan, and Wigderson (CC, 2002), capture problems verifiable with logarithmic prover communication in the classical setting. For two-message quantum analogs, even a single-bit prover response contains quantum statistical zero-knowledge ($\sf QSZK$), introduced by Watrous (FOCS 2002). However, restricting the verifier's question to classical public coins collapses the corresponding class to $\sf BQP$, as shown by Beigi, Shor, and Watrous (ToC, 2011). We further study two-message quantum interactive proof systems with a laconic prover. To this end, we introduce the class ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$, where $\ell$ is the length of the prover's response, and establish: 1. A natural complete characterization of ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ by Multi-State Distinguishability. In particular, Quantum State Distinguishability (QSD) is ${\sf QIP}_{\rm bit}$-complete. Since QSD is $\sf QSZK$-hard, our result places ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$, for $\ell\geq 2$, in a landscape "just above" $\sf QSZK$. 2. Easy regimes for ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ collapsing to $\sf QSZK$. We prove that QSD$[a,b]$ (and thus ${\sf QIP}_{\rm bit}[a,b]$) is in $\sf QSZK$ when $a(n)-b(n)\geq 1/O(\log n)$, and combine this with an answer compression from ${\sf QIP}_{\ell\text{-}{\rm bit}}[2,c,s]$ to ${\sf QIP}_{\rm bit}$ to obtain another easy regime when $2c>(1+2^{\ell/2})s$. Remarkably, our improved polarization applies to SD and $\sf SZK$, resolving an open problem in Sahai and Vadhan (JACM, 2003). 3. Quantum public coins also make the interaction useless: ${\sf qc}\text{-}{\sf QAM}[O(\sqrt{\log{n}})]$ with constant gap is in $\sf BQP$, where ${\sf qc}\text{-}{\sf QAM}[\ell]$ is a subclass of ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ in which the verifier's question is exactly halves of EPR pairs.

0.48

$\mathsf{BQP} \subseteq \mathsf{IP}$ Does Not Relativize

cs.CC quant-ph ·2026-09-22 ·Adam Bouland, Andrew Huang, Anand Natarajan, Itay Shalit, Avishay Tal
similarity 0.67
Abstract

We construct an oracle relative to which $\mathsf{BQP} \not\subseteq \mathsf{IP}$, resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson et al., our work also gives the first oracle separation between $\mathsf{IP}$ and $\mathsf{MIP}$, answering a question dating back to Fortnow's thesis. Our separation is based on the Forrelation problem, where given Boolean functions $f$ and $g$, the goal is to determine if $f$ is correlated with the Fourier spectrum of $g$. While this task is solvable by a query-efficient quantum algorithm, we show that it admits no classical interactive protocol with polynomial communication and a polynomial-query verifier. Our proof is based on (i) a new structural result showing how to approximate Avg-Max circuits (which are well-known to capture the power of interactive proofs in the oracular setting) by convex functions with small first and second derivatives and (ii) a novel analysis establishing that the Forrelation distribution suggested by Aaronson and Ambainis fools such functions. Our results imply that any prover-efficient classical interactive protocol for $\mathsf{BQP}$ must rely on non-relativizing techniques. This might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.

0.42

Computational Bounds for $f$-Routing

cs.CC quant-ph ·2026-09-30 ·Oren Renard, Nicholas Spooner
theory similarity 0.67
Abstract · Improved writing and exposition

The $f$-routing protocol is a leading candidate for quantum position verification (Kent, Munro, and Spiller, Physical Review A, 2011), but security guarantees for explicit functions remain limited. We prove unconditional resource lower bounds for uniform attackers. Our techniques bypass communication-complexity bounds central to previous works, which are inherently at most linear in the input length. We show that, for input length $n$ and a sufficiently small constant $ε>0$, a uniform strategy running in time $T$ and succeeding with probability at least $1-ε$ on every input implies the following computational bounds on $f$. 1. If the strategies are arbitrary quantum channels, then $f\in \mathrm{QSZK}(\mathrm{poly}(T))$, where $\mathrm{QSZK}(T)$ is the class of languages having quantum statistical zero-knowledge proofs in which the verifier runs in time $T$ and the simulator in time $\mathrm{poly}(T)$. 2. If the strategies are Clifford+T circuits using at most $t$ magic gates, then $f\in \mathrm{DTIME}(\mathrm{poly}(T2^t))$. 3. If the strategies are explicit Pauli-sparse unitaries acting on at most $T$ qubits and having at most $s$ nonzero Pauli coefficients, then $f\in \mathrm{DTIME}(\mathrm{poly}(Ts))$. Time and space hierarchies then yield explicit functions secure against superlinear and even all polynomial-time adversaries under our computational restrictions. These bounds exceed the bounded-storage qubit bound $q\leq\log n$ of Bluhm, Christandl, and Speelman (Nature Physics, 2022) for the inner product function $f=\mathrm{IP}$, at the cost of restricting adversarial computation and increasing honest evaluation complexity.

0.23

Beyond IP = PSPACE and QIP = PSPACE: Interactive Proofs in Arbitrary Physical Theories

cs.CC quant-ph ·2026-10-01 ·Kishor Bharti
similarity 0.67
Abstract · 36 pages

The equalities IP = PSPACE and QIP = PSPACE, the latter achievable with three messages, raise a basic question: how much of an interactive proof's power comes from the underlying physical theory? We study interactive proofs in general probabilistic theories, which include classical and quantum theory. The answer depends on what the prover and verifier exchange and how the theory specifies efficient operations. When they exchange only classical messages, protocols in every theory satisfying our standard assumptions decide exactly PSPACE. For protocols with a quantum verifier and quantum messages, allowing a prover to use any theory containing quantum theory does not increase the maximum acceptance probability. Thus, the three-message PSPACE result remains valid against such provers. When messages may be arbitrary systems, the interactive-proof class can strictly exceed PSPACE.

0.29

Optimal and Verifiable Quantum Advantages in Communication Complexity

cs.CC quant-ph ·2026-10-04 ·Ryan Anselm, Michelle Ding, Dar Gilboa, Sabee Grewal
hot direction similarity 0.67
Abstract · 65 pages

We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an $n$-qubit quantum one-way protocol, whereas every randomized two-way protocol requires $Ω(2^n)$ bits of communication. We then introduce a variant of this problem whose solutions can be verified in polynomial time. This variant also admits an $n$-qubit quantum one-way protocol, while every randomized one-way protocol requires $Ω(2^n)$ bits of communication. We also construct a family of efficiently verifiable total search problems achieving an $n$ versus $Ω_d(n^d)$ separation between quantum one-way and randomized one-way communication for every fixed $d \ge 2$. In the quantum protocol, Alice prepares her message using a single unitary from the $d$th level of the Clifford hierarchy, and Bob performs a Clifford measurement. This separation is asymptotically optimal under this restriction on Alice's message. For $d = 2$, Alice's message is a stabilizer state and Bob's measurement is Clifford, so the protocol uses no magic, yet achieves an optimal quadratic quantum advantage. Finally, we discuss how these separations can be adapted to near-term quantum advantage experiments in which the demonstrated advantage is both unconditional and efficiently verifiable.

0.47

Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace

cs.CC quant-ph ·2026-10-21 ·Chengu Wang
theory similarity 0.66
Abstract

We prove that the randomized communication complexity of Vector-in-Subspace in $\mathbb R^n$ with error at most $1/3$ is $Θ(\sqrt n)$. Alice holds a unit vector $u$ and Bob holds an $n/2$-dimensional subspace $H$; they must distinguish $u\in H$ from $u\in H^\perp$. An exact one-way quantum protocol uses $O(\log n)$ qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's $O(\sqrt n)$ upper bound, improves the $Ω(n^{1/3})$ lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's $Ω(\sqrt n)$ result. The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.

0.31