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:1609.05550 · Journal of Logic and Computation

On the computational complexity of detecting possibilistic locality

Andrew W. Simmons

Published Dec 6, 2017• 4 citations
arXivHTMLPDF

Abstract

The proofs of quantum nonlocality due to Greenberger, Horne and Zeilinger and due to Hardy are qualitatively different from that of Bell insofar as they rely only on a consideration of whether events are possible or impossible, rather than relying on specific experimental probabilities. We consider the scenario of a bipartite nonlocality experiment, in which two separated experimenters each have access to some measurements they can perform on a system. In a physical theory, some outcomes of this experiment will be labelled possible, others impossible, and an assignment of the values 0 (impossible) and 1 (possible) to these different outcomes forms a table of possibilities. Here, we consider the computational task of determining whether or not a given table of possibilities constitutes a departure from possibilistic local realism. By considering the case in which one party has access to measurements with two outcomes and the other three, it is possible to see at exactly which point this task becomes computationally difficult.

DOI
10.1093/logcom/exx045

Related papers

Possibilistic approach to network nonlocality

Antoine Restivo, Nicolas Brunner, Denis Rosset

The investigation of Bell nonlocality traditionally relies on joint probabilities of observing certain measurement outcomes. In this work we explore a possibilistic approach, where only patterns of possible outcomes matter, and apply it to Bell nonlocality in networks with independent sources. We present various algorithms for determining whether a given outcome pattern can be achieved via classical resources or via non-signaling resources. Next we illustrate these methods considering the triangle and square networks (with binary outputs and no inputs), identifying patterns that are incompatible with the network structure, as well as patterns that imply nonlocality. In particular, we obtain an example of quantum nonlocality in the square network with binary outcomes. Moreover, we show how to construct certificates for detecting the nonlocality of a certain pattern, in the form of nonlinear Bell-type inequalities involving joint probabilities. Finally, we show that these inequalities remain valid in the case where the sources in the network become partially correlated.

arXiv:2208.13526•Aug 29, 2022•0 citations

Extreme nonlocality with one photon

Libby Heaney, Adán Cabello, Marcelo França Santos +1 more

Quantum nonlocality is typically assigned to systems of two or more well-separated particles, but nonlocality can also exist in systems consisting of just a single particle when one considers the subsystems to be distant spatial field modes. Single particle nonlocality has been confirmed experimentally via a bipartite Bell inequality. In this paper, we introduce an N -party Hardy-like proof of the impossibility of local elements of reality and a Bell inequality for local realistic theories in the case of a single particle superposed symmetrically over N spatial field modes (i.e. N qubit W state). We show that, in the limit of large N , the Hardy-like proof effectively becomes an all-versus-nothing (or Greenberger–Horne–Zeilinger (GHZ)-like) proof, and the quantum-classical gap of the Bell inequality tends to be the same as that in a three-particle GHZ experiment. We describe how to test the nonlocality in realistic systems.

arXiv:0911.0770•New Journal of Physics•May 27, 2011•82 citations

Bayesian Analysis of Bell Inequalities

Asher Peres

Statistical tests are needed to determine experimentally whether a hypothetical theory based on local realism can be an acceptable alternative to quantum mechanics. It is impossible to rule out local realism by a single test, as often claimed erroneously. The “strength” of a particular Bell inequality is measured by the number of trials that are needed to invalidate local realism at a given confidence level. Various versions of Bell's inequality are compared from this point of view. It is shown that Mermin's inequality for Greenberger-Horne-Zeilinger states requires fewer tests than the Clauser-Horne-Shimony-Holt inequality or than its chained variants applied to a singlet state, and also than Hardy's proof of nonlocality.

Fortschritte der Physik•May 1, 2000•2 citations

Bayesian Analysis of Bell Inequalities

Asher Peres

Statistical tests are needed to determine experimentally whether a hypothetical theory based on local realism can be an acceptable alternative to quantum mechanics. It is impossible to rule out local realism by a single test, as often claimed erroneously. The “strength” of a particular Bell inequality is measured by the number of trials that are needed to invalidate local realism at a given confidence level. Various versions of Bell's inequality are compared from this point of view. It is shown that Mermin's inequality for Greenberger-Horne-Zeilinger states requires fewer tests than the Clauser-Horne-Shimony-Holt inequality or than its chained variants applied to a singlet state, and also than Hardy's proof of nonlocality.

arXiv:quant-ph/9905084•Fortschritte der Physik•May 1, 2000•25 citations

Nonlocality in multipartite correlation networks

Lars Erik Würflinger

Despite the success of quantum mechanics in predicting the outcomes of experiments in many branches of physics, the foundations of the theory have remained subject of research and dispute. At the basis of this struggle with the theory lie the phenomena of nonlocality and entanglement. Since it was first predicted by Bell in 1964, nonlocality was not only verified in numerous experiments, but also identified as a useful resource for quantum information processing. Thus, the study of nonlocality is important both from a fundamental point of view and with respect to new applications in quantum information theory, such as secure cryptography and randomness generation. The identification of entanglement as a resource for quantum information led to a strong theoretical effort devoted to its characterisation and detection. Many of the resulting mathematical tools find application in several domains of physics. Although the only known way to create nonlocal correlations is to measure entangled quantum systems, it has been shown that entanglement and nonlocality constitute two inequivalent properties. Therefore, in the light of the success of entanglement theory, it is of interest to also devise a resource theory of nonlocality. The task of this thesis is to develop such a theoretical framework for the characterisation of nonlocality as a resource. To gain a better understanding of nonlocal correlations it will be necessary to investigate correlation scenarios that go beyond the situation originally considered by Bell. In doing so, this thesis provides new description of nonlocality that also have implications for the characterisation of quantum correlations and the detection of new forms of nonlocality. The first question we address is how nonlocality can consistently be defined in a scenario of arbitrarily many parties that may collaborate among each other. To this end we recognise which are the allowed physical operations in this situation and then define nonlocality as the resource that cannot be created by these operations. Our approach shows that the conventional definition of multipartite nonlocality, adopted by the community so far, is inconsistent with this operational definition; we further propose and analyse new models that do not suffer from these inconsistencies. Furthermore, we show that our findings have implications for the characterisation of quantum correlations. A recent approach to describe the set of quantum correlation consists in using principles inspired from information theory. By using a special instance of the models we defined earlier we show a fundamental limitation of this approach: no bipartite information principle is sufficient to single out the set of quantum correlations from the set of nonsignalling correlations. We then developed a description of nonlocality in an even more generalised scenario of several parties. Motivated by a result of Popescu we study scenarios where the parties are allowed to perform not only a single but sequences of measurements on their systems. Characterising nonlocality also in this scenario in operational terms and defining local models compatible with this definition, we show that a new form of nonlocality can be detected Lastly, we examine the problem of detecting the presence of nonlocality in a multipartite scenario when one is given only partial access to the global system. We find that one can verify that the total system must display nonlocality, even though the accessible subsystems only exhibit local correlations.

•Sep 18, 2013•0 citations

The Statistical Strength of Nonlocality Proofs

W. vanDam, Richard David Gill, P.D. Grunwald

There exist numerous proofs of Bell's theorem, stating that quantum mechanics is incompatible with local realistic theories of nature. Here the strength of such nonlocality proofs is defined in terms of the amount of evidence against local realism provided by the corresponding experiments. Statistical considerations show that the amount of evidence should be measured by the Kullback-Leibler (KL) or relative entropy divergence. The statistical strength of the following proofs is determined: Bell's original proof and Peres' optimized variant of it, and proofs by Clauser, Horne, Shimony, and Holt (CHSH), Hardy, Mermin, and Greenberger, Horne, and Zeilinger (GHZ). The GHZ proof is at least four and a half times stronger than all other proofs, while of the two-party proofs, the one of CHSH is the strongest.

arXiv:quant-ph/0307125•IEEE Transactions on Information Theory•Jul 19, 2005•5 citations
The proofs of quantum nonlocality due to Greenberger, Horne and Zeilinger and due to Hardy are qualitatively different from that of Bell insofar as they rely only on a consideration of whether events are possible or impossible, rather than relying on specific experimental probabilities. We consider the scenario of a bipartite nonlocality experiment, in which two separated experimenters each have access to some measurements they can perform on a system. In a physical theory, some outcomes of this experiment will be labelled possible, others impossible, and an assignment of the values 0 (impossible) and 1 (possible) to these different outcomes forms a table of possibilities. Here, we consider the computational task of determining whether or not a given table of possibilities constitutes a departure from possibilistic local realism. By considering the case in which one party has access to measurements with two outcomes and the other three, it is possible to see at exactly which point this task becomes computationally difficult.
The investigation of Bell nonlocality traditionally relies on joint probabilities of observing certain measurement outcomes. In this work we explore a possibilistic approach, where only patterns of possible outcomes matter, and apply it to Bell nonlocality in networks with independent sources. We present various algorithms for determining whether a given outcome pattern can be achieved via classical resources or via non-signaling resources. Next we illustrate these methods considering the triangle and square networks (with binary outputs and no inputs), identifying patterns that are incompatible with the network structure, as well as patterns that imply nonlocality. In particular, we obtain an example of quantum nonlocality in the square network with binary outcomes. Moreover, we show how to construct certificates for detecting the nonlocality of a certain pattern, in the form of nonlinear Bell-type inequalities involving joint probabilities. Finally, we show that these inequalities remain valid in the case where the sources in the network become partially correlated.
Quantum nonlocality is typically assigned to systems of two or more well-separated particles, but nonlocality can also exist in systems consisting of just a single particle when one considers the subsystems to be distant spatial field modes. Single particle nonlocality has been confirmed experimentally via a bipartite Bell inequality. In this paper, we introduce an N -party Hardy-like proof of the impossibility of local elements of reality and a Bell inequality for local realistic theories in the case of a single particle superposed symmetrically over N spatial field modes (i.e. N qubit W state). We show that, in the limit of large N , the Hardy-like proof effectively becomes an all-versus-nothing (or Greenberger–Horne–Zeilinger (GHZ)-like) proof, and the quantum-classical gap of the Bell inequality tends to be the same as that in a three-particle GHZ experiment. We describe how to test the nonlocality in realistic systems.
Statistical tests are needed to determine experimentally whether a hypothetical theory based on local realism can be an acceptable alternative to quantum mechanics. It is impossible to rule out local realism by a single test, as often claimed erroneously. The “strength” of a particular Bell inequality is measured by the number of trials that are needed to invalidate local realism at a given confidence level. Various versions of Bell's inequality are compared from this point of view. It is shown that Mermin's inequality for Greenberger-Horne-Zeilinger states requires fewer tests than the Clauser-Horne-Shimony-Holt inequality or than its chained variants applied to a singlet state, and also than Hardy's proof of nonlocality.
Statistical tests are needed to determine experimentally whether a hypothetical theory based on local realism can be an acceptable alternative to quantum mechanics. It is impossible to rule out local realism by a single test, as often claimed erroneously. The “strength” of a particular Bell inequality is measured by the number of trials that are needed to invalidate local realism at a given confidence level. Various versions of Bell's inequality are compared from this point of view. It is shown that Mermin's inequality for Greenberger-Horne-Zeilinger states requires fewer tests than the Clauser-Horne-Shimony-Holt inequality or than its chained variants applied to a singlet state, and also than Hardy's proof of nonlocality.
Despite the success of quantum mechanics in predicting the outcomes of experiments in many branches of physics, the foundations of the theory have remained subject of research and dispute. At the basis of this struggle with the theory lie the phenomena of nonlocality and entanglement. Since it was first predicted by Bell in 1964, nonlocality was not only verified in numerous experiments, but also identified as a useful resource for quantum information processing. Thus, the study of nonlocality is important both from a fundamental point of view and with respect to new applications in quantum information theory, such as secure cryptography and randomness generation. The identification of entanglement as a resource for quantum information led to a strong theoretical effort devoted to its characterisation and detection. Many of the resulting mathematical tools find application in several domains of physics. Although the only known way to create nonlocal correlations is to measure entangled quantum systems, it has been shown that entanglement and nonlocality constitute two inequivalent properties. Therefore, in the light of the success of entanglement theory, it is of interest to also devise a resource theory of nonlocality. The task of this thesis is to develop such a theoretical framework for the characterisation of nonlocality as a resource. To gain a better understanding of nonlocal correlations it will be necessary to investigate correlation scenarios that go beyond the situation originally considered by Bell. In doing so, this thesis provides new description of nonlocality that also have implications for the characterisation of quantum correlations and the detection of new forms of nonlocality. The first question we address is how nonlocality can consistently be defined in a scenario of arbitrarily many parties that may collaborate among each other. To this end we recognise which are the allowed physical operations in this situation and then define nonlocality as the resource that cannot be created by these operations. Our approach shows that the conventional definition of multipartite nonlocality, adopted by the community so far, is inconsistent with this operational definition; we further propose and analyse new models that do not suffer from these inconsistencies. Furthermore, we show that our findings have implications for the characterisation of quantum correlations. A recent approach to describe the set of quantum correlation consists in using principles inspired from information theory. By using a special instance of the models we defined earlier we show a fundamental limitation of this approach: no bipartite information principle is sufficient to single out the set of quantum correlations from the set of nonsignalling correlations. We then developed a description of nonlocality in an even more generalised scenario of several parties. Motivated by a result of Popescu we study scenarios where the parties are allowed to perform not only a single but sequences of measurements on their systems. Characterising nonlocality also in this scenario in operational terms and defining local models compatible with this definition, we show that a new form of nonlocality can be detected Lastly, we examine the problem of detecting the presence of nonlocality in a multipartite scenario when one is given only partial access to the global system. We find that one can verify that the total system must display nonlocality, even though the accessible subsystems only exhibit local correlations.
There exist numerous proofs of Bell's theorem, stating that quantum mechanics is incompatible with local realistic theories of nature. Here the strength of such nonlocality proofs is defined in terms of the amount of evidence against local realism provided by the corresponding experiments. Statistical considerations show that the amount of evidence should be measured by the Kullback-Leibler (KL) or relative entropy divergence. The statistical strength of the following proofs is determined: Bell's original proof and Peres' optimized variant of it, and proofs by Clauser, Horne, Shimony, and Holt (CHSH), Hardy, Mermin, and Greenberger, Horne, and Zeilinger (GHZ). The GHZ proof is at least four and a half times stronger than all other proofs, while of the two-party proofs, the one of CHSH is the strongest.