Optimal, and approximately optimal, quantum strategies for $\mathrm{XOR}^{*}$ and $\mathrm{FFL}$ games

• URL: http://arxiv.org/abs/2311.12887v3
• Date: Wed, 7 Aug 2024 12:52:41 GMT
• Title: Optimal, and approximately optimal, quantum strategies for $\mathrm{XOR}^{*}$ and $\mathrm{FFL}$ games
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We analyze optimal, and approximately optimal, quantum strategies for a variety of non-local XOR games. Building upon previous arguments due to Ostrev in 2016, which characterized approximately optimal, and optimal, strategies that players Alice and Bob can adopt for maximizing a linear functional to win non-local games after a Referee party examines each answer to a question drawn from some probability distribution, we identify additional applications of the framework for analyzing the performance of a broader class of quantum strategies in which it is possible for Alice and Bob to realize quantum advantage if the two players adopt strategies relying upon quantum entanglement, two-dimensional resource systems, and reversible transformations. For the Fortnow-Feige-Lovasz (FFL) game, the 2016 framework is directly applicable, which consists of five steps, including: (1) constructing a suitable, nonzero, linear transformation for the intertwining operations, (2) demonstrating that the operator has unit Frobenius norm, (3) constructing error bounds, and corresponding approximate operations, for $\big( A_k \otimes \textbf{I} \big) \ket{\psi}$, and $\big( \textbf{I} \otimes \big( \frac{\pm B_{kl} + B_{lk}}{\sqrt{2}} \big) \big) \ket{\psi}$, (4) constructing additional bounds for permuting the order in which $A^{j_i}_i$ operators are applied, (5) obtaining Frobenius norm upper bounds for Alice and Bob's strategies. We draw the attention of the reader to applications of this framework in other games with less regular structure.

Related papers

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• GPU-accelerated semidefinite programming for causal games [0.12891210250935145]
  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.
  arXiv  Detail & Related papers  (2026-06-18T17:36:34Z)
• Generalized Distributional Alignment Games for Unbiased Answer-Level Fine-Tuning [49.24876001249647]
  Distributional Alignment Game framework provides powerful variational perspective on Answer-Level Fine-Tuning (ALFT)<n>Standard algorithms for these games rely on estimating logarithmic rewards from small batches, introducing a systematic bias due to Jensen's inequality that can destabilize training.<n>We generalize the alignment game to arbitrary Bregman divergences, showing that for a family of geometries inducing rewards, we can construct provably exact and unbiased estimators.
  arXiv  Detail & Related papers  (2026-05-04T10:34:42Z)
• The perturbative method for quantum correlations [0.6187780920448871]
  The set $mathcalQ$ of quantum correlations is the collection of all possible probability distributions on measurement outcomes achievable by space-like separated parties sharing a quantum state.<n>We introduce a perturbative method using Lie-theoretic tools for the unitary group to analyze the response of the evaluations of Bell functional perturbations under infinitesimal unitarys of quantum strategies.
  arXiv  Detail & Related papers  (2026-03-27T18:00:08Z)
• Towards Exponential Quantum Improvements in Solving Cardinality-Constrained Binary Optimization [6.264051440120738]
  We introduce a Grover-based quantum algorithm that exploits the structure of the fixed-cardinality feasible subspace under a natural promise on solution existence.<n>For quadratic objectives, our approach achieves $Oleft(sqrtbinomnkfracn6k3/2 sqrtM2 right)$ queries to a quadratic oracle, together with $Oleft(fracn6k3/22right)$ classical overhead.
  arXiv  Detail & Related papers  (2026-03-16T02:30:52Z)
• An Information-Minimal Geometry for Qubit-Efficient Optimization [0.0]
  We recast qubit-efficient optimization as a geometry problem.<n>Local-consistency problem coincides exactly with the Sherali-Adams level-2 polytope $mathrmSA(2)$.
  arXiv  Detail & Related papers  (2025-11-11T15:38:57Z)
• 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)
• Quantum strategies, error bounds, optimality, and duality gaps for multiplayer XOR, $\mathrm{XOR}^{*}$, compiled XOR, $\mathrm{XOR}^{*}$, and strong parallel repetiton of XOR, $\mathrm{XOR}^{*}$, and FFL games [0.0]
  We characterize exact, and approximate, optimality of games that players can interact with using quantum strategies.<n>We conclude this effort by describing other variants of other possible strategies, as proposed sources for quantum advantage.
  arXiv  Detail & Related papers  (2025-05-09T03:47:41Z)
• Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
  This paper considers the problem for finding the $(,epsilon)$-Goldstein stationary point of Lipschitz continuous objective. We construct a zeroth-order quantum estimator for the surrogate oracle function.
  arXiv  Detail & Related papers  (2024-10-21T16:52:26Z)
• A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization [3.3493770627144004]
  We experimentally test how existing quantum processing units (QPUs) perform as subsolvers within a multilevel strategy. We find approximate solutions to $10$ instances of fully connected $82$-qubit Sherrington-Kirkpatrick graphs. We observe that quantum optimization results are competitive regarding the quality of solutions compared to classicals.
  arXiv  Detail & Related papers  (2024-08-14T20:06:32Z)
• Memory-Efficient Gradient Unrolling for Large-Scale Bi-level Optimization [71.35604981129838]
  Traditional gradient-based bi-level optimization algorithms are ill-suited to meet the demands of large-scale applications. We introduce $(textFG)2textU$, which achieves an unbiased approximation of the meta gradient for bi-level optimization. $(textFG)2textU$ is inherently designed to support parallel computing, enabling it to effectively leverage large-scale distributed computing systems.
  arXiv  Detail & Related papers  (2024-06-20T08:21:52Z)
• A quantum-classical performance separation in nonconvex optimization [7.427989325451079]
  We prove that the recently proposed Quantum Hamiltonian (QHD) algorithm is able to solve any $d$dimensional queries from this family. On the other side, a comprehensive empirical study suggests that representative state-of-the-art classical algorithms/solvers would require a superpolynomial time to solve such queries.
  arXiv  Detail & Related papers  (2023-11-01T19:51:00Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• Representation Learning for General-sum Low-rank Markov Games [63.119870889883224]
  We study multi-agent general-sum Markov games with nonlinear function approximation. We focus on low-rank Markov games whose transition matrix admits a hidden low-rank structure on top of an unknown non-linear representation.
  arXiv  Detail & Related papers  (2022-10-30T22:58:22Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  We propose and analyze new fictitious play policy optimization algorithms for zero-sum Markov games with structured but unknown transitions. We prove tight $widetildemathcalO(sqrtK)$ regret bounds after $K$ episodes in a two-agent competitive game scenario. Our algorithms feature a combination of Upper Confidence Bound (UCB)-type optimism and fictitious play under the scope of simultaneous policy optimization.
  arXiv  Detail & Related papers  (2022-07-25T18:29:16Z)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  We show that regret can be obtained for general convex and compact strategy sets. Our dynamics are on an instantiation of optimistic follow-the-regularized-bounds over an appropriately emphlifted space. Even in those special cases where prior results apply, our algorithm improves over the state-of-the-art regret.
  arXiv  Detail & Related papers  (2022-06-17T12:58:58Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• On the relation between completely bounded and $(1,cb)$-summing maps with applications to quantum XOR games [65.51757376525798]
  We show that given a linear map from a general operator space into the dual of a C$*$-algebra, its completely bounded norm is upper bounded by a universal constant times its $(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  arXiv  Detail & Related papers  (2021-12-09T21:06:52Z)
• Quantum Magic Rectangles: Characterization and Application to Certified Randomness Expansion [0.0]
  We study a generalization of the Mermin-Peres magic square game to arbitrary rectangular dimensions. We find that for $m times n$ rectangular games of dimensions $m,n geq 3$ there are quantum strategies that win with certainty. For dimensions $1 times n$ quantum strategies do not outperform classical strategies.
  arXiv  Detail & Related papers  (2020-08-05T21:19:34Z)

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.