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

Leibniz international proceedings in informatics

On Local Testability in the Non-Signaling Setting

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Published Jan 1, 2020• 1 citation
Publisher

Abstract

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics for decades, and have recently found applications in theoretical computer science. These applications motivate the study of local-to-global phenomena for non-signaling functions. We prove that low-degree testing in the non-signaling setting is possible, assuming that the locality of the non-signaling function exceeds a threshold. We additionally show that if the locality is below the threshold then the test fails spectacularly, in that there exists a non-signaling function which passes the test with probability 1 and yet is maximally far from being low-degree. Along the way, we present general results about the local testability of linear codes in the non-signaling setting. These include formulating natural definitions that capture the condition that a non-signaling function "belongs" to a given code, and characterizing the sets of local constraints that imply membership in the code. We prove these results by formulating a logical inference system for linear constraints on non-signaling functions that is complete and sound.

DOI
10.4230/lipics.itcs.2020.26

Related papers

Testing Linearity against Non-Signaling Strategies

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent non-locality. Recently, they have received attention in Theoretical Computer Science due to connections to Complexity and Cryptography. We initiate the study of Property Testing against non-signaling strategies, focusing first on the classical problem of linearity testing (Blum, Luby, and Rubinfeld; JCSS 1993). We prove that any non-signaling strategy that passes the linearity test with high probability must be close to a quasi-distribution over linear functions. Quasi-distributions generalize the notion of probability distributions over global objects (such as functions) by allowing negative probabilities, while at the same time requiring that "local views" follow standard distributions (with non-negative probabilities). Quasi-distributions arise naturally in the study of Quantum Mechanics as a tool to describe various non-local phenomena. Our analysis of the linearity test relies on Fourier analytic techniques applied to quasi-distributions. Along the way, we also establish general equivalences between non-signaling strategies and quasi-distributions, which we believe will provide a useful perspective on the study of Property Testing against non-signaling strategies beyond linearity testing.

Leibniz international proceedings in informatics•Jan 1, 2018•0 citations

Testing linearity against non-signaling strategies

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent non-locality. Recently, they have received attention in Theoretical Computer Science due to connections to Complexity and Cryptography.We initiate the study of Property Testing against non-signaling strategies, focusing first on the classical problem of linearity testing (Blum, Luby, and Rubinfeld; JCSS 1993). We prove that any non-signaling strategy that passes the linearity test with high probability must be close to a quasi-distribution over linear functions.Quasi-distributions generalize the notion of probability distributions over global objects (such as functions) by allowing negative probabilities, while at the same time requiring that local views follow standard distributions (with non-negative probabilities). Quasi-distributions arise naturally in the study of Quantum Mechanics as a tool to describe various non-local phenomena.Our analysis of the linearity test relies on Fourier analytic techniques applied to quasi-distributions. Along the way, we also establish general equivalences between non-signaling strategies and quasi-distributions, which we believe will provide a useful perspective on the study of Property Testing against non-signaling strategies beyond linearity testing.

•Jun 22, 2018•3 citations

Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality

Mohammad Mahdi Jahanara, Sajin Koroth, Igor Shinkar

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is probabilistically checkable proof (PCPs) systems that are sound against non-signaling strategies. In this paper we show, assuming a certain geometrical hypothesis about noise robustness of non-signaling proofs (or, equivalently, about robustness to noise of solutions to the Sherali-Adams linear program), that a slight variant of the parallel repetition of the exponential-length constant-query PCP construction due to Arora et al. (JACM 1998) is sound against non-signaling strategies with constant locality. Our proof relies on the analysis of the linearity test and agreement test (also known as the direct product test) in the non-signaling setting.

arXiv:2009.04892•Sep 10, 2020•2 citations

Testing Linearity against Non-signaling Strategies

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in physics as a strict generalization of quantum strategies to understand the power and limitations of nature’s apparent non-locality. Recently, they have received attention in theoretical computer science due to connections to Complexity and Cryptography. We initiate the study of Property Testing against non-signaling strategies, focusing first on the classical problem of linearity testing (Blum, Luby, and Rubinfeld; JCSS 1993). We prove that any non-signaling strategy that passes the linearity test with high probability must be close to a quasi-distribution over linear functions. Quasi-distributions generalize the notion of probability distributions over global objects (such as functions) by allowing negative probabilities, while at the same time requiring that “local views” follow standard distributions (with non-negative probabilities). Quasi-distributions arise naturally in the study of quantum mechanics as a tool to describe various non-local phenomena. Our analysis of the linearity test relies on Fourier analytic techniques applied to quasi-distributions. Along the way, we also establish general equivalences between non-signaling strategies and quasi-distributions, which we believe will provide a useful perspective on the study of Property Testing against non-signaling strategies beyond linearity testing.

ACM Transactions on Computation Theory•Jun 1, 2020•1 citation

Measuring Bell non-locality in the presence of signaling

Mark Broom, Talel Naccache, Emmanuel M. Pothos +2 more

Scientific inquiry seeks causal explanations of observed phenomena. The Bell experiment provides a paradigmatic case, revealing correlations between spatially separated systems that no local model can reproduce. Such correlations, known as Bell non-locality, are typically analyzed under the non-signaling assumption, which requires that local statistics be independent of distant measurement choices. Yet real experiments, as well as applications beyond physics, often involve signaling, raising the question of how non-locality should be characterized without this constraint. We introduce a general method for quantifying Bell non-locality in the presence of signaling, designed to relax locality as little as necessary. Our approach is guided by the question: how often can locality be preserved across repeated trials in explaining the observed correlations? The task reduces to finding the optimal convex decomposition of the observed correlations into local and genuinely non-local components. We solve this problem within the linear-programming framework, obtaining a closed-form solution valid for arbitrary correlations. We further evaluate a corresponding measure of signaling, demonstrating the generality of the method and the non-trivial character of the results. By extending the notion of non-locality beyond the non-signaling regime, our framework reshapes the basis for experimental analysis in physics and offers tools applicable outside physics.

quant-pharXiv:2603.00984•New Journal of Physics•Mar 3, 2026•0 citations

Quantum Locally Testable Codes

Dorit Aharonov, Lior Eldar

We initiate the study of quantum locally testable codes ($\text{qLTC}$s). Classical $\text{LTC}$s are very important in computational complexity. These codes are defined as the linear subspace satisfying a set of local constraints, with the additional requirement that their soundness, $R(\delta)$, which is the probability that a randomly chosen constraint is violated, is proportional to the proximity $\delta$, where $\delta n$ is the distance of a word from the code. Excellent $\text{LTC}$s exist in the classical world, and they are tightly related to the celebrated $\text{PCP}$ (probabilistically checkable proof) theorem. In quantum complexity, quantum error correcting codes provide central examples in the study of the illusive behavior of multiparticle entanglement, and they have played a crucial role in many computational complexity results. We provide a definition of the quantum analogue of $\text{LTC}$s and motivate it by connecting its central notions in the study of both entanglement and quantum Hamiltonian complexity. A natural question is whether such codes exist, and how good can their soundness be. To the best of our knowledge all quantum codes known today exhibit poor soundness. Moreover, we show that the soundness of $\text{CSS}$ codes (which are commonly used quantum codes defined by two classical codes) is governed by the minimal soundness of the two classical codes; in the most natural $\text{CSS}$ code we examined as a candidate $\text{qLTC}$, namely, the Reed--Muller code, there is a tradeoff between the parameters of the two codes, which prevents the resulting quantum code from being $\text{qLTC}$. These facts seem to suggest a more general phenomenon, by which the soundness of $\text{qLTC}$s is inherently restricted due to multiparticle entanglement. Our main technical contribution consists of two complementary results regarding $\text{qLTC}$s which are stabilizer codes (denoted $\text{sLTC}$s). We first prove a surprising, inherently quantum property of $\text{sLTC}$s. For small constant values of proximity, the better the local expansion of the interaction graph of the constraints, the less sound the $\text{sLTC}$ becomes. This stands in sharp contrast to the classical setting. The complementary, more intuitive result also holds (and is actually much more involved technically to prove in the quantum case): an upper bound on the soundness when the code is defined on bad local expanders. Together we arrive at a quantum upper bound on the soundness of $\text{sLTC}$s set on any graph, which does not hold in the classical case. Many open questions are raised regarding what possible parameters are achievable for $\text{qLTC}$s, and their relation to other objects of interest in quantum information theory. In the appendix we also define a quantum analogue of $\text{PCP}$s of proximity ($\text{PCPP}$s) and point out that the result of [E. Ben-Sasson et al., SIAM J. Comput., 36 (2006), pp. 889--974] by which $\text{PCPP}$s imply $\text{LTC}$s with related parameters carries over to the $\text{sLTC}$s. This creates a first link between $\text{qLTC}$s and quantum $\text{PCP}$s [D. Aharonov, I. Arad, and T. Vidick, ACM SIGACT News Archive, 44 (2013), pp. 47--79].

arXiv:1310.5664•SIAM Journal on Computing•Jan 1, 2015•46 citations
Non-signaling strategies are a generalization of quantum strategies that have been studied in physics for decades, and have recently found applications in theoretical computer science. These applications motivate the study of local-to-global phenomena for non-signaling functions. We prove that low-degree testing in the non-signaling setting is possible, assuming that the locality of the non-signaling function exceeds a threshold. We additionally show that if the locality is below the threshold then the test fails spectacularly, in that there exists a non-signaling function which passes the test with probability 1 and yet is maximally far from being low-degree. Along the way, we present general results about the local testability of linear codes in the non-signaling setting. These include formulating natural definitions that capture the condition that a non-signaling function "belongs" to a given code, and characterizing the sets of local constraints that imply membership in the code. We prove these results by formulating a logical inference system for linear constraints on non-signaling functions that is complete and sound.
Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent non-locality. Recently, they have received attention in Theoretical Computer Science due to connections to Complexity and Cryptography. We initiate the study of Property Testing against non-signaling strategies, focusing first on the classical problem of linearity testing (Blum, Luby, and Rubinfeld; JCSS 1993). We prove that any non-signaling strategy that passes the linearity test with high probability must be close to a quasi-distribution over linear functions. Quasi-distributions generalize the notion of probability distributions over global objects (such as functions) by allowing negative probabilities, while at the same time requiring that "local views" follow standard distributions (with non-negative probabilities). Quasi-distributions arise naturally in the study of Quantum Mechanics as a tool to describe various non-local phenomena. Our analysis of the linearity test relies on Fourier analytic techniques applied to quasi-distributions. Along the way, we also establish general equivalences between non-signaling strategies and quasi-distributions, which we believe will provide a useful perspective on the study of Property Testing against non-signaling strategies beyond linearity testing.
Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent non-locality. Recently, they have received attention in Theoretical Computer Science due to connections to Complexity and Cryptography.We initiate the study of Property Testing against non-signaling strategies, focusing first on the classical problem of linearity testing (Blum, Luby, and Rubinfeld; JCSS 1993). We prove that any non-signaling strategy that passes the linearity test with high probability must be close to a quasi-distribution over linear functions.Quasi-distributions generalize the notion of probability distributions over global objects (such as functions) by allowing negative probabilities, while at the same time requiring that local views follow standard distributions (with non-negative probabilities). Quasi-distributions arise naturally in the study of Quantum Mechanics as a tool to describe various non-local phenomena.Our analysis of the linearity test relies on Fourier analytic techniques applied to quasi-distributions. Along the way, we also establish general equivalences between non-signaling strategies and quasi-distributions, which we believe will provide a useful perspective on the study of Property Testing against non-signaling strategies beyond linearity testing.
Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is probabilistically checkable proof (PCPs) systems that are sound against non-signaling strategies. In this paper we show, assuming a certain geometrical hypothesis about noise robustness of non-signaling proofs (or, equivalently, about robustness to noise of solutions to the Sherali-Adams linear program), that a slight variant of the parallel repetition of the exponential-length constant-query PCP construction due to Arora et al. (JACM 1998) is sound against non-signaling strategies with constant locality. Our proof relies on the analysis of the linearity test and agreement test (also known as the direct product test) in the non-signaling setting.
Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in physics as a strict generalization of quantum strategies to understand the power and limitations of nature’s apparent non-locality. Recently, they have received attention in theoretical computer science due to connections to Complexity and Cryptography. We initiate the study of Property Testing against non-signaling strategies, focusing first on the classical problem of linearity testing (Blum, Luby, and Rubinfeld; JCSS 1993). We prove that any non-signaling strategy that passes the linearity test with high probability must be close to a quasi-distribution over linear functions. Quasi-distributions generalize the notion of probability distributions over global objects (such as functions) by allowing negative probabilities, while at the same time requiring that “local views” follow standard distributions (with non-negative probabilities). Quasi-distributions arise naturally in the study of quantum mechanics as a tool to describe various non-local phenomena. Our analysis of the linearity test relies on Fourier analytic techniques applied to quasi-distributions. Along the way, we also establish general equivalences between non-signaling strategies and quasi-distributions, which we believe will provide a useful perspective on the study of Property Testing against non-signaling strategies beyond linearity testing.
Scientific inquiry seeks causal explanations of observed phenomena. The Bell experiment provides a paradigmatic case, revealing correlations between spatially separated systems that no local model can reproduce. Such correlations, known as Bell non-locality, are typically analyzed under the non-signaling assumption, which requires that local statistics be independent of distant measurement choices. Yet real experiments, as well as applications beyond physics, often involve signaling, raising the question of how non-locality should be characterized without this constraint. We introduce a general method for quantifying Bell non-locality in the presence of signaling, designed to relax locality as little as necessary. Our approach is guided by the question: how often can locality be preserved across repeated trials in explaining the observed correlations? The task reduces to finding the optimal convex decomposition of the observed correlations into local and genuinely non-local components. We solve this problem within the linear-programming framework, obtaining a closed-form solution valid for arbitrary correlations. We further evaluate a corresponding measure of signaling, demonstrating the generality of the method and the non-trivial character of the results. By extending the notion of non-locality beyond the non-signaling regime, our framework reshapes the basis for experimental analysis in physics and offers tools applicable outside physics.
We initiate the study of quantum locally testable codes (qLTC\text{qLTC}qLTCs). Classical LTC\text{LTC}LTCs are very important in computational complexity. These codes are defined as the linear subspace satisfying a set of local constraints, with the additional requirement that their soundness, R(δ)R(\delta)R(δ), which is the probability that a randomly chosen constraint is violated, is proportional to the proximity δ\deltaδ, where δn\delta nδn is the distance of a word from the code. Excellent LTC\text{LTC}LTCs exist in the classical world, and they are tightly related to the celebrated PCP\text{PCP}PCP (probabilistically checkable proof) theorem. In quantum complexity, quantum error correcting codes provide central examples in the study of the illusive behavior of multiparticle entanglement, and they have played a crucial role in many computational complexity results. We provide a definition of the quantum analogue of LTC\text{LTC}LTCs and motivate it by connecting its central notions in the study of both entanglement and quantum Hamiltonian complexity. A natural question is whether such codes exist, and how good can their soundness be. To the best of our knowledge all quantum codes known today exhibit poor soundness. Moreover, we show that the soundness of CSS\text{CSS}CSS codes (which are commonly used quantum codes defined by two classical codes) is governed by the minimal soundness of the two classical codes; in the most natural CSS\text{CSS}CSS code we examined as a candidate qLTC\text{qLTC}qLTC, namely, the Reed--Muller code, there is a tradeoff between the parameters of the two codes, which prevents the resulting quantum code from being qLTC\text{qLTC}qLTC. These facts seem to suggest a more general phenomenon, by which the soundness of qLTC\text{qLTC}qLTCs is inherently restricted due to multiparticle entanglement. Our main technical contribution consists of two complementary results regarding qLTC\text{qLTC}qLTCs which are stabilizer codes (denoted sLTC\text{sLTC}sLTCs). We first prove a surprising, inherently quantum property of sLTC\text{sLTC}sLTCs. For small constant values of proximity, the better the local expansion of the interaction graph of the constraints, the less sound the sLTC\text{sLTC}sLTC becomes. This stands in sharp contrast to the classical setting. The complementary, more intuitive result also holds (and is actually much more involved technically to prove in the quantum case): an upper bound on the soundness when the code is defined on bad local expanders. Together we arrive at a quantum upper bound on the soundness of sLTC\text{sLTC}sLTCs set on any graph, which does not hold in the classical case. Many open questions are raised regarding what possible parameters are achievable for qLTC\text{qLTC}qLTCs, and their relation to other objects of interest in quantum information theory. In the appendix we also define a quantum analogue of PCP\text{PCP}PCPs of proximity (PCPP\text{PCPP}PCPPs) and point out that the result of [E. Ben-Sasson et al., SIAM J. Comput., 36 (2006), pp. 889--974] by which PCPP\text{PCPP}PCPPs imply LTC\text{LTC}LTCs with related parameters carries over to the sLTC\text{sLTC}sLTCs. This creates a first link between qLTC\text{qLTC}qLTCs and quantum PCP\text{PCP}PCPs [D. Aharonov, I. Arad, and T. Vidick, ACM SIGACT News Archive, 44 (2013), pp. 47--79].