Approximate quantum 3-colorings of graphs and the quantum Max 3-Cut problem

• URL: http://arxiv.org/abs/2412.19405v1
• Date: Fri, 27 Dec 2024 02:05:37 GMT
• Title: Approximate quantum 3-colorings of graphs and the quantum Max 3-Cut problem
• Authors: Samuel J. Harris,
• Abstract summary: We prove that to each synchronous non-local game $mathcalG=(I,O,lambda)$ with $|I|=n$ and $O=m geq 3$, there is an associated graph $G_lambda$. We also prove that there exists an $alpha in (0,1)$ for which determining whether the non-commutative Max-$3$-Cut of a graph is $E|$ or less than $alpha |E|$ is RE-hard.
• Score: 0.0
• License:
• Abstract: We prove that, to each synchronous non-local game $\mathcal{G}=(I,O,\lambda)$ with $|I|=n$ and $|O|=m \geq 3$, there is an associated graph $G_{\lambda}$ for which approximate winning strategies for the game $\mathcal{G}$ and the $3$-coloring game for $G_{\lambda}$ are preserved. That is, using a similar graph to previous work of the author (Ann. Henri Poincar\'{e}, 2024), any synchronous strategy for $\text{Hom}(G_{\lambda},K_3)$ that wins the game with probability $1-\varepsilon$ with respect to the uniform probability distribution on the edges, yields a strategy in the same model that wins the game $\mathcal{G}$ with respect to the uniform distribution with probability at least $1-h(n,m)\varepsilon^{\frac{1}{2}}$, where $h$ is a polynomial in $n$ and $2^m$. As an application, we prove that the gapped promise problem for quantum $3$-coloring is undecidable. Moreover, we prove that there exists an $\alpha \in (0,1)$ for which determining whether the non-commutative Max-$3$-Cut of a graph is $|E|$ or less than $\alpha |E|$ is RE-hard, thus giving a positive answer to a problem posed by Culf, Mousavi and Spirig (arXiv:2312.16765), along with evidence for a sharp computability gap in the non-commutative Max-$3$-Cut problem. We also prove that there is some $\alpha \in (0,1)$ such that determining the non-commutative (respectively, commuting operator framework) versions of the Max-$3$-Cut of a graph within a factor of $\alpha$ is uncomputable. All of these results avoid use of the unique games conjecture.

Related papers

• Sharp Noisy Binary Search with Monotonic Probabilities [5.563988395126509]
  We revisit the noisy binary search model of Karp and Kleinberg. We produce an algorithm that succeeds with probability $1-delta$ from [ frac1C_tau, varepsilon cdot left(lg n + O(log2/3 n log 1/3 frac1delta + log frac1delta) right.
  arXiv  Detail & Related papers  (2023-11-01T20:45:13Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• 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)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
  arXiv  Detail & Related papers  (2023-04-17T10:38:08Z)
• Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
  We show how all properties of a quantum manifold of states are fully described by a gauge-invariant Bargmann. We show how our results have immediate applications to the modern theory of polarization.
  arXiv  Detail & Related papers  (2022-05-30T18:01:34Z)
• Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
  This paper studies the problem of matching two complete graphs with edge weights correlated through latent geometries. We derive an approximate maximum likelihood estimator, which provably achieves, with high probability, perfect recovery of $pi*$. As a side discovery, we show that the celebrated spectral algorithm of [Ume88] emerges as a further approximation to the maximum likelihood in the geometric model.
  arXiv  Detail & Related papers  (2022-02-22T04:14:45Z)
• Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality [6.621324975749854]
  We show that the noise stability of a function $f:mathbbRn to -1, 1$ is the expected value of $f(boldsymbolx) cdot f(boldsymboly)$. We conjecture that the expected value of $langle f(boldsymbolx), f(boldsymboly)rangle$ is minimized by the function $f(x) = x_leq k / Vert x_leq k /
  arXiv  Detail & Related papers  (2021-11-01T20:45:42Z)
• Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
  This paper deals with the problem of graph matching or network alignment for ErdHos--R'enyi graphs. It can be viewed as a noisy average-case version of the graph isomorphism problem.
  arXiv  Detail & Related papers  (2021-10-11T05:07:50Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets. Two types of structural assumptions lead to better pseudo-regret bounds.
  arXiv  Detail & Related papers  (2021-03-10T07:33:03Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  We study learning in contextual bandits with the help of loss predictors. We show that the optimal regret is $mathcalO(minsqrtT, sqrtmathcalETfrac13)$ when $mathcalE$ is known.
  arXiv  Detail & Related papers  (2020-03-04T07:36:38Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

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.