Hybrid Rydberg atom plus SDP algorithm achieves 0.651-approximation for quantum Max Cut, improving on the prior 0.614 SDP-only bound and remaining effective at 89% ground-state fidelity.
Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
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.
years
2026 3verdicts
UNVERDICTED 3representative citing papers
Proves Brouwer's Laplacian conjecture and establishes its equivalence to the Grone-Merris-Bai theorem for split graphs.
Level-ℓ Kikuchi graphs of random 2r-uniform hypergraphs spectrally approximate those of the complete hypergraph at near-optimal sampling rates for r ≤ ℓ ≤ n/2.
citing papers explorer
-
A 0.651-approximation to quantum Max Cut via Rydberg atoms
Hybrid Rydberg atom plus SDP algorithm achieves 0.651-approximation for quantum Max Cut, improving on the prior 0.614 SDP-only bound and remaining effective at 89% ground-state fidelity.
-
On Brouwer's Laplacian conjecture
Proves Brouwer's Laplacian conjecture and establishes its equivalence to the Grone-Merris-Bai theorem for split graphs.
-
Kikuchi Graphs of Random Hypergraphs are Approximately Johnson
Level-ℓ Kikuchi graphs of random 2r-uniform hypergraphs spectrally approximate those of the complete hypergraph at near-optimal sampling rates for r ≤ ℓ ≤ n/2.