233 citations · 516 across the 26 of their papers we have counts for
27 papers · 1 filter
An (almost) efficient classical algorithm for sampling from typical Gibbs states
Saleh Naghdi, Eric R. Anschuetz
Gibbs state preparation has emerged as a potential avenue for quantum advantage in the study of physical systems. Although there is known advantage for computing local properties o…
The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem
Mikhail Mints, Eric R. Anschuetz
In this work, we analyze the average-case hardness of approximation for the Quantum Hypergraph Max-Cut problem using the theoretical framework of the Quantum Overlap Gap Property (…
Fragmentation is Efficiently Learnable by Quantum Neural Networks
Mikhail Mints, Eric R. Anschuetz
In certain classes of physical quantum systems, the exponentially large state space "fragments" into many low-dimensional, dynamically disconnected subspaces. We introduce a learni…
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…
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…
k-Contextuality as a Heuristic for Memory Separations in Learning
Mariesa H. Teo, Willers Yang, James Sud +3
Classical machine learning models struggle with learning and prediction tasks on data sets exhibiting long-range correlations. Previously, the existence of a long-range correlation…