A Lovász theta lower bound on Quantum Max Cut

• URL: http://arxiv.org/abs/2512.20326v1
• Date: Tue, 23 Dec 2025 12:53:40 GMT
• Title: A Lovász theta lower bound on Quantum Max Cut
• Abstract summary: We prove a lower bound to quantum Max Cut of a graph in terms of the Lovsz theta function of its complement.<n>The bound outperforms the classical bound when applied to quantum Max Cut.
• Score: 2.0305676256390934
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove a lower bound to quantum Max Cut of a graph in terms of the Lovász theta function of its complement. For a graph with $m$ edges, $\text{qmc}(G) \geq \tfrac{m}{4}\big( 1 + \tfrac{8}{3π}\tfrac{1}{\vartheta(\bar{G}) -1} \big)$, with the bound achieved by a product state. The proof extends a result by Balla, Janzer, and Sudakov on classical Max Cut and is also inspired by the randomized rounding method of Gharibian and Parekh. The bound outperforms the classical bound when applied to quantum Max Cut.

Related papers

• Optimal Quantum de Finetti Theorems via Argmax Rounding [42.55259086694773]
  We prove optimal finite quantum de Finetti upper bounds for bosonic states and arbitrary exchangeable states.<n>Our proof formulates de Finetti approximation as the integrality gap of a symmetric-extension semidefinite program.<n> spectral truncation gives the first dimension-free bosonic de Finetti theorem in Hilbert--Schmidt distance.
  arXiv  Detail & Related papers  (2026-08-03T17:57:15Z)
• A Spectral Proof of the Hypergraph Moore Bound [46.26532142699448]
  We prove Feige's 2008 conjecture on the hypergraph Moore bound.<n>For every $kge3$ and every $1leellle n$, any $k$-uniform hypergraph on $n$ vertices with more than $C,nk/2/ellk/2-1$ hyperedges contains an even cover of size at most $A,elllog(en/ell)$.
  arXiv  Detail & Related papers  (2026-07-28T17:38:31Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• 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)
• Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA [0.027042267806481293]
  We study MaxCut on 3-regular graphs of minimum girth $g$ for various $g$'s.<n>For $g geq 16$, at depth $p geq 7$, the QAOA improves on previously known lower bounds.
  arXiv  Detail & Related papers  (2025-03-17T03:58:43Z)
• 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)
• Causal Bandits with General Causal Models and Interventions [38.112806687145344]
  This paper considers causal bandits (CBs) for the sequential design of interventions in a causal system. The objective is to optimize a reward function via minimizing a measure of cumulative regret with respect to the best sequence of interventions in hindsight.
  arXiv  Detail & Related papers  (2024-03-01T02:28:49Z)
• The classical limit of Quantum Max-Cut [0.16385815610837165]
  We show that the limit of large quantum spin $S$ should be understood as a semiclassical limit.<n>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)
• Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
  The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, $d$-dimensional qudits over all local interactions. We develop an algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees.
  arXiv  Detail & Related papers  (2023-09-19T22:53:17Z)
• Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
  We show that there are distributions on $[-1,1]$ that cannot be approximated to accuracy $epsilon$ in Wasserstein-1 distance. No algorithm can compute an $epsilon$-accurate approximation to the spectrum of a normalized graph adjacency matrix with constant probability.
  arXiv  Detail & Related papers  (2023-07-02T05:03:38Z)
• The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut [0.07614628596146598]
  We investigate the space complexity of two graph streaming problems: Max-Cut and its quantum analogue, Quantum Max-Cut. Our work resolves the quantum and classical approximability of quantum and classical Max-Cut using $textrmo(n)$ space.
  arXiv  Detail & Related papers  (2022-06-01T03:40:56Z)
• 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)
• 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)
• Quantum Max-Flow Min-Cut theorem [11.98034899127065]
  We establish a quantum max-flow min-cut theorem for a new definition of quantum maximum flow. Our result implies that the ratio of the quantum max-flow to the quantum min-cut converges to $1$ as the dimension $n$ tends to infinity.
  arXiv  Detail & Related papers  (2021-10-03T02:11:39Z)
• 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.