Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy

• URL: http://arxiv.org/abs/2110.04651v2
• Date: Tue, 12 Oct 2021 02:28:26 GMT
• Title: Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy
• Authors: Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen
• Abstract summary: 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.
• Score: 0.12891210250935145
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the connection between the complexity of nonlocal games and the arithmetical hierarchy, a classification of languages according to the complexity of arithmetical formulas defining them. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that deciding whether the (finite-dimensional) quantum value of a nonlocal game is $1$ or at most $\frac{1}{2}$ is complete for the class $\Sigma_1$ (i.e., $\mathsf{RE}$). A result of Slofstra implies that deciding whether the commuting operator value of a nonlocal game is equal to $1$ is complete for the class $\Pi_1$ (i.e., $\mathsf{coRE}$). We prove that deciding whether the quantum value of a two-player nonlocal game is exactly equal to $1$ is complete for $\Pi_2$; this class is in the second level of the arithmetical hierarchy and corresponds to formulas of the form "$\forall x \, \exists y \, \phi(x,y)$". This shows that exactly computing the quantum value is strictly harder than approximating it, and also strictly harder than computing the commuting operator value (either exactly or approximately). We explain how results about the complexity of nonlocal games all follow in a unified manner from a technique known as compression. At the core of our $\Pi_2$-completeness result is a new "gapless" compression theorem that holds for both quantum and commuting operator strategies. Our compression theorem yields as a byproduct an alternative proof of Slofstra's result that the set of quantum correlations is not closed. We also show how a "gap-preserving" compression theorem for commuting operator strategies would imply that approximating the commuting operator value is complete for $\Pi_1$.

Related papers

• The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
  Smooth boosters generate distributions that do not place too much weight on any given example. Originally introduced for their noise-tolerant properties, such boosters have also found applications in differential privacy, mildly, and quantum learning theory.
  arXiv  Detail & Related papers  (2024-09-17T23:09:25Z)
• Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$ [0.0]
  We study the complexity of a classic problem in computational topology, the homology problem. We find that the complexity is characterized by quantum complexity classes. Our results can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics.
  arXiv  Detail & Related papers  (2023-11-28T21:15:30Z)
• 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)
• Nonlocality under Computational Assumptions [51.020610614131186]
  A set of correlations is said to be nonlocal if it cannot be reproduced by spacelike-separated parties sharing randomness and performing local operations. We show that there exist (efficient) local producing measurements that cannot be reproduced through randomness and quantum-time computation.
  arXiv  Detail & Related papers  (2023-03-03T16:53:30Z)
• Quantum free games [2.298932494750101]
  We show a BellQMA(2) protocol for 3SAT on $n$ variables, where the total amount of communication is $tildeO(sqrtn)
  arXiv  Detail & Related papers  (2023-02-08T20:32:24Z)
• 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)
• 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)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• On the complexity of zero gap MIP* [0.11470070927586014]
  We show that the class $mathsfMIP*$ is equal to $mathsfRE$. In particular this shows that the complexity of approximating the quantum value of a non-local game $G$ is equivalent to the complexity of the Halting problem.
  arXiv  Detail & Related papers  (2020-02-24T19:11:01Z)
• 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.