Counterexamples in self-testing
- URL: http://arxiv.org/abs/2212.11572v3
- Date: Wed, 5 Jul 2023 13:43:47 GMT
- Title: Counterexamples in self-testing
- Authors: Laura Man\v{c}inska and Simon Schmidt
- Abstract summary: We study self-testing in nonlocal games.
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?
Our counterexamples are based on a class of games to be of independent interest.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- 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 $\mathcal{G}_1$
and $\mathcal{G}_2$, we introduce the $(\mathcal{G}_1 \lor
\mathcal{G}_2)$-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.
Related papers
- Robust self-testing for nonlocal games with robust game algebras [3.069161525997864]
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 prove that self-testing is equivalent to the uniqueness of finite-dimensional tracial states on the associated game algebra.
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.
arXiv Detail & Related papers (2024-11-05T16:55:39Z) - A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
A cryptographic compiler converts any nonlocal game into an interactive protocol with a single computationally bounded prover.
We establish a quantum soundness result for all compiled two-player nonlocal games.
arXiv Detail & Related papers (2024-08-13T08:11:56Z) - Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before.
In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings.
arXiv Detail & Related papers (2024-06-23T00:27:28Z) - Photonic implementation of the quantum Morra game [69.65384453064829]
We study a faithful translation of a two-player quantum Morra game, which builds on previous work by including the classical game as a special case.
We propose a natural deformation of the game in the quantum regime in which Alice has a winning advantage, breaking the balance of the classical game.
We discuss potential applications of the quantum Morra game to the study of quantum information and communication.
arXiv Detail & Related papers (2023-11-14T19:41:50Z) - Decidability of fully quantum nonlocal games with noisy maximally
entangled states [5.076419064097734]
This paper considers the decidability of fully quantum nonlocal games with noisy maximally entangled states.
We prove that there is a computable upper bound on the copies of noisy maximally entangled states for the players to win a fully quantum nonlocal game with a probability arbitrarily close to the quantum value.
arXiv Detail & Related papers (2022-11-19T08:11:02Z) - Connes implies Tsirelson: a simple proof [91.3755431537592]
We show that the Connes embedding problem implies the synchronous Tsirelson conjecture.
We also give a different construction of Connes' algebra $mathcalRomega$ appearing in the Connes embedding problem.
arXiv Detail & Related papers (2022-09-16T13:59:42Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
We develop the concepts of Mean-Field correlated and coarse-correlated equilibria.
We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
arXiv Detail & Related papers (2022-08-22T08:31:46Z) - Quantum guessing games with posterior information [68.8204255655161]
A quantum guessing game with posterior information uses quantum systems to encode messages and classical communication to give partial information after a quantum measurement has been performed.
We formalize symmetry of guessing games and characterize the optimal measurements in cases where the symmetry is related to an irreducible representation.
arXiv Detail & Related papers (2021-07-25T19:10:26Z) - Practical parallel self-testing of Bell states via magic rectangles [0.0]
Self-testing is a method to verify that one has a particular quantum state from purely classical statistics.
We use the $3 times n$ magic rectangle games to obtain a self-test for $n$ Bell states where the one side needs only to measure single-qubit Pauli observables.
arXiv Detail & Related papers (2021-05-09T23:07:18Z) - Quantum-over-classical Advantage in Solving Multiplayer Games [0.0]
Subtraction games are sometimes referred to as one-heap Nim games.
In quantum game theory, a subset of Subtraction games became the first explicitly defined class of zero-sum games.
For a narrower subset of Subtraction games, an exact quantum sublinear algorithm is known that surpasses all deterministic algorithms.
arXiv Detail & Related papers (2020-06-12T06:36:07Z) - Complexity limitations on one-turn quantum refereed games [0.6091702876917281]
The paper studies theoretic aspects of quantum refereed games.
The abstract games are between two competing players that send quantum states to a referee.
The referee performs an efficiently implementable joint measurement on the two states to determine which of the player wins.
arXiv Detail & Related papers (2020-02-04T19:28:03Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.