Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.08858

Quantum Interactive Proofs of Proximity

Kenan Wood

Published Nov 6, 2026• 0 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.2611.08858

Related papers

Interactive proofs of proximity: delegating computation in sublinear time

Guy N. Rothblum, Salil Vadhan, Avi Wigderson

We study interactive proofs with sublinear-time verifiers. These proof systems can be used to ensure approximate correctness for the results of computations delegated to an untrusted server. Following the literature on property testing, we seek proof systems where with high probability the verifier accepts every input in the language, and rejects every input that is far from the language. The verifier's query complexity (and computation complexity), as well as the communication, should all be sublinear. We call such a proof system an Interactive Proof of Proximity (IPP). On the positive side, our main result is that all languages in NC have Interactive Proofs of Proximity with roughly √n query and communication and complexities, and polylog(n) communication rounds. This is achieved by identifying a natural language, membership in an affine subspace (for a structured class of subspaces), that is complete for constructing interactive proofs of proximity, and providing efficient protocols for it. In building an IPP for this complete language, we show a tradeoff between the query and communication complexity and the number of rounds. For example, we give a 2-round protocol with roughly n3/4 queries and communication. On the negative side, we show that there exist natural languages in NC1, for which the sum of queries and communication in any constant-round interactive proof of proximity must be polynomially related to n. In particular, for any 2-round protocol, the sum of queries and communication must be at least ~Ω(√n). Finally, we construct much better IPPs for specific functions, such as bipartiteness on random or well-mixing graphs, and the majority function. The query complexities of these protocols are provably better (by exponential or polynomial factors) than what is possible in the standard property testing model, i.e. without a prover.

ACM Symposium on Theory of Computing (STOC)•May 28, 2013•81 citations

Probabilistically Checking Quantum Proofs, with Interaction

Baocheng Sun, Thomas Vidick

The model of interactive oracle proofs (IOP) generalizes the notion of probabilistically checkable proof (PCP), in which a static proof is verified probabilistically by querying a small number of bits, to the interactive setting: a polynomial-time verifier interacts with an unbounded prover, but is restricted to only reading a small number of bits, in total, from the messages sent by the prover. IOPs provide a relaxed setting in which to study local probabilistic verification. They have proved instrumental in devising efficient methods for verification through subsequent compilation into non-interactive or succinct protocols. We study a quantum analogue of interactive oracle proofs (qIOP) in which the verifier and communication are both allowed to be quantum; yet the verifier is restricted to perform measurements only on a small number of qubits received from the prover. Our main result is a qIOP for any language in QMA, in which the total communication is polynomial but the verifier only reads a polylogarithmic number of qubits in total. The protocol has completeness parameter exponentially close to $1$ and soundness bounded away from $1$ by a constant. In the absence of a quantum PCP theorem, this provides the first information-theoretically sound local and robust characterization of QMA, albeit interactive. Our protocol combines the use of a quantum locally testable code (LTC) with classical techniques, notably probabilistically checkable proofs of proximity (PCPP). We avoid the necessity for complex multi-qubit tests employed in other settings by leveraging the local indistinguishability property of the quantum LTC.

cs.CCCross-listedarXiv:2606.09588•Leibniz international proceedings in informatics•Jun 9, 2026•2 citations

Quantum Interactive Oracle Proofs

Baocheng Sun, Thomas Vidick

We initiate the study of quantum Interactive Oracle Proofs (qIOPs), a generalization of both quantum Probabilistically Checkable Proofs and quantum Interactive Proofs, as well as a quantum analogue of classical Interactive Oracle Proofs. In the model of quantum Interactive Oracle Proofs, we allow multiple rounds of quantum interaction between the quantum prover and the quantum verifier, but the verifier has limited access to quantum resources. This includes both queries to the prover's messages and the complexity of the quantum circuits applied by the verifier. The question of whether QMA admits a quantum interactive oracle proof system is a relaxation of the quantum PCP Conjecture. We show the following two main constructions of qIOPs, both of which are unconditional: - We construct a qIOP for QMA in which the verifier shares polynomially many EPR pairs with the prover at the start of the protocol and reads only a constant number of qubits from the prover's messages. - We provide a stronger construction of qIOP for QMA in which the verifier not only reads a constant number of qubits but also operates on a constant number of qubits overall, including those in their private registers. However, in this stronger setting, the communication complexity becomes exponential. This leaves open the question of whether strong qIOPs for QMA, with polynomial communication complexity, exist. As a key component of our construction, we introduce a novel single prover many-qubits test, which may be of independent interest.

cs.CCCross-listedarXiv:2601.12874•Jan 20, 2026•1 citation

Quantum Proofs of Proximity

Marcel Dall’Agnol, Tom Gur, Subhayan Roy Moulick +1 more

We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property Π and reject inputs that are ε -far from Π , while only probing a minuscule portion of their input.We investigate the complexity landscape of this model, showing that QMAPs can be exponentially stronger than both classical proofs of proximity and quantum testers. To this end, we extend the methodology of Blais, Brody, and Matulef (Computational Complexity, 2012) to prove quantum property testing lower bounds via reductions from communication complexity. This also resolves a question raised in 2013 by Montanaro and de Wolf (cf. Theory of Computing, 2016).Our algorithmic results include a purpose an algorithmic framework that enables quantum speedups for testing an expressive class of properties, namely, those that are succinctly decomposable . A consequence of this framework is a QMA algorithm to verify the Parity of an n -bit string with O(n2/3) queries and proof length. We also propose a QMA algorithm for testing graph bipartitneness, a property that lies outside of this family, for which there is a quantum speedup.

arXiv:2105.03697•Quantum•Oct 13, 2022•11 citations

An Exponential Separation Between MA and AM Proofs of Proximity

Tom Gur, Yang P. Liu, Ron D. Rothblum

Abstract Interactive proofs of proximity allow a sublinear-time verifier to check that a given input is close to the language, using a small amount of communication with a powerful (but untrusted) prover. In this work, we consider two natural minimally interactive variants of such proofs systems, in which the prover only sends a single message, referred to as the proof. The first variant, known as -proofs of Proximity (), is fully non-interactive, meaning that the proof is a function of the input only. The second variant, known as -proofs of Proximity (), allows the proof to additionally depend on the verifier's (entire) random string. The complexity of both s and s is the total number of bits that the verifier observes—namely, the sum of the proof length and query complexity. Our main result is an exponential separation between the power of s and s. Specifically, we exhibit an explicit and natural property $$\Pi$$ Π that admits an with complexity $$O(\log n)$$ O ( log n ) , whereas any for $$\Pi$$ Π has complexity $$\tilde{\Omega}(n^{1/4})$$ Ω ~ ( n 1 / 4 ) , where n denotes the length of the input in bits. Our lower bound also yields an alternate proof, which is more general and arguably much simpler, for a recent result of Fischer et al. (ITCS, 2014). Also, Aaronson (Quantum Information & Computation 2012) has shown a $$\Omega(n^{1/6})$$ Ω ( n 1 / 6 ) lower bound for the same property $$\Pi$$ Π . Lastly, we also consider the notion of oblivious proofs of proximity, in which the verifier's queries are oblivious to the proof. In this setting, we show that s can only be quadratically stronger than s. As an application of this result, we show an exponential separation between the power of public and private coin for oblivious interactive proofs of proximity.

Computational Complexity•Aug 18, 2021•11 citations

Quantum Proofs

Thomas Vidick, John Watrous

Quantum information and computation provide a fascinating twist on the notion of proofs in computational complexity theory. For instance, one may consider a quantum computational analogue of the complexity class NP, known as QMA, in which a quantum state plays the role of a proof (also called a certificate or witness), and is checked by a polynomial-time quantum computation. For some problems, the fact that a quantum proof state could be a superposition over exponentially many classical states appears to offer computational advantages over classical proof strings. In the interactive proof system setting, one may consider a verifier and one or more provers that exchange and process quantum information rather than classical information during an interaction for a given input string, giving rise to quantum complexity classes such as QIP, QSZK, and QMIP* that represent natural quantum analogues of IP, SZK, and MIP. While quantum interactive proof systems inherit some properties from their classical counterparts, they also possess distinct and uniquely quantum features that lead to an interesting landscape of complexity classes based on variants of this model. In this survey we provide an overview of many of the known results concerning quantum proofs, computational models based on this concept, and properties of the complexity classes they define. In particular, we discuss non-interactive proofs and the complexity class QMA, single-prover quantum interactive proof systems and the complexity class QIP, statistical zero-knowledge quantum interactive proof systems and the complexity class QSZK, and multiprover interactive proof systems and the complexity classes QMIP, QMIP*, and MIP*.

arXiv:1610.01664•Foundations and Trends® in Theoretical Computer Science•Mar 31, 2016•56 citations
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 NC\mathbf{NC}NC properties admit QIPPs with query, communication and time complexity all O~(n2/5)\widetilde{O}(n^{2/5})O(n2/5). This improves on the best known classical total complexity of O~(n)\widetilde{O}(\sqrt n)O(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 NC\mathbf{NC}NC, we prove that, for every nondecreasing, logspace-computable query bound q(n)≤n1/2−Ω(1)q(n)\le n^{1/2-Ω(1)}q(n)≤n1/2−Ω(1), there exists a property ΠΠΠ in logspace-uniform NC\mathbf{NC}NC and a constant ε>0\varepsilon>0ε>0 such that no polynomial-time ε\varepsilonε-QIPP for ΠΠΠ can achieve query complexity q(n)q(n)q(n) and communication complexity c(n)c(n)c(n) satisfying q(n)+c(n)=o(n1/3)q(n)+c(n)=o(n^{1/3})q(n)+c(n)=o(n1/3). 3. We establish a bi-directional connection between QIPPs for logspace-uniform NC\mathbf{NC}NC and query-model QIPs for parity. A QIP for kkk-bit parity with total complexity k2/3−Ω(1)k^{2/3-Ω(1)}k2/3−Ω(1) yields QIPPs for every logspace-uniform NC\mathbf{NC}NC property with total complexity n2/5−Ω(1)n^{2/5-Ω(1)}n2/5−Ω(1). Conversely, achieving total complexity o(n2/5)o(n^{2/5})o(n2/5) within the standard PVAL\mathsf{PVAL}PVAL-based framework requires improving the known query-communication tradeoff for parity. Additionally, we show that almost every size-2βn2^{βn}2βn property (0<β<10<β<10<β<1) requires linear total QIPP complexity at constant proximity.
We study interactive proofs with sublinear-time verifiers. These proof systems can be used to ensure approximate correctness for the results of computations delegated to an untrusted server. Following the literature on property testing, we seek proof systems where with high probability the verifier accepts every input in the language, and rejects every input that is far from the language. The verifier's query complexity (and computation complexity), as well as the communication, should all be sublinear. We call such a proof system an Interactive Proof of Proximity (IPP). On the positive side, our main result is that all languages in NC have Interactive Proofs of Proximity with roughly √n query and communication and complexities, and polylog(n) communication rounds. This is achieved by identifying a natural language, membership in an affine subspace (for a structured class of subspaces), that is complete for constructing interactive proofs of proximity, and providing efficient protocols for it. In building an IPP for this complete language, we show a tradeoff between the query and communication complexity and the number of rounds. For example, we give a 2-round protocol with roughly n3/4 queries and communication. On the negative side, we show that there exist natural languages in NC1, for which the sum of queries and communication in any constant-round interactive proof of proximity must be polynomially related to n. In particular, for any 2-round protocol, the sum of queries and communication must be at least ~Ω(√n). Finally, we construct much better IPPs for specific functions, such as bipartiteness on random or well-mixing graphs, and the majority function. The query complexities of these protocols are provably better (by exponential or polynomial factors) than what is possible in the standard property testing model, i.e. without a prover.
The model of interactive oracle proofs (IOP) generalizes the notion of probabilistically checkable proof (PCP), in which a static proof is verified probabilistically by querying a small number of bits, to the interactive setting: a polynomial-time verifier interacts with an unbounded prover, but is restricted to only reading a small number of bits, in total, from the messages sent by the prover. IOPs provide a relaxed setting in which to study local probabilistic verification. They have proved instrumental in devising efficient methods for verification through subsequent compilation into non-interactive or succinct protocols. We study a quantum analogue of interactive oracle proofs (qIOP) in which the verifier and communication are both allowed to be quantum; yet the verifier is restricted to perform measurements only on a small number of qubits received from the prover. Our main result is a qIOP for any language in QMA, in which the total communication is polynomial but the verifier only reads a polylogarithmic number of qubits in total. The protocol has completeness parameter exponentially close to 111 and soundness bounded away from 111 by a constant. In the absence of a quantum PCP theorem, this provides the first information-theoretically sound local and robust characterization of QMA, albeit interactive. Our protocol combines the use of a quantum locally testable code (LTC) with classical techniques, notably probabilistically checkable proofs of proximity (PCPP). We avoid the necessity for complex multi-qubit tests employed in other settings by leveraging the local indistinguishability property of the quantum LTC.
We initiate the study of quantum Interactive Oracle Proofs (qIOPs), a generalization of both quantum Probabilistically Checkable Proofs and quantum Interactive Proofs, as well as a quantum analogue of classical Interactive Oracle Proofs. In the model of quantum Interactive Oracle Proofs, we allow multiple rounds of quantum interaction between the quantum prover and the quantum verifier, but the verifier has limited access to quantum resources. This includes both queries to the prover's messages and the complexity of the quantum circuits applied by the verifier. The question of whether QMA admits a quantum interactive oracle proof system is a relaxation of the quantum PCP Conjecture. We show the following two main constructions of qIOPs, both of which are unconditional: - We construct a qIOP for QMA in which the verifier shares polynomially many EPR pairs with the prover at the start of the protocol and reads only a constant number of qubits from the prover's messages. - We provide a stronger construction of qIOP for QMA in which the verifier not only reads a constant number of qubits but also operates on a constant number of qubits overall, including those in their private registers. However, in this stronger setting, the communication complexity becomes exponential. This leaves open the question of whether strong qIOPs for QMA, with polynomial communication complexity, exist. As a key component of our construction, we introduce a novel single prover many-qubits test, which may be of independent interest.
We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property Π and reject inputs that are ε -far from Π , while only probing a minuscule portion of their input.We investigate the complexity landscape of this model, showing that QMAPs can be exponentially stronger than both classical proofs of proximity and quantum testers. To this end, we extend the methodology of Blais, Brody, and Matulef (Computational Complexity, 2012) to prove quantum property testing lower bounds via reductions from communication complexity. This also resolves a question raised in 2013 by Montanaro and de Wolf (cf. Theory of Computing, 2016).Our algorithmic results include a purpose an algorithmic framework that enables quantum speedups for testing an expressive class of properties, namely, those that are succinctly decomposable . A consequence of this framework is a QMA algorithm to verify the Parity of an n -bit string with O(n2/3) queries and proof length. We also propose a QMA algorithm for testing graph bipartitneness, a property that lies outside of this family, for which there is a quantum speedup.
Abstract Interactive proofs of proximity allow a sublinear-time verifier to check that a given input is close to the language, using a small amount of communication with a powerful (but untrusted) prover. In this work, we consider two natural minimally interactive variants of such proofs systems, in which the prover only sends a single message, referred to as the proof. The first variant, known as -proofs of Proximity (), is fully non-interactive, meaning that the proof is a function of the input only. The second variant, known as -proofs of Proximity (), allows the proof to additionally depend on the verifier's (entire) random string. The complexity of both s and s is the total number of bits that the verifier observes—namely, the sum of the proof length and query complexity. Our main result is an exponential separation between the power of s and s. Specifically, we exhibit an explicit and natural property Π\PiΠ Π that admits an with complexity O(log⁡n)O(\log n)O(logn) O ( log n ) , whereas any for Π\PiΠ Π has complexity Ω~(n1/4)\tilde{\Omega}(n^{1/4})Ω~(n1/4) Ω ~ ( n 1 / 4 ) , where n denotes the length of the input in bits. Our lower bound also yields an alternate proof, which is more general and arguably much simpler, for a recent result of Fischer et al. (ITCS, 2014). Also, Aaronson (Quantum Information & Computation 2012) has shown a Ω(n1/6)\Omega(n^{1/6})Ω(n1/6) Ω ( n 1 / 6 ) lower bound for the same property Π\PiΠ Π . Lastly, we also consider the notion of oblivious proofs of proximity, in which the verifier's queries are oblivious to the proof. In this setting, we show that s can only be quadratically stronger than s. As an application of this result, we show an exponential separation between the power of public and private coin for oblivious interactive proofs of proximity.
Quantum information and computation provide a fascinating twist on the notion of proofs in computational complexity theory. For instance, one may consider a quantum computational analogue of the complexity class NP, known as QMA, in which a quantum state plays the role of a proof (also called a certificate or witness), and is checked by a polynomial-time quantum computation. For some problems, the fact that a quantum proof state could be a superposition over exponentially many classical states appears to offer computational advantages over classical proof strings. In the interactive proof system setting, one may consider a verifier and one or more provers that exchange and process quantum information rather than classical information during an interaction for a given input string, giving rise to quantum complexity classes such as QIP, QSZK, and QMIP* that represent natural quantum analogues of IP, SZK, and MIP. While quantum interactive proof systems inherit some properties from their classical counterparts, they also possess distinct and uniquely quantum features that lead to an interesting landscape of complexity classes based on variants of this model. In this survey we provide an overview of many of the known results concerning quantum proofs, computational models based on this concept, and properties of the complexity classes they define. In particular, we discuss non-interactive proofs and the complexity class QMA, single-prover quantum interactive proof systems and the complexity class QIP, statistical zero-knowledge quantum interactive proof systems and the complexity class QSZK, and multiprover interactive proof systems and the complexity classes QMIP, QMIP*, and MIP*.