5 papers
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…