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:2212.11572 · Quantum

Counterexamples in self-testing

Laura Mančinska, Simon Schmidt

Published Jul 11, 2023• 6 citations
arXivHTMLPDF

Abstract

In the recent years self-testing has grown into a rich and active area of study with applications ranging from practical verification of quantum devices to deep complexity theoretic results. Self-testing allows a classical verifier to deduce which quantum measurements and on what state are used, for example, by provers Alice and Bob in a nonlocal game. Hence, self-testing as well as its noise-tolerant cousin – robust self-testing – are desirable features for a nonlocal game to have.Contrary to what one might expect, we have a rather incomplete understanding of if and how self-testing could fail to hold. In particular, could it be that every 2-party nonlocal game or Bell inequality with a quantum advantage certifies the presence of a specific quantum state? Also, is it the case that every self-testing result can be turned robust with enough ingeniuty and effort? We answer these questions in the negative by providing simple and fully explicit counterexamples. To this end, given two nonlocal games G1 and G2 , we introduce the (G1∨G2) -game, in which the players get pairs of questions and choose which game they want to play. The players win if they choose the same game and win it with the answers they have given. Our counterexamples are based on this game and we believe this class of games to be of independent interest.

DOI
10.22331/q-2023-07-11-1051

Related papers

Optimal Robust Self-Testing by Binary Nonlocal XOR Games

Carl A. Miller, Yaoyun Shi

Self-testing a quantum apparatus means verifying the existence of a certain quantum state as well as the effect of the associated measuring devices based only on the statistics of the measurement outcomes. Robust (i.e., error-tolerant) self-testing quantum apparatuses are critical building blocks for quantum cryptographic protocols that rely on imperfect or untrusted devices. We devise a general scheme for proving optimal robust self-testing properties for tests based on nonlocal binary XOR games. We offer some simplified proofs of known results on self-testing, and also prove some new results.

Leibniz international proceedings in informatics•Jan 1, 2013•23 citations

Robust self-testing quantum states and binary nonlocal XOR games

Carl A. Miller, Yaoyun Shi

Self-testing a quantum device means verifying the existence of a certain quantum state as well as the effect of the associated measurements based only on the statistics of the measurement outcomes. Robust, i.e., error-tolerant, self-testing quantum devices are critical building blocks for quantum cryptographic protocols that rely on imperfect or untrusted quantum devices. We give a criterion which determines whether a given binary XOR game is robust self-testing with the asymptotically optimal error parameter. As an application, we prove that the celebrated CHSH game is an optimally robust self-test. We also prove the same for a family of tests recently proposed by Acin et al. (PRL 108:100402, 2012) for random number generation, thus extending the benefit of the latter tests to allow imperfect or untrusted quantum devices.

•Jul 7, 2012•1 citation

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.

arXiv:2505.13537•May 18, 2025•2 citations

Self-Testing of a Single Quantum Device Under Computational Assumptions

Tony Metger, Thomas Vidick

Self-testing is a method to characterise an arbitrary quantum system based only on its classical input-output correlations, and plays an important role in device-independent quantum information processing as well as quantum complexity theory. Prior works on self-testing require the assumption that the system’s state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of multiple non-communicating parties, which is difficult to enforce in practice, by a single computationally bounded party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed single-qubit measurements on it, up to a change of basis applied to both the device’s state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement, a property usually closely associated with two separated subsystems, inside a single quantum device. To achieve this, we build on techniques first introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break post-quantum cryptography.

•Jan 1, 2021•5 citations

The Grothendieck Game and Self-Testing Continuous Groups

Alexander Kulpe, Giulio Malavolta, Simon Schmidt +1 more

Self-testing certifies quantum states and measurements from observed correlations alone, without requiring a description of the devices that produce them. In this work we establish, to the best of our knowledge, the first robust self-test of the full continuous family of measurements generated by Majorana operators. We achieve this by showing that the Grothendieck game, a two-player nonlocal game in which the players receive directions on a sphere and return binary answers, is a self-test of Majorana observables. That is, any near-optimal performance certifies an entire continuously parameterized family of quantum measurements. We further extend this certification to products of Majorana observables, obtaining a robust self-test of the spin representation of the continuous pin group.

quant-pharXiv:2610.06755•Oct 6, 2026•0 citations

Experimentally Robust Self-testing for Bipartite and Tripartite Entangled States

Wen-Hao Zhang, Geng Chen, Xing-Xiang Peng +9 more

Self-testing is a method with which a classical user can certify the state and measurements of quantum systems in a device-independent way. In particular, self-testing of entangled states is of great importance in quantum information processing. An understandable example is that the maximal violation of the Clauser-Horne-Shimony-Holt inequality necessarily implies that the bipartite system shares a singlet. One essential question in self-testing is that, when one observes a nonmaximum violation, how far is the tested state from the target state (which maximally violates a certain Bell inequality)? The answer to this question describes the robustness of the used self-testing criterion, which is highly important in a practical sense. Recently, J. Kaniewski derived two analytic self-testing bounds for bipartite and tripartite systems. In this Letter, we experimentally investigate these two bounds with high-quality two-qubit and three-qubit entanglement sources. The results show that these bounds are valid for various entangled states that we prepared. Thereby, a proof-of-concept demonstration of robust self-testing is achieved, which improves on the previous results significantly.

arXiv:1804.01375•Physical Review Letters•Dec 13, 2018•32 citations
In the recent years self-testing has grown into a rich and active area of study with applications ranging from practical verification of quantum devices to deep complexity theoretic results. Self-testing allows a classical verifier to deduce which quantum measurements and on what state are used, for example, by provers Alice and Bob in a nonlocal game. Hence, self-testing as well as its noise-tolerant cousin – robust self-testing – are desirable features for a nonlocal game to have.Contrary to what one might expect, we have a rather incomplete understanding of if and how self-testing could fail to hold. In particular, could it be that every 2-party nonlocal game or Bell inequality with a quantum advantage certifies the presence of a specific quantum state? Also, is it the case that every self-testing result can be turned robust with enough ingeniuty and effort? We answer these questions in the negative by providing simple and fully explicit counterexamples. To this end, given two nonlocal games G1 and G2 , we introduce the (G1∨G2) -game, in which the players get pairs of questions and choose which game they want to play. The players win if they choose the same game and win it with the answers they have given. Our counterexamples are based on this game and we believe this class of games to be of independent interest.
Self-testing a quantum apparatus means verifying the existence of a certain quantum state as well as the effect of the associated measuring devices based only on the statistics of the measurement outcomes. Robust (i.e., error-tolerant) self-testing quantum apparatuses are critical building blocks for quantum cryptographic protocols that rely on imperfect or untrusted devices. We devise a general scheme for proving optimal robust self-testing properties for tests based on nonlocal binary XOR games. We offer some simplified proofs of known results on self-testing, and also prove some new results.
Self-testing a quantum device means verifying the existence of a certain quantum state as well as the effect of the associated measurements based only on the statistics of the measurement outcomes. Robust, i.e., error-tolerant, self-testing quantum devices are critical building blocks for quantum cryptographic protocols that rely on imperfect or untrusted quantum devices. We give a criterion which determines whether a given binary XOR game is robust self-testing with the asymptotically optimal error parameter. As an application, we prove that the celebrated CHSH game is an optimally robust self-test. We also prove the same for a family of tests recently proposed by Acin et al. (PRL 108:100402, 2012) for random number generation, thus extending the benefit of the latter tests to allow imperfect or untrusted quantum devices.
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.
Self-testing is a method to characterise an arbitrary quantum system based only on its classical input-output correlations, and plays an important role in device-independent quantum information processing as well as quantum complexity theory. Prior works on self-testing require the assumption that the system’s state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of multiple non-communicating parties, which is difficult to enforce in practice, by a single computationally bounded party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed single-qubit measurements on it, up to a change of basis applied to both the device’s state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement, a property usually closely associated with two separated subsystems, inside a single quantum device. To achieve this, we build on techniques first introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break post-quantum cryptography.
Self-testing certifies quantum states and measurements from observed correlations alone, without requiring a description of the devices that produce them. In this work we establish, to the best of our knowledge, the first robust self-test of the full continuous family of measurements generated by Majorana operators. We achieve this by showing that the Grothendieck game, a two-player nonlocal game in which the players receive directions on a sphere and return binary answers, is a self-test of Majorana observables. That is, any near-optimal performance certifies an entire continuously parameterized family of quantum measurements. We further extend this certification to products of Majorana observables, obtaining a robust self-test of the spin representation of the continuous pin group.
Self-testing is a method with which a classical user can certify the state and measurements of quantum systems in a device-independent way. In particular, self-testing of entangled states is of great importance in quantum information processing. An understandable example is that the maximal violation of the Clauser-Horne-Shimony-Holt inequality necessarily implies that the bipartite system shares a singlet. One essential question in self-testing is that, when one observes a nonmaximum violation, how far is the tested state from the target state (which maximally violates a certain Bell inequality)? The answer to this question describes the robustness of the used self-testing criterion, which is highly important in a practical sense. Recently, J. Kaniewski derived two analytic self-testing bounds for bipartite and tripartite systems. In this Letter, we experimentally investigate these two bounds with high-quality two-qubit and three-qubit entanglement sources. The results show that these bounds are valid for various entangled states that we prepared. Thereby, a proof-of-concept demonstration of robust self-testing is achieved, which improves on the previous results significantly.