Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bakshi, Ainesh, Basu, Arpon, Kothari, Pravesh, Li, Anqi
Format:	Preprint
Published:	2026
Subjects:	Quantum Physics Data Structures and Algorithms Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
by: Kothari, Pravesh K., et al.
Published: (2025)

An Improved Classical Singular Value Transformation for Quantum Machine Learning
by: Bakshi, Ainesh, et al.
Published: (2023)

Comparison of Hyperplane Rounding for Max-Cut and Quantum Approximate Optimization Algorithm over Certain Regular Graph Families
by: Tate, Reuben, et al.
Published: (2025)

Rapid mixing for high-temperature Gibbs states with arbitrary external fields
by: Bakshi, Ainesh, et al.
Published: (2026)

Sparsifying Sums of Positive Semidefinite Matrices
by: Basu, Arpon, et al.
Published: (2025)

Efficient Certificates of Anti-Concentration Beyond Gaussians
by: Bakshi, Ainesh, et al.
Published: (2024)

A Dobrushin condition for quantum Markov chains: Rapid mixing and conditional mutual information at high temperature
by: Bakshi, Ainesh, et al.
Published: (2025)

Many Hamiltonians Are Sparsifiable
by: Basu, Arpon, et al.
Published: (2026)

High-Temperature Gibbs States are Unentangled and Efficiently Preparable
by: Bakshi, Ainesh, et al.
Published: (2024)

No Quantum Advantage in Decoded Quantum Interferometry for MaxCut
by: Parekh, Ojas
Published: (2025)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
by: Kothari, Pravesh, et al.
Published: (2024)

Structure learning of Hamiltonians from real-time evolution
by: Bakshi, Ainesh, et al.
Published: (2024)

Learning quantum Hamiltonians at any temperature in polynomial time
by: Bakshi, Ainesh, et al.
Published: (2023)

Scalable Pattern Matching in Computation Graphs
by: Mondada, Luca, et al.
Published: (2024)

Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth $p=1$
by: Tate, Reuben, et al.
Published: (2024)

A Lower Bound for the Max Entropy Algorithm for TSP
by: Jin, Billy, et al.
Published: (2023)

Improved Upper Bounds for the Directed Flow-Cut Gap
by: Bodwin, Greg, et al.
Published: (2026)

Min-Max Connected Multiway Cut
by: Tiwary, Hans Raj, et al.
Published: (2026)

Quantum Filtering and Analysis of Multiplicities in Eigenvalue Spectra
by: Ding, Zhiyan, et al.
Published: (2025)

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
by: Huang, Jeremy Ahrens, et al.
Published: (2024)

Entrywise Low-Rank Approximation and Matrix $p \rightarrow q$ Norms via Global Correlation Rounding
by: Anderson, Prashanti, et al.
Published: (2026)

Additive Approximation Schemes for Low-Dimensional Embeddings
by: Anderson, Prashanti, et al.
Published: (2025)

Algorithmic Cluster Expansions for Quantum Problems
by: Mann, Ryan L., et al.
Published: (2023)

Efficient Algorithms for Weakly-Interacting Quantum Spin Systems
by: Mann, Ryan L., et al.
Published: (2026)

Complexity of Digital Quantum Simulation in the Low-Energy Subspace: Applications and a Lower Bound
by: Gong, Weiyuan, et al.
Published: (2023)

Quantum divide and conquer
by: Childs, Andrew M., et al.
Published: (2022)

Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
by: Lucke, Felicia, et al.
Published: (2024)

Cuts in Graphs with Matroid Constraints
by: Banik, Aritra, et al.
Published: (2024)

Approximate Counting in Local Lemma Regimes
by: Mann, Ryan L., et al.
Published: (2025)

EPTAS for Hard Graph Cut Problems for Dense Graphs
by: Deguchi, Kaisei, et al.
Published: (2026)

Quantum Approximate Optimization Algorithms for Maximum Cut on Low-Girth Graphs
by: Li, Tongyang, et al.
Published: (2024)

Sum-Of-Squares To Approximate Knapsack
by: Kothari, Pravesh K., et al.
Published: (2025)

Query-optimal estimation of unitary channels in diamond distance
by: Haah, Jeongwan, et al.
Published: (2023)

Optimal Bounds for Distinct Quartics
by: Charalampopoulos, Panagiotis, et al.
Published: (2024)

Lower Bounds on Tree Covers
by: Chen, Yu, et al.
Published: (2025)

Local Max-Cut on Sparse Graphs
by: Schwartzman, Gregory
Published: (2023)

Conjectured Bounds for 2-Local Hamiltonians via Token Graphs
by: Apte, Anuj, et al.
Published: (2025)

Improved Certificates for Independence Number in Semirandom Hypergraphs
by: Kothari, Pravesh, et al.
Published: (2026)

Scalable Experimental Bounds for Entangled Quantum State Fidelities
by: Aktar, Shamminuj, et al.
Published: (2022)

Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs
by: Li, Jianqiang, et al.
Published: (2024)