GPU-accelerated semidefinite programming for causal games

• URL: http://arxiv.org/abs/2606.20519v1
• Date: Thu, 18 Jun 2026 17:36:34 GMT
• Title: GPU-accelerated semidefinite programming for causal games
• Abstract summary: Correlations compatible with any definite, or probabilistically mixed, causal order cannot achieve a winning probability exceeding $1/2$.<n>We investigate whether increasing the local dimension beyond $d = 5$ can narrow this gap.<n>Our results suggest either qualitatively different strategies are required to approach the known upper bound, or that the bound itself is not tight.
• Score: 0.12891210250935145
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The process matrix formalism describes quantum correlations in scenarios without a fixed causal order between local laboratories. Operational signatures of such correlations can be investigated through causal games. A paradigmatic example is the Guess-Your-Neighbour's-Input game, in which two parties attempt to guess each other's inputs. Correlations compatible with any definite, or probabilistically mixed, causal order cannot achieve a winning probability exceeding $1/2$. The best process-matrix strategy currently known attains a value of approximately $0.6218$ using local dimension $d=5$, while the strongest known dimension-independent upper bound is $0.7592$. In this work, we investigate whether increasing the local dimension beyond $d = 5$ can narrow this gap. To this end, we employ a see-saw optimization scheme in which each step is formulated as a semidefinite program. For scalability, we develop a custom implementation of the SCS solver in which the dominant computational cost, the projection onto the positive-semidefinite cone, is offloaded to a GPU, yielding a six-fold speedup. Using this implementation, we explore local dimensions up to $d = 8$, and we do not find significant improvements over the value at $d=5$. Our results suggest that either qualitatively different strategies are required to approach the known upper bound, or that the bound itself is not tight.

Related papers

• Approximating fixed size quantum correlations in polynomial time [8.099700053397278]
  We show that $varepsilon$-additive approximations of the optimal value of fixed-size two-player free games can be computed in time.<n>Our main result is based on novel Bose-symmetric quantum de Finetti theorems tailored for constrained quantum separability problems.
  arXiv  Detail & Related papers  (2025-07-16T15:01:45Z)
• Scalable 3D Registration via Truncated Entry-wise Absolute Residuals [65.04922801371363]
  A $3$D registration approach can process more than ten million ($107$) point pairs with over $99%$ random outliers. We call our method TEAR, as it involves minimizing an outlier-robust loss that computes Truncated Entry-wise Absolute Residuals.
  arXiv  Detail & Related papers  (2024-04-01T04:43:39Z)
• Targeted Variance Reduction: Robust Bayesian Optimization of Black-Box Simulators with Noise Parameters [1.7404865362620803]
  We propose a new Bayesian optimization method called Targeted Variance Reduction (TVR) TVR leverages a novel joint acquisition function over $(mathbfx,boldsymboltheta)$, which targets variance reduction on the objective within the desired region of improvement. We demonstrate the improved performance of TVR over the state-of-the-art in a suite of numerical experiments and an application to the robust design of automobile brake discs.
  arXiv  Detail & Related papers  (2024-03-06T16:03:37Z)
• Optimal, and approximately optimal, quantum strategies for $\mathrm{XOR}^{*}$ and $\mathrm{FFL}$ games [0.0]
  We analyze optimal, and approximately optimal, quantum strategies for a variety of non-local XOR games. We identify additional applications of the framework for analyzing the performance of a broader class of quantum strategies.
  arXiv  Detail & Related papers  (2023-11-21T04:03:26Z)
• Local Convergence of Gradient Methods for Min-Max Games: Partial Curvature Generically Suffices [0.5439020425819]
  We study the convergence to local Nash equilibria of gradient methods for two-player zero-sum differentiable games. We show that thanks to partial curvature, conic particle methods -- which optimize over both weights and supports of the mixed strategies -- generically converge faster than fixed-support methods.
  arXiv  Detail & Related papers  (2023-05-26T21:43:56Z)
• Can We Find Nash Equilibria at a Linear Rate in Markov Games? [95.10091348976779]
  We study decentralized learning in two-player zero-sum discounted Markov games. The goal is to design a policy optimization algorithm for either agent satisfying two properties.
  arXiv  Detail & Related papers  (2023-03-03T02:40:26Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
  We propose the first computationally efficient horizon-free algorithm for linear mixture MDPs. Our algorithm adapts a weighted least square estimator for the unknown transitional dynamic. This also improves upon the best-known algorithms in this setting when $sigma_k2$'s are known.
  arXiv  Detail & Related papers  (2022-05-23T17:59:18Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  We study the statistical limits of Imitation Learning in episodic Markov Decision Processes (MDPs) with a state space $mathcalS$. We establish an upper bound $O(|mathcalS|H3/2/N)$ for the suboptimality using the Mimic-MD algorithm in Rajaraman et al ( 2020) We show the minimax suboptimality grows as $Omega( H3/2/N)$ when $mathcalS|geq 3$ while the unknown-transition setting suffers from a larger sharp rate
  arXiv  Detail & Related papers  (2021-02-25T15:50:19Z)
• Empirical Risk Minimization in the Non-interactive Local Model of Differential Privacy [26.69391745812235]
  We study the Empirical Risk Minimization (ERM) problem in the noninteractive Local Differential Privacy (LDP) model. Previous research indicates that the sample complexity, to achieve error $alpha, needs to be depending on dimensionality $p$ for general loss functions.
  arXiv  Detail & Related papers  (2020-11-11T17:48:00Z)
• Learning Near Optimal Policies with Low Inherent Bellman Error [115.16037976819331]
  We study the exploration problem with approximate linear action-value functions in episodic reinforcement learning. We show that exploration is possible using only emphbatch assumptions with an algorithm that achieves the optimal statistical rate for the setting we consider.
  arXiv  Detail & Related papers  (2020-02-29T02:02:40Z)
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits [0.755972004983746]
  Variational quantum algorithms (VQAs) optimize the parameters $vectheta$ of a parametrized quantum circuit. We prove two results, assuming $V(vectheta)$ is an alternating layered ansatz composed of blocks forming local 2-designs. We illustrate these ideas with large-scale simulations, up to 100 qubits, of a quantum autoencoder implementation.
  arXiv  Detail & Related papers  (2020-01-02T18:18:25Z)

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.