3 papers
quant-ph2026
A Hierarchy of Spectral Gap Certificates for Frustration-Free Spin Systems
Kshiti Sneh Rai, Ilya Kull, Patrick Emonts +3
Estimating spectral gaps of quantum many-body Hamiltonians is a highly challenging computational task, even under assumptions of locality and translation-invariance. Yet, the quest…
cs.DS2025
A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
Harry Buhrman, Sevag Gharibian, Zeph Landau +3
We present an extremely simple polynomial-space exponential-time -approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomia…
quant-ph2025
Beating the natural Grover bound for low-energy estimation and state preparation
Harry Buhrman, Sevag Gharibian, Zeph Landau +3
Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics. In this work, we give quantum algorithms which, given any -body Ha…