6 citations · 8 across the 11 of their papers we have counts for
13 papers
Beyond Light Cones: State Preparation Complexity in Quantum Spin Glasses
Omar Al-Ghattas, David Gamarnik, Bobak T Kiani
We introduce a method for studying state preparation complexity in dense quantum -spin Hamiltonians on qubits, going beyond bounds based only on circuit lightcones. The key…
Circuit complexity lower bounds for quantum spin glasses
Omar Al-Ghattas, David Gamarnik
A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum -spin glasses, ra…
The stochastic block model has the overlap graph property for modularity
Shankar Bhamidi, David Gamarnik, Remco van der Hofstad +4
The overlap gap property (OGP) is a statement about the geometry of near-optimal solutions. Exhibiting OGP implies failure of a class of local algorithms; and has been observed to…
Price of Quality: Sufficient Conditions for Sparse Recovery using Mixed-Quality Data
Youssef Chaabouni, David Gamarnik
We study sparse recovery when observations come from mixed-quality sources: a small collection of high-quality measurements with small noise variance and a larger collection of low…
Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
David Gamarnik, Miklós Z. Rácz, Gabe Schoenbach
We study the problem of efficiently finding large common induced subgraphs of two independent Erdős--Rényi random graphs . Recently, Chatterjee and…
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…
The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Youssef Chaabouni, David Gamarnik
We consider the problem of support recovery for sparse binary signals from noisy linear measurements. For sparse Gaussian measurement matrices we identify sufficient conditions on…
Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes
David Gamarnik
The 2021 Nobel Prize in physics was awarded to Giorgio Parisi ``for the discovery of the interplay of disorder and fluctuations in physical systems from atomic to planetary scales,…
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…
Bounds on the ground state energy of quantum -spin Hamiltonians
Eric R. Anschuetz, David Gamarnik, Bobak T. Kiani
We consider the problem of estimating the ground state energy of quantum -local spin glass random Hamiltonians, the quantum analogues of widely studied classical spin glass mode…
Integrating High-Dimensional Functions Deterministically
David Gamarnik, Devin Smedira
We design a Quasi-Polynomial time deterministic approximation algorithm for computing the integral of a multi-dimensional separable function, supported by some underlying hyper-gra…
Computing the Volume of a Restricted Independent Set Polytope Deterministically
David Gamarnik, Devin Smedira
We construct a quasi-polynomial time deterministic approximation algorithm for computing the volume of an independent set polytope with restrictions. Randomized polynomial time app…
Product states optimize quantum -spin models for large
Eric R. Anschuetz, David Gamarnik, Bobak T. Kiani
We consider the problem of estimating the maximal energy of quantum -local spin glass random Hamiltonians, the quantum analogues of widely studied classical spin glass models. D…