Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs

• URL: http://arxiv.org/abs/2504.11120v1
• Date: Tue, 15 Apr 2025 12:08:07 GMT
• Title: Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs
• Abstract summary: The Quantum Max-Cut (QMC) problem is to determine the largest eigenvalue of a particular $2n times 2n$ matrix.<n>We provide a sharpened analysis of the currently best-known QMC approximation algorithm for general graphs.<n>We propose two new approximation algorithms for the QMC problem on triangle-free and bipartite graphs.
• Score: 0.9374652839580183
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study polynomial-time approximation algorithms for the Quantum Max-Cut (QMC) problem. Given an edge-weighted graph $G$ on n vertices, the QMC problem is to determine the largest eigenvalue of a particular $2^n \times 2^n$ matrix that corresponds to $G$. We provide a sharpened analysis of the currently best-known QMC approximation algorithm for general graphs. This algorithm achieves an approximation ratio of $0.599$, which our analysis improves to $0.603$. Additionally, we propose two new approximation algorithms for the QMC problem on triangle-free and bipartite graphs, that achieve approximation ratios of $0.61383$ and $0.8162$, respectively. These are the best-known approximation ratios for their respective graph classes.

Related papers

• Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut [4.812727079006245]
  We prove that the maximum eigenvalue of the Laplacian of level $k$ Kikuchi graph of any graph $G$ with $m$ edges is at most $m+k$.<n>We also make modest progress on Brouwer's conjecture and improve Lew's bound on the sum of the top-$k$ eigenvalues of a Graph Laplacian.
  arXiv  Detail & Related papers  (2026-05-14T15:56:29Z)
• Quantum Max Cut for complete tripartite graphs [0.0]
  The Quantum Max-$d$-Cut ($d$-QMC) problem is a special instance of a $2$-local Hamiltonian problem.<n>This article solves the $d$-QMC problem for complete tripartite graphs for small local dimensions, $d le 3$.
  arXiv  Detail & Related papers  (2025-12-03T12:37:48Z)
• Comparison of Hyperplane Rounding for Max-Cut and Quantum Approximate Optimization Algorithm over Certain Regular Graph Families [0.9699101045941679]
  Goemans-Williamson algorithm for approximating the Max-Cut achieves at most a 0.912-approximation.<n>We explore construction of challenging instances computationally by perturbing edge weights, which may be of independent interest.
  arXiv  Detail & Related papers  (2025-09-28T23:00:28Z)
• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  We solve the $k$-sparse parity problem with sign gradient descent (SGD) on two-layer fully-connected neural networks.<n>We show that this approach can efficiently solve the $k$-sparse parity problem on a $d$-dimensional hypercube.<n>We then demonstrate how a trained neural network with sign SGD can effectively approximate this good network, solving the $k$-parity problem with small statistical errors.
  arXiv  Detail & Related papers  (2024-04-18T17:57:53Z)
• Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms [1.2622634782102324]
  We develop an algorithm that decomposes the QAOA input problem graph into a smaller problem and solves MaxCut using QAOA on the reduced graph. We are able to measure optimal solutions for ten 100-vertex graphs by running single-layer QAOA circuits on the Quantinuum trapped-ion quantum computer H1-1.
  arXiv  Detail & Related papers  (2023-06-01T09:44:17Z)
• Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
  We give a statistical characterization of the $gamma$-regret for arbitrary structured bandit problems. The $gamma$-regret emerges in structured bandit problems over a function class $mathcalF$ where finding an exact optimum of $f in mathcalF$ is intractable.
  arXiv  Detail & Related papers  (2023-03-06T17:54:33Z)
• A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs [1.0435741631709405]
  An $soperatorname-t$ minimum cut in a graph corresponds to a minimum weight subset of edges whose removal disconnects $s$ and $t$. In this work we describe a quantum algorithm for the minimum $soperatorname-t$ cut problem on undirected graphs.
  arXiv  Detail & Related papers  (2021-10-29T07:35:46Z)
• An explicit vector algorithm for high-girth MaxCut [0.0]
  For every $d geq 3$ and $k geq 4$, our approximation guarantees are better than those of all other classical and quantum algorithms known to the authors.
  arXiv  Detail & Related papers  (2021-08-27T19:47:56Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees.
  arXiv  Detail & Related papers  (2021-06-16T03:34:14Z)
• 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)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  We show that a modified greedy algorithm can achieve an approximation factor of $0.305$. We derive a data-dependent upper bound on the optimum. It can also be used to significantly improve the efficiency of such algorithms as branch and bound.
  arXiv  Detail & Related papers  (2020-08-12T15:40:21Z)
• Consistent Structured Prediction with Max-Min Margin Markov Networks [84.60515484036239]
  Max-margin methods for binary classification have been extended to the structured prediction setting under the name of max-margin Markov networks ($M3N$) We overcome such limitations by defining the learning problem in terms of a "max-min" margin formulation, naming the resulting method max-min margin Markov networks ($M4N$) Experiments on multi-class classification, ordinal regression, sequence prediction and ranking demonstrate the effectiveness of the proposed method.
  arXiv  Detail & Related papers  (2020-07-02T10:48:42Z)
• 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)

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.