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:1606.08403 · Physical Review Letters

Nonsignaling Deterministic Models for Nonlocal Correlations have to be Uncomputable

Ariel Bendersky, Gabriel Senno, Gonzalo de la Torre, Santiago Daniel Figueira, Antonio Acín

Published Mar 28, 2017• 19 citations
arXivHTMLPDF

Abstract

Quantum mechanics postulates random outcomes. However, a model making the same output predictions but in a deterministic manner would be, in principle, experimentally indistinguishable from quantum theory. In this work we consider such models in the context of nonlocality on a device-independent scenario. That is, we study pairs of nonlocal boxes that produce their outputs deterministically. It is known that, for these boxes to be nonlocal, at least one of the boxes' outputs has to depend on the other party's input via some kind of hidden signaling. We prove that, if the deterministic mechanism is also algorithmic, there is a protocol that, with the sole knowledge of any upper bound on the time complexity of such an algorithm, extracts that hidden signaling and uses it for the communication of information.

DOI
10.1103/physrevlett.118.130401

Related papers

Quantifying the randomness of copies of noisy Popescu-Rohrlich correlations

Boris Bourdoncle, Stefano Pironio, Antonio Acín

In a no-signaling world, the outputs of a nonlocal box cannot be completely predetermined, a feature that is exploited in many quantum information protocols exploiting nonlocality, such as device-independent randomness generation and quantum key distribution. This relation between nonlocality and randomness can be formally quantified through the min-entropy, a measure of the unpredictability of the outputs that holds conditioned on the knowledge of any adversary that is limited only by the no-signaling principle. This quantity can easily be computed for the noisy Popescu-Rohrlich (PR) box, the paradigmatic example of nonlocality. In this paper, we consider the min-entropy associated to several copies of noisy PR boxes. In the case where $n$ noisy PR boxes are implemented using $n$ noncommunicating pairs of devices, it is known that each PR box behaves as an independent biased coin: the min-entropy per PR box is constant with the number of copies. We show that this does not hold in more general scenarios where several noisy PR boxes are implemented from a single pair of devices, either used sequentially $n$ times or producing $n$ outcome bits in a single run. In this case, the min-entropy per PR box is smaller than the min-entropy of a single PR box, and it decreases as the number of copies increases.

arXiv:1807.04674•Physical Review A•Oct 25, 2018•2 citations

Quantum Nonlocality and Device-Independent Randomness are Robust to Noisy Signaling Channels

Kuntal Sengupta, Lewis Wooltorton

Given a pair of isolated devices that accept random binary inputs and return binary outputs, a user can deduce from the observed data alone if the underlying mechanism can be explained classically. Bell's theorem further states that a classical explanation can be ruled out if the devices perform certain measurements on an entangled quantum state, underpinning the security of cryptographic protocols that are device-independent (DI). For certain protocols, such as those performed in a tight space, it might be difficult to perfectly enforce the non-signaling assumption required in Bell's theorem. This prompts the question: is quantum nonlocality robust to such imperfections? We show that if a binary channel sends a noisy copy of one party's input to the other before any measurements take place, the answer is yes. We completely characterize the vertices and facets of the local polytope in this scenario, and identify Bell inequalities that certify non-signaling quantum correlations. This is possible even when a near perfect copy of the input is sent. We go on to show that the identified inequalities are more robust to depolarizing noise than the Clauser-Horne-Shimony-Holt inequality when certifying DI randomness in this scenario. In addition, we characterize the local polytope when both parties receive a noisy copy of each other's input and make similar conclusions, leaving many new potential Bell inequalities to be explored.

quant-pharXiv:2605.21293•May 21, 2026•0 citations

Nonlocal boxes for networks

Jean-Daniel Bancal, Nicolas Gisin

Nonlocal boxes are conceptual tools that capture the essence of the phenomenon of quantum nonlocality, central to modern quantum theory and quantum technologies. We introduce network nonlocal boxes tailored for quantum networks under the natural assumption that these networks connect independent sources and do not allow signaling. Hence, these boxes satisfy the no-signaling and independence principle. For the case of boxes without inputs, connecting pairs of bipartite sources and producing binary outputs, we prove that the sources and boxes producing local random outputs and maximal two-box correlations, i.e., ${E}_{2}=\sqrt{2}\ensuremath{-}1, {E}_{2}^{o}=1$, are essentially unique.

arXiv:2102.03597•Physical Review A•Nov 17, 2021•22 citations

Device-independent secret sharing and a stronger form of Bell nonlocality

George Moreno, Samuraí Brito, Ranieri Nery +1 more

Bell nonlocality, the fact that local hidden-variable models cannot reproduce the correlations obtained by measurements on entangled states, is a cornerstone in our modern understanding of quantum theory. Apart from its fundamental implications, nonlocality is also at the core of device-independent quantum information processing, the successful implementation of which is achieved without precise knowledge of the physical apparatus. Here we show that a stronger form of Bell nonlocality, for which even some nonlocal hidden-variable models cannot reproduce the quantum predictions, allows us to circumvent possible attacks in the implementation of secret sharing, a paradigmatic communication protocol in which a secret split amid many possibly untrusted parts can be decoded only if they collaborate among themselves.

arXiv:1909.11785•Physical Review A•May 27, 2020•43 citations

Error-free interconversion of nonlocal boxes

András Bodor, Orsolya Kálmán, Mátyás Koniorczyk

Understanding the structure of nonlocal correlations is important in many fields ranging from fundamental questions of physics to device-independent cryptography. We present a protocol that can convert extremal two-party--two-input nonlocal no-signaling boxes of any type into any other extremal two-party--two-input nonlocal no-signaling box perfectly. Our results are exact, and even though the number of required boxes cannot be determined in advance, their expected number is finite. Our protocol is adaptive and demonstrates for the first time the usefulness of using no-signaling boxes in different causal orders by the parties.

arXiv:2201.09554•Physical Review A•Jul 29, 2022•2 citations

Lack of measurement independence can simulate quantum correlations even when signaling can not

Manik Banik

In the Bell scenario, any nonlocal correlation shared between two spatially separated parties can be modeled deterministically either by allowing communications between the two parties or by restricting their free will in choosing the measurement settings. Recently, the Bell scenario has been generalized into a ``semiquantum'' scenario where external quantum inputs are provided to the parties. We show that in the semiquantum scenario, entangled states produce correlations whose deterministic explanation is possible only if measurement independence is reduced. Thus in simulating quantum correlation the semiquantum scenario reveals a qualitative distinction between signaling and measurement dependence which is absent in the Bell scenario. We further show that such distinction is not observed in the ``steering-game'' scenario, a special case of the semiquantum scenario.

arXiv:1304.6425•Physical Review A•Sep 27, 2013•12 citations
Quantum mechanics postulates random outcomes. However, a model making the same output predictions but in a deterministic manner would be, in principle, experimentally indistinguishable from quantum theory. In this work we consider such models in the context of nonlocality on a device-independent scenario. That is, we study pairs of nonlocal boxes that produce their outputs deterministically. It is known that, for these boxes to be nonlocal, at least one of the boxes' outputs has to depend on the other party's input via some kind of hidden signaling. We prove that, if the deterministic mechanism is also algorithmic, there is a protocol that, with the sole knowledge of any upper bound on the time complexity of such an algorithm, extracts that hidden signaling and uses it for the communication of information.
In a no-signaling world, the outputs of a nonlocal box cannot be completely predetermined, a feature that is exploited in many quantum information protocols exploiting nonlocality, such as device-independent randomness generation and quantum key distribution. This relation between nonlocality and randomness can be formally quantified through the min-entropy, a measure of the unpredictability of the outputs that holds conditioned on the knowledge of any adversary that is limited only by the no-signaling principle. This quantity can easily be computed for the noisy Popescu-Rohrlich (PR) box, the paradigmatic example of nonlocality. In this paper, we consider the min-entropy associated to several copies of noisy PR boxes. In the case where nnn noisy PR boxes are implemented using nnn noncommunicating pairs of devices, it is known that each PR box behaves as an independent biased coin: the min-entropy per PR box is constant with the number of copies. We show that this does not hold in more general scenarios where several noisy PR boxes are implemented from a single pair of devices, either used sequentially nnn times or producing nnn outcome bits in a single run. In this case, the min-entropy per PR box is smaller than the min-entropy of a single PR box, and it decreases as the number of copies increases.
Given a pair of isolated devices that accept random binary inputs and return binary outputs, a user can deduce from the observed data alone if the underlying mechanism can be explained classically. Bell's theorem further states that a classical explanation can be ruled out if the devices perform certain measurements on an entangled quantum state, underpinning the security of cryptographic protocols that are device-independent (DI). For certain protocols, such as those performed in a tight space, it might be difficult to perfectly enforce the non-signaling assumption required in Bell's theorem. This prompts the question: is quantum nonlocality robust to such imperfections? We show that if a binary channel sends a noisy copy of one party's input to the other before any measurements take place, the answer is yes. We completely characterize the vertices and facets of the local polytope in this scenario, and identify Bell inequalities that certify non-signaling quantum correlations. This is possible even when a near perfect copy of the input is sent. We go on to show that the identified inequalities are more robust to depolarizing noise than the Clauser-Horne-Shimony-Holt inequality when certifying DI randomness in this scenario. In addition, we characterize the local polytope when both parties receive a noisy copy of each other's input and make similar conclusions, leaving many new potential Bell inequalities to be explored.
Nonlocal boxes are conceptual tools that capture the essence of the phenomenon of quantum nonlocality, central to modern quantum theory and quantum technologies. We introduce network nonlocal boxes tailored for quantum networks under the natural assumption that these networks connect independent sources and do not allow signaling. Hence, these boxes satisfy the no-signaling and independence principle. For the case of boxes without inputs, connecting pairs of bipartite sources and producing binary outputs, we prove that the sources and boxes producing local random outputs and maximal two-box correlations, i.e., ${E}_{2}=\sqrt{2}\ensuremath{-}1, {E}_{2}^{o}=1$, are essentially unique.
Bell nonlocality, the fact that local hidden-variable models cannot reproduce the correlations obtained by measurements on entangled states, is a cornerstone in our modern understanding of quantum theory. Apart from its fundamental implications, nonlocality is also at the core of device-independent quantum information processing, the successful implementation of which is achieved without precise knowledge of the physical apparatus. Here we show that a stronger form of Bell nonlocality, for which even some nonlocal hidden-variable models cannot reproduce the quantum predictions, allows us to circumvent possible attacks in the implementation of secret sharing, a paradigmatic communication protocol in which a secret split amid many possibly untrusted parts can be decoded only if they collaborate among themselves.
Understanding the structure of nonlocal correlations is important in many fields ranging from fundamental questions of physics to device-independent cryptography. We present a protocol that can convert extremal two-party--two-input nonlocal no-signaling boxes of any type into any other extremal two-party--two-input nonlocal no-signaling box perfectly. Our results are exact, and even though the number of required boxes cannot be determined in advance, their expected number is finite. Our protocol is adaptive and demonstrates for the first time the usefulness of using no-signaling boxes in different causal orders by the parties.
In the Bell scenario, any nonlocal correlation shared between two spatially separated parties can be modeled deterministically either by allowing communications between the two parties or by restricting their free will in choosing the measurement settings. Recently, the Bell scenario has been generalized into a ``semiquantum'' scenario where external quantum inputs are provided to the parties. We show that in the semiquantum scenario, entangled states produce correlations whose deterministic explanation is possible only if measurement independence is reduced. Thus in simulating quantum correlation the semiquantum scenario reveals a qualitative distinction between signaling and measurement dependence which is absent in the Bell scenario. We further show that such distinction is not observed in the ``steering-game'' scenario, a special case of the semiquantum scenario.