Leibniz international proceedings in informatics

Optimal Robust Self-Testing by Binary Nonlocal XOR Games

Carl A. Miller, Yaoyun Shi

Published Jan 1, 2013• 21 citations

Abstract

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.

DOI: 10.4230/lipics.tqc.2013.254

Related papers

Optimal robust quantum self-testing by 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.

arXiv:1207.1819Jul 7, 201224 citations

Robust self-testing quantum states and binary nonlocal XOR games

Carl A. Miller, Yaoyun Shi

Jul 7, 20122 citations

A non-robust quantum correlation self-test

Ranyiliu Chen, Yuming Zhao

We show that exact self-testing of a quantum correlation does not imply robust self-testing. Mančinska and Schmidt previously established such a separation for non-local games, but their obstruction to robustness arises from two distinct optimal correlations, with the self-tested one remaining robust. We establish the separation for a single correlation. Our proof is operator-algebraic. The main technical contribution is a general construction that associates a synchronous binary correlation to any finitely presented C*-algebra with unitary generators and real-coefficient relations. The implementing states of the correlation correspond exactly to the tracial states on the algebra. We apply this construction to an algebra with a unique finite-dimensional tracial state and a distinct amenable tracial state. By a characterization established by Zhao and independently by Kar, the resulting correlation is a self-test but not a robust self-test.

quant-pharXiv:2609.25117Sep 22, 20260 citations

Counterexamples in self-testing

Laura Mančinska, Simon Schmidt

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.

arXiv:2212.11572QuantumJul 11, 20231 citation

Robust self-testing for nonlocal games with robust game algebras

Yuming Zhao

We give an operator-algebraic formulation of robust self-testing in terms of states on C*-algebras. We show that a quantum correlation p is a robust self-test only if among all (abstract) states, there is a unique one achieving p. We show that the "if" direction of this statement also holds, provided that p is optimal/perfect for a nonlocal game that has a robust game algebra. This last condition applies to many nonlocal games of interest, including all XOR games, synchronous games, and boolean constrained system (BCS) games. For those nonlocal games with robust game algebras, we prove that self-testing is equivalent to the uniqueness of finite-dimensional tracial states on the associated game algebra, and robust self-testing is equivalent to the uniqueness of amenable tracial states. Applying this tracial-state characterization of self-testing to parallel repetition, we show that a synchronous game is a self-test for perfect quantum strategies if and only if its parallel repeated version is a self-test for perfect quantum strategies. As a proof approach, we give the first quantitative Gower-Hatami theorem that is applicable to C*-algebras. Here "quantitative" means there is a constructive bound on the distance between the approximate representations and exact representations. We also demonstrate how this quantitative Gowers-Hatami theorem can be used to calculate the explicit robustness function of a self-test.

arXiv:2411.03259Nov 5, 20240 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.

arXiv:2505.13537May 18, 20250 citations