Quantum Max-Cut is NP hard to approximate

• URL: http://arxiv.org/abs/2510.07995v1
• Date: Thu, 09 Oct 2025 09:32:08 GMT
• Title: Quantum Max-Cut is NP hard to approximate
• Abstract summary: We prove that it is NP-hard to compute a constant multiplicative approximation to the QUANTUM MAX-CUT problem on an unweighted graph of constant bounded degree.
• Score: 0.06768558752130309
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We unconditionally prove that it is NP-hard to compute a constant multiplicative approximation to the QUANTUM MAX-CUT problem on an unweighted graph of constant bounded degree. The proof works in two stages: first we demonstrate a generic reduction to computing the optimal value of a quantum problem, from the optimal value over product states. Then we prove an approximation preserving reduction from MAX-CUT to PRODUCT-QMC the product state version of QUANTUM MAX-CUT. More precisely, in the second part, we construct a PTAS reduction from MAX-CUT$_k$ (the rank-k constrained version of MAX-CUT) to MAX-CUT$_{k+1}$, where MAX-CUT and PRODUCT-QMC coincide with MAX-CUT$_1$ and MAX-CUT$_3$ respectively. We thus prove that Max-Cut$_k$ is APX-complete for all constant $k$.

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)
• The Complexity of Min-Max Optimization for Quadratic Polynomials [71.85811744604827]
  We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratics.<n>As a direct consequence, we obtain the first PPAD-hardness results for two-team zero-sum polymatrix.
  arXiv  Detail & Related papers  (2026-06-15T17:37:13Z)
• 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)
• 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)
• Softmax is $1/2$-Lipschitz: A tight bound across all $\ell_p$ norms [5.600982367387832]
  We prove that the softmax function is contractive with the Lipschitz constant $1/2$.<n>To our knowledge, this is the first comprehensive norm-uniform analysis of softmax Lipschitz continuity.
  arXiv  Detail & Related papers  (2025-10-27T05:16:04Z)
• Reinforced Generation of Combinatorial Structures: Applications to Complexity Theory [3.359365297148466]
  We explore whether techniques from AI can help discover new structures that improve on known limits on efficient algorithms.<n>Specifically, we use AlphaEvolve to study two settings: a) Average-case hardness for MAX-CUT and MAX-Independent Set.<n>Our improved lower bounds are obtained by constructing nearly extremal Ramanujan graphs on as many as $163$ nodes.
  arXiv  Detail & Related papers  (2025-09-22T17:30:33Z)
• Self-Adjust Softmax [62.267367768385434]
  The softmax function is crucial in Transformer attention, which normalizes each row of the attention scores with summation to one.<n>We propose Self-Adjust Softmax (SA-Softmax) to address this issue by modifying $softmax(x)$ to $x cdot softmax(x)$ and its normalized variant $frac(x - min(x_min,0))max(0,x_max)-min(x_min,0) cdot softmax(x)$.
  arXiv  Detail & Related papers  (2025-02-25T15:07:40Z)
• Continuous K-Max Bandits [54.21533414838677]
  We study the $K$-Max multi-armed bandits problem with continuous outcome distributions and weak value-index feedback.<n>This setting captures critical applications in recommendation systems, distributed computing, server scheduling, etc.<n>Our key contribution is the computationally efficient algorithm DCK-UCB, which combines adaptive discretization with bias-corrected confidence bounds.
  arXiv  Detail & Related papers  (2025-02-19T06:37:37Z)
• A maximum concurrence criterion to investigate absolutely maximally entangled states [0.7373617024876725]
  We use the criterion of maximal I-concurrence, a measure of entanglement, to determine the maximal entanglement of pure states.<n>We identify numerous Absolutely Maximallyangled (AME) pure states that exhibit maximal entanglement across all possible bipartitions.
  arXiv  Detail & Related papers  (2025-01-26T10:46:03Z)
• On the (Classical and Quantum) Fine-Grained Complexity of Log-Approximate CVP and Max-Cut [2.2776283699063664]
  We show a linear sized reduction from the Maximum Cut Problem (Max-Cut) with $1 - varepsilon$ and soundness $1 - varepsilon1/2$ to the $gamma$-Approximate Closest Vector Problem under any finite $ell_p$-norm. We show that any sub-exponential time (classical or quantum) algorithm for the $o(sqrtlog nfrac1p)$-Approximate Closest Vector Problem in any finite $ell_p$-norm implies a faster than the state-
  arXiv  Detail & Related papers  (2024-11-06T18:58:17Z)
• Convex Bounds on the Softmax Function with Applications to Robustness Verification [69.09991317119679]
  The softmax function is a ubiquitous component at the output of neural networks and increasingly in intermediate layers as well. This paper provides convex lower bounds and concave upper bounds on the softmax function, which are compatible with convex optimization formulations for characterizing neural networks and other ML models.
  arXiv  Detail & Related papers  (2023-03-03T05:07:02Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Fast Incremental Expectation Maximization for finite-sum optimization: nonasymptotic convergence [0.0]
  This paper recasts Fast Incremental Expectation Maximization (FIEM) and other incremental EM type algorithms in the em Approximation within EM framework. We provide nonasymptotic bounds for the convergence in expectation as a function of the number of examples $n$ and of the maximal number of iterations $kmax$.
  arXiv  Detail & Related papers  (2020-12-29T09:11:42Z)
• 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)
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization [61.66927778694731]
  Epoch gradient descent method (a.k.a. Epoch-GD) proposed by Hazan and Kale (2011) was deemed a breakthrough for strongly convex minimization. Our result is the first one that shows Epoch-GDA can achieve the optimal rate of $O (1/T)$ for the duality gap of SCSC min-max problems.
  arXiv  Detail & Related papers  (2020-02-13T02:16:57Z)

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.