From the 1 of 7 linked papers with an AI index.
7 papers
When quantum thermal states look classical
Harald Putterman, Alexander Zlokapa, Jordan Cotler
The paper analyzes how quantum Gibbs states retain classical properties such as lack of entanglement and magic at finite temperatures, establishing a hierarchy of classical‑to‑quan…
Optimal Lower Bounds for Hamiltonian Simulation
Alexander Zlokapa, Richard R. Allen, Aram W. Harrow
For Hamiltonian , we prove asymptotically tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer. Our bounds hold…
The free energy limit of the SYK model at high temperature
David Gamarnik, Francisco Pernice, Alexander Schmidhuber +1
The Sachdev-Ye-Kitaev (SYK) model is a disordered quantum mean-field model studied in condensed matter physics and the holographic theory of black holes. Its structural properties…
A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations
Alexander Zlokapa
Estimating local observables in Gibbs states is a central problem in quantum simulation. While this task is BQP-complete at asymptotically low temperatures, the possibility of quan…
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…
Quartic quantum speedups for community detection
Alexander Schmidhuber, Alexander Zlokapa
Community detection is a foundational problem in data science. Its natural extension to hypergraphs captures higher-order correlations beyond pairwise interactions. In this work, w…