7 papers · 1 filter
Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization
Shouvanik Chakrabarti, Dylan Herman, Guneykan Ozgul +6
We analyze generalizations of quantum algorithms based on the short path framework first proposed by Hastings~[\textit{Quantum} 2, 78 (2018)], which has been extended and shown by…
Provably faster randomized and quantum algorithms for -means clustering via uniform sampling
Tyler Chen, Archan Ray, Akshay Seshadri +6
The -means algorithm (Lloyd's algorithm) is a widely used method for clustering unlabeled data. A key bottleneck of the -means algorithm is that each iteration requires time…
Mechanisms for Quantum Advantage in Global Optimization of Nonconvex Functions
Dylan Herman, Guneykan Ozgul, Anuj Apte +4
We present new theoretical mechanisms for quantum speedup in the global optimization of nonconvex functions, expanding the scope of quantum advantage beyond traditional tunneling-b…
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…
A simple analysis of a quantum-inspired algorithm for solving low-rank linear systems
Tyler Chen, Junhyung Lyle Kim, Archan Ray +3
We describe and analyze a simple algorithm for sampling from the solution to a linear system . We assume…
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…