7 papers
Faster Algorithms for Multimarginal Optimal Transport
Brandon Augustino, Yue Sun, Atithi Acharya +4
We study algorithms for approximating the multimarginal optimal transport (MOT) distance, a generalization of the classic optimal transport distance, between discrete probabili…
Regularized Warm-Started Quantum Approximate Optimization and Conditions for Surpassing Classical Solvers on the Max-Cut Problem
Zichang He, Anuj Apte, Brandon Augustino +4
Demonstrating quantum heuristics that outperform strong classical solvers on large-scale optimization remains an open challenge. Here we introduce Regularized Warm-Started QAOA (RW…
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…
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…
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…