MAXCUT QAOA performance guarantees for p >1

• URL: http://arxiv.org/abs/2010.11209v2
• Date: Tue, 2 Feb 2021 21:25:07 GMT
• Title: MAXCUT QAOA performance guarantees for p >1
• Abstract summary: We obtain worst case performance guarantees for $p=2$ and $3$ QAOA for MAXCUT on uniform 3-regular graphs. We conjecture a hierarchy for all $p$, where worst case graphs have with no cycles $leq 2p+1$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We obtain worst case performance guarantees for $p=2$ and $3$ QAOA for MAXCUT on uniform 3-regular graphs. Previous work by Farhi et al obtained a lower bound on the approximation ratio of $0.692$ for $p=1$. We find a lower bound of $0.7559$ for $p=2$, where worst case graphs are those with no cycles $\leq 5$. This bound holds for any 3 regular graph evaluated at particular fixed parameters. We conjecture a hierarchy for all $p$, where worst case graphs have with no cycles $\leq 2p+1$. Under this conjecture, the approximation ratio is at least $0.7924$ for all 3 regular graphs and $p=3$. In addition, using a simple indistinguishability argument we find an upper bound on the worst case approximation ratio for all $p$, which indicates classes of graphs for which there can be no quantum advantage for at least $p<6$.

Related papers

• Exponential random graph models with soft clique constraints [0.0]
  We consider an exponential random graph model which gives higher probability to $G in mathbfG_n than to $H in mathbfG_n$ if $G$ has fewer $r$-cliques than $H$.<n>The degree to which graphs with fewer $r$-cliques are given higher probability is determined by a positive weight $w$.
  arXiv  Detail & Related papers  (2026-08-31T14:31:57Z)
• Correlation Clustering with Random Partial Information [4.706621352211144]
  Correlation clustering is a fundamental unsupervised learning problem.<n>We study a natural class of graphs obtained by randomly subsampling a complete signed graph $G$.<n>We prove approximation guarantees that are substantially better than the bounds achievable for general graphs.
  arXiv  Detail & Related papers  (2026-08-17T09:22:22Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  We study horizon-free regret for finite-horizon time-homogeneous Markov decision processes with $A$ states, $A$ actions, horizon $H$, and per-trajectory total reward bounded by $1$.<n>We prove a regret upper bound [tilde O(sqrtSAK+S8A3)] with failure probability $$, where $K$ is the number of episodes and $tilde O(sqrtSAK+S3K)$ hides $mathsfpoly
  arXiv  Detail & Related papers  (2026-07-22T07:42:19Z)
• Approximate quantum 3-colorings of graphs and the quantum Max 3-Cut problem [0.0]
  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.
  arXiv  Detail & Related papers  (2024-12-27T02:05:37Z)
• Extremal Maximal Entanglement [12.189398760348018]
  An $n$-qubit absolutely maximally entangled state only exists when $n$ equals $2$, $3$, $5$, and $6$. A natural question arises when it does not exist: which $n-qubit pure state has the largest number of maximally mixed $lfloor n/2 rfloor-party reductions?
  arXiv  Detail & Related papers  (2024-11-19T03:56:34Z)
• Complexity of graph-state preparation by Clifford circuits [2.4032529562561176]
  We consider general quantum algorithms acting on at most two qubits for graph-state preparations. We show a connection between the CZ-complexity of graph state $|Grangle$ and the rank-width of the graph $G$. We present quantum algorithms for preparing graph states for three specific graph classes related to intervals: interval graphs, interval containment graphs, and circle graphs.
  arXiv  Detail & Related papers  (2024-02-08T18:08:09Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  We provide analytic evidence that on large graphs, d-separation is a rare phenomenon, even when guaranteed to exist. For the PC Algorithm, while it is known that its worst-case guarantees fail on non-sparse graphs, we show that the same is true for the average case. For UniformSGS, while it is known that the running time is exponential for existing edges, we show that in the average case, that is the expected running time for most non-existing edges as well.
  arXiv  Detail & Related papers  (2023-03-10T00:11:18Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  We study high-probability regret bounds for adversarial $K$-armed bandits with time-varying feedback graphs over $T$ rounds. We develop an algorithm that achieves the optimal regret $widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$ with high probability. We also develop the first algorithm that achieves the optimal high-probability regret bound for weakly observable graphs.
  arXiv  Detail & Related papers  (2022-10-04T04:36:15Z)
• Repeated Averages on Graphs [2.363388546004777]
  We prove that $frac(1-epsilon)2log2nlog n-O(n)$ is a general lower bound for all connected graphs on $n$ nodes. We also get sharp magnitude of $t_epsilon,1$ for several important families of graphs, including star, expander, dumbbell, and cycle.
  arXiv  Detail & Related papers  (2022-05-09T20:18:31Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• 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)
• The fixed angle conjecture for QAOA on regular MaxCut graphs [0.0]
  We provide numerical evidence for a fixed angle conjecture for $p12$. These fixed angles serve for an optimization-free version of QAOA, and have universally good performance on any 3 regular graph. Heuristic evidence is presented for the fixed angle conjecture on graph ensembles, which suggests that these fixed angles are close" to global optimum.
  arXiv  Detail & Related papers  (2021-07-01T18:02:36Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$ We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
  arXiv  Detail & Related papers  (2021-03-02T06:53:44Z)
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs [0.0]
  We show that for all degrees $D ge 2$ of girth $> 5$, QAOA$ has a larger expected cut fraction than QAOA$$ on $G$. We conjecture that for every constant $p$, there exists a local classical MAX-CUT algorithm that performs as well as QAOA$_p$ on all graphs.
  arXiv  Detail & Related papers  (2021-01-14T09:17:20Z)
• 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.