Lifting the maximally-entangledness assumption in robust self-testing for synchronous games

• URL: http://arxiv.org/abs/2505.05994v1
• Date: Fri, 09 May 2025 12:24:09 GMT
• Title: Lifting the maximally-entangledness assumption in robust self-testing for synchronous games
• Abstract summary: Robust self-testing in non-local games allows a classical referee to certify that two untrustworthy players are able to perform a specific quantum strategy up to high precision.<n>This has been exploited in the celebrated MIP*=RE paper and related articles to prove robust self-testing results for synchronous games when restricting to PME strategies.<n>We prove that any perfect synchronous game which is a robust self-test when restricted to PME strategies, is in fact a robust self-test for all strategies.
• Score: 2.5979734944486648
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Robust self-testing in non-local games allows a classical referee to certify that two untrustworthy players are able to perform a specific quantum strategy up to high precision. Proving robust self-testing results becomes significantly easier when one restricts the allowed strategies to symmetric projective maximally entangled (PME) strategies, which allow natural descriptions in terms of tracial von Neumann algebras. This has been exploited in the celebrated MIP*=RE paper and related articles to prove robust self-testing results for synchronous games when restricting to PME strategies. However, the PME assumptions are not physical, so these results need to be upgraded to make them physically relevant. In this work, we do just that: we prove that any perfect synchronous game which is a robust self-test when restricted to PME strategies, is in fact a robust self-test for all strategies. We then apply our result to the Quantum Low Degree Test to find an efficient $n$-qubit test.

Related papers

• Matching Multiple Experts: On the Exploitability of Multi-Agent Imitation Learning [51.77462571479799]
  Multi-agent imitation learning (MA-IL) aims to learn optimal policies from expert demonstrations of interactions in multi-agent interactive domains.<n>Despite existing guarantees on the performance of the resulting learned policies, characterizations of how far the learned polices are from a Nash equilibrium are missing for offline MA-IL.
  arXiv  Detail & Related papers  (2026-02-24T15:38:11Z)
• On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference [71.09125259964684]
  Test-time compute (TTC) has become an increasingly prominent paradigm for enhancing large language models (LLMs)<n>We study reward-filtered sequential inference, a simple procedure that selectively incorporates only high-reward generations into the context.<n>On the theoretical side, we show that reward-filtered sequential inference yields strictly stronger guarantees than standard TTC paradigms.
  arXiv  Detail & Related papers  (2025-12-04T08:21:33Z)
• Nonlocal Games and Self-tests in the Presence of Noise [9.763471774242237]
  We study self-testing in the high-noise regime.<n>These are the first known self-tests that are robust in the high-noise regime and remain sound even when the players' measurements are noisy.
  arXiv  Detail & Related papers  (2025-09-24T17:45:03Z)
• 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)
• Boosting Certificate Robustness for Time Series Classification with Efficient Self-Ensemble [10.63844868166531]
  Randomized Smoothing has emerged as a standout method due to its ability to certify a provable lower bound on robustness radius under $ell_p$-ball attacks. We propose a self-ensemble method to enhance the lower bound of the probability confidence of predicted labels by reducing the variance of classification margins. This approach also addresses the computational overhead issue of Deep Ensemble(DE) while remaining competitive and, in some cases, outperforming it in terms of robustness.
  arXiv  Detail & Related papers  (2024-09-04T15:22:08Z)
• A Minimaximalist Approach to Reinforcement Learning from Human Feedback [49.45285664482369]
  We present Self-Play Preference Optimization (SPO), an algorithm for reinforcement learning from human feedback. Our approach is minimalist in that it does not require training a reward model nor unstable adversarial training. We demonstrate that on a suite of continuous control tasks, we are able to learn significantly more efficiently than reward-model based approaches.
  arXiv  Detail & Related papers  (2024-01-08T17:55:02Z)
• How to Prune Your Language Model: Recovering Accuracy on the "Sparsity May Cry'' Benchmark [60.72725673114168]
  We revisit the question of accurate BERT-pruning during fine-tuning on downstream datasets. We propose a set of general guidelines for successful pruning, even on the challenging SMC benchmark.
  arXiv  Detail & Related papers  (2023-12-21T03:11:30Z)
• Perturbation-Invariant Adversarial Training for Neural Ranking Models: Improving the Effectiveness-Robustness Trade-Off [107.35833747750446]
  adversarial examples can be crafted by adding imperceptible perturbations to legitimate documents. This vulnerability raises significant concerns about their reliability and hinders the widespread deployment of NRMs. In this study, we establish theoretical guarantees regarding the effectiveness-robustness trade-off in NRMs.
  arXiv  Detail & Related papers  (2023-12-16T05:38:39Z)
• All Real Projective Measurements Can be Self-tested [0.0]
  We show that every real projective measurement can be self-tested. We employ the idea that existing self-tests can be extended to verify additional untrusted measurements. We develop a new technique of iterative self-testing, which involves using post-hoc self-testing in a sequential manner.
  arXiv  Detail & Related papers  (2023-02-02T09:50:13Z)
• Adversarial Attacks and Defense for Non-Parametric Two-Sample Tests [73.32304304788838]
  This paper systematically uncovers the failure mode of non-parametric TSTs through adversarial attacks. To enable TST-agnostic attacks, we propose an ensemble attack framework that jointly minimizes the different types of test criteria. To robustify TSTs, we propose a max-min optimization that iteratively generates adversarial pairs to train the deep kernels.
  arXiv  Detail & Related papers  (2022-02-07T11:18:04Z)
• Glued magic games self-test maximally entangled states [0.0]
  Self-testing results allow us to infer the underlying quantum mechanical description of states and measurements from classical outputs produced by non-communicating parties. We introduce the notion of self-testing convex combinations of reference strategies, which is a generalisation of self-testing to multiple strategies.
  arXiv  Detail & Related papers  (2021-05-22T07:29:55Z)
• Provably Efficient Algorithms for Multi-Objective Competitive RL [54.22598924633369]
  We study multi-objective reinforcement learning (RL) where an agent's reward is represented as a vector. In settings where an agent competes against opponents, its performance is measured by the distance of its average return vector to a target set. We develop statistically and computationally efficient algorithms to approach the associated target set.
  arXiv  Detail & Related papers  (2021-02-05T14:26:00Z)
• Self-testing two-qubit maximally entangled states from generalized CHSH tests [0.0]
  We show how the self-testing of two-qubit maximally entangled states is improved by a refined analysis of measurement statistics. Our results not only provide novel insight into the set of quantum correlations suited for self-testing, but also facilitate the experimental implementations of device-independent certifications.
  arXiv  Detail & Related papers  (2020-11-05T19:00:00Z)
• Adversarial Example Games [51.92698856933169]
  Adrial Example Games (AEG) is a framework that models the crafting of adversarial examples. AEG provides a new way to design adversarial examples by adversarially training a generator and aversa from a given hypothesis class. We demonstrate the efficacy of AEG on the MNIST and CIFAR-10 datasets.
  arXiv  Detail & Related papers  (2020-07-01T19:47:23Z)

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.