66 citations · 66 across the 5 of their papers we have counts for
7 papers
Hypergraph cycle enumeration for efficient inference of planted k-XOR with smooth trade-off
Arman Babakhani, Enrico Fontana, Junhyung Lyle Kim +2
We introduce hypergraph cycle enumeration (HCE), a simple spectral framework for detecting and recovering planted signals in noisy hypergraph inference problems. We study HCE on on…
Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank
Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana +4
We establish a linear quantum query lower bound for high-accuracy convex optimization over an explicit family of -dimensional ellipsoids. We focus on linear optimization with an…
Quantum Speedups for Group Relaxations of Integer Linear Programs
Brandon Augustino, Dylan Herman, Guneykan Ozgul +5
Integer Linear Programs (ILPs) are a flexible and ubiquitous model for discrete optimization problems. Solving ILPs is \textsf{NP-Hard} yet of great practical importance. Super-qua…
End-to-end quantum algorithms for tensor problems
Enrico Fontana, Sivaprasad Omanakuttan, Junhyung Lyle Kim +4
We present a comprehensive end-to-end quantum algorithm for tensor problems, including tensor PCA and planted kXOR, that achieves potential superquadratic quantum speedups over cla…
On Speedups for Convex Optimization via Quantum Dynamics
Shouvanik Chakrabarti, Dylan Herman, Jacob Watkins +4
We explore the potential for quantum speedups in convex optimization using discrete simulations of the Quantum Hamiltonian Descent (QHD) framework, as proposed by Leng et al., and…
Fast Convex Optimization with Quantum Gradient Methods
Brandon Augustino, Dylan Herman, Enrico Fontana +4
We study quantum algorithms based on quantum (sub)gradient estimation using noisy function evaluation oracles, and demonstrate the first dimension-independent query complexities (u…
The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ansätze
Enrico Fontana, Dylan Herman, Shouvanik Chakrabarti +5
Using tools from the representation theory of compact Lie groups, we formulate a theory of Barren Plateaus (BPs) for parameterized quantum circuits whose observables lie in their d…