Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut

• URL: http://arxiv.org/abs/2605.14994v1
• Date: Thu, 14 May 2026 15:56:29 GMT
• Title: Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
• Abstract summary: 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.
• Score: 4.812727079006245
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level $k$ Kikuchi graph of any graph $G$ with $m$ edges is at most $m+k$. This confirms four recent conjectures of Apte, Parekh, and Sud. As applications, we obtain that tensor products of one and two qubit product states achieve an approximation ratio of $5/8$ for Quantum Max Cut and $5/7$ for the XY Hamiltonian. Moreover, combining our bounds with the algorithms analyzed by Apte, Parekh, and Sud, yields efficient algorithms achieving an approximation ratio of $0.614$ for Quantum Max Cut and $0.674$ for the XY Hamiltonian. Finally, 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.

Related papers

• An Argmax Principle for Sum-of-Squares Relaxations on the Sphere [42.540924632302925]
  We develop an argmax principle for analyzing sum-of-squares relaxations of optimization problems over the unit sphere.<n>Our guiding principle is that its maximizers are rounding candidates.
  arXiv  Detail & Related papers  (2026-08-03T17:58:00Z)
• The Kikuchi Hierarchy is Sharp for $k$XOR [46.26532142699448]
  We show that a normalized variant of the Kikuchi hierarchy achieves the sharp conjectured trade-off, with no logarithmic loss, at every arity $kge3$.<n>We also prove matching lower bounds in the same model. The inference and refutation upper bounds transfer to more general planting laws and predicates.
  arXiv  Detail & Related papers  (2026-07-31T17:54:11Z)
• 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)
• 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)
• A Lovász theta lower bound on Quantum Max Cut [2.0305676256390934]
  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.
  arXiv  Detail & Related papers  (2025-12-23T12:53:40Z)
• Quantum Max-Cut is NP hard to approximate [0.06768558752130309]
  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.
  arXiv  Detail & Related papers  (2025-10-09T09:32:08Z)
• Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs [0.9374652839580183]
  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.
  arXiv  Detail & Related papers  (2025-04-15T12:08:07Z)
• Improved approximation algorithms for the EPR Hamiltonian [0.0]
  The EPR Hamiltonian is a family of 2-local quantum Hamiltonians introduced by King (arXiv:2202589)<n>We introduce a time $frac1+sqrt54$-approximation algorithm for the problem of computing the ground energy of the EPR Hamiltonian.
  arXiv  Detail & Related papers  (2025-04-14T21:08:40Z)
• Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians [37.96754147111215]
  We prove new monogamy of entanglement bounds for two-local qudit Hamiltonians of rank-one projectors without one-local terms.<n>In particular, we certify the ground state energy in terms of the maximum matching of the underlying interaction graph via low-degree sum-of-squares.
  arXiv  Detail & Related papers  (2024-10-21T00:10:51Z)
• 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)
• Delving Into Deep Walkers: A Convergence Analysis of Random-Walk-Based Vertex Embeddings [0.7366405857677227]
  We provide a theoretical analysis for random-walks based embeddings techniques. We prove that, under some weak assumptions, corpora converge both in the single limit of the number of random walks $N to infty$ and in the double limit of both $N$ and the length of each random walk $Ltoinfty$.
  arXiv  Detail & Related papers  (2021-07-21T11:23:04Z)
• 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)

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.