1 citations · 1 across the 7 of their papers we have counts for
6 papers · 1 filter
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…
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…
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…