1 citations · 1 across the 7 of their papers we have counts for
7 papers
When quantum thermal states look classical
Harald Putterman, Alexander Zlokapa, Jordan Cotler
At high temperature, quantum Gibbs states retain several classical features of the maximally mixed state: the absence of entanglement, the absence of magic, analyticity of the part…
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…