7 papers
SYK thermal expectations are classically easy at any temperature
Alexander Zlokapa, Bobak T. Kiani
Estimating thermal expectations of local observables is a natural target for quantum advantage. We give a simple classical algorithm that approximates thermal expectations for Gibb…
Optimizing Sparse SYK
Matthew Ding, Robbie King, Bobak T. Kiani +1
Finding the ground state of strongly-interacting fermionic systems is often the prerequisite for fully understanding both quantum chemistry and condensed matter systems. The Sachde…
Average-case quantum complexity from glassiness
Alexander Zlokapa, Bobak T. Kiani, Eric R. Anschuetz
Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms. For example, it can obstruct constant-time…
Slow Mixing of Quantum Gibbs Samplers
David Gamarnik, Bobak T. Kiani, Alexander Zlokapa
Preparing thermal (Gibbs) states is a common task in physics and computer science. Recent algorithms mimic cooling via system-bath coupling, where the cost is determined by mixing…
Combinatorial NLTS From the Overlap Gap Property
Eric R. Anschuetz, David Gamarnik, Bobak Kiani
In an important recent development, Anshu, Breuckmann, and Nirkhe [ABN22] resolved positively the so-called No Low-Energy Trivial State (NLTS) conjecture by Freedman and Hastings.…
Strongly interacting fermions are non-trivial yet non-glassy
Eric R. Anschuetz, Chi-Fang Chen, Bobak T. Kiani +1
Random spin systems at low temperatures are glassy and feature computational hardness in finding low-energy states. We study the random all-to-all interacting fermionic Sachdev--Ye…