From the 1 of 8 linked papers with an AI index.
Showing quant-phShow all
3 papers · 1 filter
quant-ph2026
Circuit complexity lower bounds for quantum spin glasses
Omar Al-Ghattas, David Gamarnik
The paper proves that preparing near‑optimal low‑energy states of random quantum p‑spin glass Hamiltonians requires circuits of at least logarithmic depth, showing that shallow qua…
quant-ph2025
Spin Glass Transitions Obstruct Decoded Quantum Interferometry
Eric R. Anschuetz, David Gamarnik, Jonathan Z. Lu
Quantum algorithms are believed to offer advantages in solving certain hard discrete optimization problems, yet identifying when such advantages persist in explicit distributions o…
quant-ph2024
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…