In this work we construct tests that allow a classical user to certify high dimensional entanglement in uncharacterized and possibly noisy quantum devices. We present a family of non-local games $\{G_n\}$ that for all $n$ certify states with entanglement of formation $Ω(n)$ . These tests can be derived from any bipartite non-local game with a classical-quantum gap. Furthermore, our tests are noise-tolerant in the sense that fault tolerant technologies are not needed to play the games; entanglement distributed over noisy channels can pass with high probability, making our tests relevant for realistic experimental settings. This is in contrast to, e.g., results on self-testing of high dimensional entanglement, which are only relevant when the noise rate goes to zero with the system's size $n$ . As a corollary of our result, we supply a lower-bound on the entanglement cost of any state achieving a quantum advantage in a bipartite non-local game. Our proof techniques heavily rely on ideas from the work on classical and quantum parallel repetition theorems.In this work we construct tests that allow a classical user to certify high dimensional entanglement in uncharacterized and possibly noisy quantum devices. We present a family of non-local games $\{G_n\}$ that for all $n$ certify states with entanglement of formation $Ω(n)$. These tests can be derived from any bipartite non-local game with a classical-quantum gap. Furthermore, our tests are noise-tolerant in the sense that fault tolerant technologies are not needed to play the games; entanglement distributed over noisy channels can pass with high probability, making our tests relevant for realistic experimental settings. This is in contrast to, e.g., results on self-testing of high dimensional entanglement, which are only relevant when the noise rate goes to zero with the system's size $n$. As a corollary of our result, we supply a lower-bound on the entanglement cost of any state achieving a quantum advantage in a bipartite non-local game. Our proof techniques heavily rely on ideas from the work on classical and quantum parallel repetition theorems.

arXiv:1712.09368Dec 26, 20175 citations

Non-local games and communication complexity with noisy entanglement

Srijita Kundu, Olivier Lalonde

We study the impact of noise on the theories of quantum nonlocality and entanglement-assisted communication complexity. We consider non-local games and entanglement-assisted communication complexity in a model where Alice and Bob may share arbitrarily many noisy EPR pairs. We study four noise models: depolarizing noise, unital noise, biased reset noise, and erasure noise. Our results are as follows: 1. We upper bound the value of the CHSH game under all these noise models in terms of the noise parameter, without any assumptions on the measurements used in the strategy. 2. We prove a parallel repetition theorem for general non-local games under all noise models except biased reset noise; we prove an improved parallel repetition theorem for unique games. Our parallel repetition rate is smaller than the quantum parallel repetition rate for CHSH in a nontrivial noise regime. 3. Using our unique-game parallel repetition theorem and a relation defined by the CHSH game, we prove a separation between communication complexity with noisy vs noiseless entanglement. This implies an $Ω(n)$ two-way communication lower bound for distilling $n$ EPR pairs from noisy EPR pairs, in the same nontrivial noise regime. 4. We show that any interactive entanglement-assisted communication protocol can be simulated by an SMP communication protocol with noisy shared randomness, with an exponential blowup in communication. This generalizes a known result on the simulation of noiseless shared randomness with noisy shared randomness. 5. We show a polynomial lower bound on the number of copies of noisy EPR pairs required to compute the Equality function with constant communication, under all four noise models. The previous result gives a matching upper bound, and moreover, this answers an open question in the literature on whether logarithmically many noisy shared bits suffice for communication.We study the impact of noise on the theories of quantum nonlocality and entanglement-assisted communication complexity. We consider non-local games and entanglement-assisted communication complexity in a model where Alice and Bob may share arbitrarily many noisy EPR pairs. We study four noise models: depolarizing noise, unital noise, biased reset noise, and erasure noise. Our results are as follows: 1. We upper bound the value of the CHSH game under all these noise models in terms of the noise parameter, without any assumptions on the measurements used in the strategy. 2. We prove a parallel repetition theorem for general non-local games under all noise models except biased reset noise; we prove an improved parallel repetition theorem for unique games. Our parallel repetition rate is smaller than the quantum parallel repetition rate for CHSH in a nontrivial noise regime. 3. Using our unique-game parallel repetition theorem and a relation defined by the CHSH game, we prove a separation between communication complexity with noisy vs noiseless entanglement. This implies an $Ω(n)$ two-way communication lower bound for distilling $n$ EPR pairs from noisy EPR pairs, in the same nontrivial noise regime. 4. We show that any interactive entanglement-assisted communication protocol can be simulated by an SMP communication protocol with noisy shared randomness, with an exponential blowup in communication. This generalizes a known result on the simulation of noiseless shared randomness with noisy shared randomness. 5. We show a polynomial lower bound on the number of copies of noisy EPR pairs required to compute the Equality function with constant communication, under all four noise models. The previous result gives a matching upper bound, and moreover, this answers an open question in the literature on whether logarithmically many noisy shared bits suffice for communication.

quant-pharXiv:2609.05122Sep 7, 20260 citations

Noise-Robust Self-Testing: Detecting Non-Locality in Noisy Non-Local Inputs

Romi Lifshitz

Non-local games test for non-locality and entanglement in quantum systems and are used in self-tests for certifying quantum states in untrusted devices. However, these protocols are tailored to ideal states, so realistic noise prevents maximal violations and leaves many partially non-local states undetected. Selecting self-tests based on their 'robustness' to noise can tailor protocols to specific applications, but current literature lacks a standardized measure of noise-robustness. Creating such a measure is challenging as there is no operational measure for comparing tests of different dimensionalities and input-output settings. We propose and study three comparative measures: noise-tolerance, convincingness, and an analytic approximation of convincingness called the gapped score. Our computational experiments and analytic framework demonstrate that convincingness provides the most nuanced measure for noise-robustness. We then show that the CHSH game has the highest noise-robustness compared to more complex games (2-CHSH variants and the Magic Square Game) when given equal resources, while with unequal resources, some 2-CHSH variants can outperform CHSH at a high resource cost. This work provides the first systematic and operational framework for comparing noise-robustness in self-testing protocols, laying a foundation for theoretical advances in understanding noise-robustness of self-tests and practical improvements in quantum resource utilization.Non-local games test for non-locality and entanglement in quantum systems and are used in self-tests for certifying quantum states in untrusted devices. However, these protocols are tailored to ideal states, so realistic noise prevents maximal violations and leaves many partially non-local states undetected. Selecting self-tests based on their 'robustness' to noise can tailor protocols to specific applications, but current literature lacks a standardized measure of noise-robustness. Creating such a measure is challenging as there is no operational measure for comparing tests of different dimensionalities and input-output settings. We propose and study three comparative measures: noise-tolerance, convincingness, and an analytic approximation of convincingness called the gapped score. Our computational experiments and analytic framework demonstrate that convincingness provides the most nuanced measure for noise-robustness. We then show that the CHSH game has the highest noise-robustness compared to more complex games (2-CHSH variants and the Magic Square Game) when given equal resources, while with unequal resources, some 2-CHSH variants can outperform CHSH at a high resource cost. This work provides the first systematic and operational framework for comparing noise-robustness in self-testing protocols, laying a foundation for theoretical advances in understanding noise-robustness of self-tests and practical improvements in quantum resource utilization.

arXiv:2505.13537May 18, 20250 citations

Semi-device-independent characterization of multipartite entanglement of states and measurements

Armin Tavakoli, Alastair A. Abbott, Marc-Olivier Renou +2 more

The semi-device-independent framework allows one to draw conclusions about properties of an unknown quantum system under weak assumptions. Here we present a semi-device-independent scheme for the characterization of multipartite entanglement based around a game played by several isolated parties whose devices are uncharacterized beyond an assumption about the dimension of their Hilbert spaces. Our scheme can simultaneously certify that an $n$ -partite high-dimensional quantum state features genuine multipartite entanglement, and that a joint measurement on $n$ subsystems is entangled. Moreover, it provides a lower bound on the number of entangled measurement operators. These tests are strongly robust to noise, and even optimal for certain classes of states and measurements, as we demonstrate with illustrative examples. Notably, our scheme allows the certification of many entangled states admitting a local model, which therefore cannot violate any Bell inequality.The semi-device-independent framework allows one to draw conclusions about properties of an unknown quantum system under weak assumptions. Here we present a semi-device-independent scheme for the characterization of multipartite entanglement based around a game played by several isolated parties whose devices are uncharacterized beyond an assumption about the dimension of their Hilbert spaces. Our scheme can simultaneously certify that an $n$-partite high-dimensional quantum state features genuine multipartite entanglement, and that a joint measurement on $n$ subsystems is entangled. Moreover, it provides a lower bound on the number of entangled measurement operators. These tests are strongly robust to noise, and even optimal for certain classes of states and measurements, as we demonstrate with illustrative examples. Notably, our scheme allows the certification of many entangled states admitting a local model, which therefore cannot violate any Bell inequality.

arXiv:1805.00377Physical Review ANov 26, 201830 citations

All pure bipartite entangled states can be self-tested

Andrea Coladangelo, Koon Tong Goh, Valerio Scarani

Quantum technologies promise advantages over their classical counterparts in the fields of computation, security and sensing. It is thus desirable that classical users are able to obtain guarantees on quantum devices, even without any knowledge of their inner workings. That such classical certification is possible at all is remarkable: it is a consequence of the violation of Bell inequalities by entangled quantum systems. Device-independent self-testing refers to the most complete such certification: it enables a classical user to uniquely identify the quantum state shared by uncharacterized devices by simply inspecting the correlations of measurement outcomes. Self-testing was first demonstrated for the singlet state and a few other examples of self-testable states were reported in recent years. Here, we address the long-standing open question of whether every pure bipartite entangled state is self-testable. We answer it affirmatively by providing explicit self-testing correlations for all such states.Quantum technologies promise advantages over their classical counterparts in the fields of computation, security and sensing. It is thus desirable that classical users are able to obtain guarantees on quantum devices, even without any knowledge of their inner workings. That such classical certification is possible at all is remarkable: it is a consequence of the violation of Bell inequalities by entangled quantum systems. Device-independent self-testing refers to the most complete such certification: it enables a classical user to uniquely identify the quantum state shared by uncharacterized devices by simply inspecting the correlations of measurement outcomes. Self-testing was first demonstrated for the singlet state and a few other examples of self-testable states were reported in recent years. Here, we address the long-standing open question of whether every pure bipartite entangled state is self-testable. We answer it affirmatively by providing explicit self-testing correlations for all such states.

arXiv:1611.08062Nature CommunicationsMay 26, 2017199 citations

Test for a large amount of entanglement, using few measurements

Rui Chao, Ben W. Reichardt, Chris Sutherland +1 more

Bell-inequality violations establish that two systems share some quantum entanglement. We give a simple test to certify that two systems share an asymptotically large amount of entanglement, n EPR states. The test is efficient: unlike earlier tests that play many games, in sequence or in parallel, our test requires only one or two CHSH games. One system is directed to play a CHSH game on a random specified qubit i , and the other is told to play games on qubits {i,j} , without knowing which index is i .The test is robust: a success probability within δ of optimal guarantees distance O(n5/2δ) from n EPR states. However, the test does not tolerate constant δ ; it breaks down for δ=Ω~(1/n) . We give an adversarial strategy that succeeds within delta of the optimum probability using only O~(δ−2) EPR states.Bell-inequality violations establish that two systems share some quantum entanglement. We give a simple test to certify that two systems share an asymptotically large amount of entanglement, n EPR states. The test is efficient: unlike earlier tests that play many games, in sequence or in parallel, our test requires only one or two CHSH games. One system is directed to play a CHSH game on a random specified qubit i , and the other is told to play games on qubits {i,j} , without knowing which index is i .The test is robust: a success probability within δ of optimal guarantees distance O(n5/2δ) from n EPR states. However, the test does not tolerate constant δ ; it breaks down for δ=Ω~(1/n) . We give an adversarial strategy that succeeds within delta of the optimum probability using only O~(δ−2) EPR states.

arXiv:1610.00771QuantumSep 3, 201823 citations

In this work we construct tests that allow a classical user to certify high dimensional entanglement in uncharacterized and possibly noisy quantum devices. We present a family of non-local games

\{G_n\}

that for all

n

certify states with entanglement of formation

Ω(n)

. These tests can be derived from any bipartite non-local game with a classical-quantum gap. Furthermore, our tests are noise-tolerant in the sense that fault tolerant technologies are not needed to play the games; entanglement distributed over noisy channels can pass with high probability, making our tests relevant for realistic experimental settings. This is in contrast to, e.g., results on self-testing of high dimensional entanglement, which are only relevant when the noise rate goes to zero with the system's size

n

. As a corollary of our result, we supply a lower-bound on the entanglement cost of any state achieving a quantum advantage in a bipartite non-local game. Our proof techniques heavily rely on ideas from the work on classical and quantum parallel repetition theorems.

Ω(n)

two-way communication lower bound for distilling

n

EPR pairs from noisy EPR pairs, in the same nontrivial noise regime. 4. We show that any interactive entanglement-assisted communication protocol can be simulated by an SMP communication protocol with noisy shared randomness, with an exponential blowup in communication. This generalizes a known result on the simulation of noiseless shared randomness with noisy shared randomness. 5. We show a polynomial lower bound on the number of copies of noisy EPR pairs required to compute the Equality function with constant communication, under all four noise models. The previous result gives a matching upper bound, and moreover, this answers an open question in the literature on whether logarithmically many noisy shared bits suffice for communication.

n

-partite high-dimensional quantum state features genuine multipartite entanglement, and that a joint measurement on

n

subsystems is entangled. Moreover, it provides a lower bound on the number of entangled measurement operators. These tests are strongly robust to noise, and even optimal for certain classes of states and measurements, as we demonstrate with illustrative examples. Notably, our scheme allows the certification of many entangled states admitting a local model, which therefore cannot violate any Bell inequality.