Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions

• URL: http://arxiv.org/abs/2408.10114v5
• Date: Mon, 30 Sep 2024 08:55:30 GMT
• Title: Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions
• Authors: Entong He,
• Abstract summary: We prove the equivalence between the hereditary and $C*$ models questioned in (Helton et al., New York J. Math.) We also extend the quantum-version NP-hardness reduction $texttt3-SAT* leq_p textttClique*$ by exhibiting another instance of such reduction.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We review the correspondence between synchronous games and their associated $*$-algebra. Building upon the work of (Helton et al., New York J. Math. 2017), we propose results on algebraic and locally commuting graph identities. Based on the noncommutative Nullstellens\"atze (Watts, Helton and Klep, Annales Henri Poincar\'e 2023), we build computational tools that check the non-existence of perfect $C^*$ and algebraic strategies of synchronous games using Gr\"obner basis methods and semidefinite programming. We prove the equivalence between the hereditary and $C^*$ models questioned in (Helton et al., New York J. Math. 2017). We also extend the quantum-version NP-hardness reduction $\texttt{3-SAT}^* \leq_p \texttt{3-Coloring}^*$ due to (Ji, arXiv 2013) by exhibiting another instance of such reduction $\texttt{3-SAT}^* \leq_p \texttt{Clique}^*$.

Related papers

• Parity vs. AC0 with simple quantum preprocessing [0.0]
  We study a hybrid circuit model where $mathsfAC0$ operates on measurement outcomes of a $mathsfQNC0$ circuit. We find that while $mathsfQNC0$ is surprisingly powerful for search and sampling tasks, that power is "locked away" in the global correlations of its output.
  arXiv  Detail & Related papers  (2023-11-22T20:27:05Z)
• Universality of graph homomorphism games and the quantum coloring problem [0.0]
  We show that quantum graph parameters encode winning strategies for all possible synchronous non-local games. Winning strategies for a synchronous game can be transformed into winning strategies for an associated graph coloring game.
  arXiv  Detail & Related papers  (2023-05-29T14:28:28Z)
• 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)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  We present the first line of algorithms that require only $widetildemathcalO((XA+YB)/varepsilon2)$ episodes of play to find an $varepsilon$-approximate Nash equilibrium in two-player zero-sum games. This improves upon the best known sample complexity of $widetildemathcalO((X2A+Y2B)/varepsilon2)$ by a factor of $widetildemathcalO(maxX,
  arXiv  Detail & Related papers  (2022-02-03T18:18:28Z)
• Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
  The observables associated with a quantum system $S$ form a non-commutative algebra $mathcal A_S$. It is assumed that a density matrix $rho$ can be determined from the expectation values of observables. Abelian algebras do not have inner automorphisms, so the measurement apparatus can determine mean values of observables.
  arXiv  Detail & Related papers  (2021-12-14T16:29:53Z)
• Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy [0.12891210250935145]
  We investigate the connection between the complexity of nonlocal games and the arithmetical hierarchy. We show that exactly computing the quantum value is strictly harder than approximating it, and also strictly harder than computing the commuting operator value.
  arXiv  Detail & Related papers  (2021-10-09T21:53:02Z)
• Synchronous games with $*$-isomorphic game algebras [0.0]
  We show that the game algebra of any synchronous game on $n$ inputs and $k$ outputs is $*$-isomorphic to the game algebra of an associated bisynchronous game on $nk$ inputs and $nk$ outputs. We also exhibit a $*$-isomorphism between any synchronous game algebra with $n$ questions and $k>3$ answers and a synchronous game algebra with $n(k-2)$ questions and $3$ answers.
  arXiv  Detail & Related papers  (2021-09-10T13:19:14Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  We focus on self-play algorithms which learn the optimal policy by playing against itself without any direct supervision. We propose an optimistic variant of the emphNash Q-learning algorithm with sample complexity $tildemathcalO(SAB)$, and a new emphNash V-learning algorithm with sample complexity $tildemathcalO(S(A+B))$.
  arXiv  Detail & Related papers  (2020-06-22T05:00:13Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)
• MIP*=RE [9.42581332803306]
  We show that the class MIP* of languages can be decided by a classical verifier interacting with multiple quantum provers sharing entanglement. We provide a refutation of Connes' theory of von Neumann algebras.
  arXiv  Detail & Related papers  (2020-01-13T16:32:40Z)

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.