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

2025/04/15 by Sander Gribling, Gribling, Sander, Lennart Sinjorgo +3 · 3 citations
Computer Science · Mathematics · #Quantum Computing Algorithms and Architecture #Complexity and Algorithms in Graphs #Markov Chains and Monte Carlo Methods

paper · pdf · doi:10.48550/arxiv.2504.11120

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ⁿ × 2ⁿ 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.

Cited by

• Lovász theta and Shearer lower bounds on Quantum Max Cut
• A 0.8395-approximation algorithm for the EPR problem
• Testing APS conjecture on regular graphs

Related

• Quantum Max-Cut is NP hard to approximate
• Quantum Speedup for the Maximum Cut Problem
• Improved Combinatorial Approximation Algorithms for MAX CUT in Sparse Graphs
• Quantum Max Cut for complete tripartite graphs
• Quantum Approximate Optimization Algorithms for Maximum Cut on Low-Girth Graphs