Sphere Valued Noise Stability and Quantum MAX-CUT Hardness

• URL: http://arxiv.org/abs/2306.03912v2
• Date: Thu, 31 Aug 2023 22:31:28 GMT
• Title: Sphere Valued Noise Stability and Quantum MAX-CUT Hardness
• Abstract summary: This inequality was conjectured (for all correlation parameters at most $1$ in absolute value) by Hwang, Neeman, Parekh, Thompson and Wright. We show that the product state of Quantum MAX-CUT is NP-hard to approximate within a multiplicative factor $.9859$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove a vector-valued inequality for the Gaussian noise stability (i.e. we prove a vector-valued Borell inequality) for Euclidean functions taking values in the two-dimensional sphere, for all correlation parameters at most $1/10$ in absolute value. This inequality was conjectured (for all correlation parameters at most $1$ in absolute value) by Hwang, Neeman, Parekh, Thompson and Wright. Such an inequality is needed to prove sharp computational hardness of the product state Quantum MAX-CUT problem, assuming the Unique Games Conjecture. In fact, assuming the Unique Games Conjecture, we show that the product state of Quantum MAX-CUT is NP-hard to approximate within a multiplicative factor of $.9859$. In contrast, a polynomial time algorithm is known with approximation factor $.956\ldots$.

Related papers

• Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT [2.538209532048867]
  We show it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of $_3+$ for every $>0$.<n>With a similar strategy we prove it is NP-hard to approximate the product-state value of Quantum-CUT within a multiplicative factor of $_rm BOV+$ for every $>0$.
  arXiv  Detail & Related papers  (2026-07-31T22:53:00Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
  We study a new class of MDPs that employs multinomial logit (MNL) function approximation to ensure valid probability distributions over the state space. Despite its significant benefits, incorporating the non-linear function raises substantial challenges in both statistical and computational efficiency. We propose an algorithm that achieves a regret of $widetildemathcalO(dH2sqrtK + kappa-1d2H2)$, eliminating the dependence on $kappa-1$ in the dominant term for the first time
  arXiv  Detail & Related papers  (2024-05-27T11:31:54Z)
• The classical limit of Quantum Max-Cut [0.18416014644193066]
  We show that the limit of large quantum spin $S$ should be understood as a semiclassical limit. We present two families of classical approximation algorithms for $mathrmQMaxCut_S$ based on rounding the output of a semidefinite program to a product of Bloch coherent states.
  arXiv  Detail & Related papers  (2024-01-23T18:53:34Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Tip of the Quantum Entropy Cone [1.1606619391009658]
  Relations among von Neumann entropies of different parts of an $N$-partite quantum system have direct impact on our understanding of diverse situations. We show that while it is always possible to up-scale an entropy vector to arbitrary integer multiples it is not always possible to down-scale it to arbitrarily small size.
  arXiv  Detail & Related papers  (2023-05-31T21:37:24Z)
• A generic quantum Wielandt's inequality [0.9975341265604578]
  It is conjectured that $k$ should be of order $mathcalO(n2)$ in general. We provide a generic version of quantum Wielandt's inequality, which gives the optimal length with probability one. We shed new light on a long-standing open problem for Projected Entangled Pair State.
  arXiv  Detail & Related papers  (2023-01-19T18:57:32Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points [50.90125395570797]
  This nearly establishes a conjecture ofciteSaundersonCPW12, within logarithmic factors. The latter conjecture has attracted significant attention over the past decade, due to its connections to machine learning and sum-of-squares lower bounds for certain statistical problems.
  arXiv  Detail & Related papers  (2022-12-21T17:48:01Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• 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)
• 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)
• Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
  We give a semidefinite program of size $exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big)) to compute additive $epsilon$-approximations on the values of two-player free games. We make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints.
  arXiv  Detail & Related papers  (2020-05-18T16:55:08Z)

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.