181 citations · 237 across the 18 of their papers we have counts for
20 papers
Quantum Simulation on Riemannian Manifolds
Dylan Herman, Jacob Watkins, Guneykan Ozgul +4
We investigate algorithms for the quantum simulation of the Schrödinger equation on a Riemannian manifold, where the kinetic operator is defined by the Laplace--Beltrami operator c…
An analysis of iterative refinement for quantum linear system solvers
Adrian Harkness, Mohammadhossein Mohammadisiahroudi, Brandon Augustino +2
We present and analyze an iterative refinement (IR) framework for improving the precision dependence of algorithms that combine a quantum linear system algorithm (QLSA) with quantu…
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…
Global Multi-Maturity SPX-VIX Calibration Beyond Markovian Stitching
Atithi Acharya, Yue Sun, Brandon Augustino +3
We develop a global martingale optimal transport framework for joint S&P 500 (SPX)-VIX smile calibration across multiple maturities, without the conditional independence that Marko…
Faster Algorithms for Multimarginal Optimal Transport
Brandon Augustino, Yue Sun, Atithi Acharya +4
We study constructive discrete multimarginal optimal transport (MOT) among distributions on points, where the cost tensor has entries. For additive accuracy $\v…
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…
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…
Strategies for running the QAOA at hundreds of qubits
Brandon Augustino, Madelyn Cain, Edward Farhi +5
We explore strategies aimed at reducing the amount of computation, both quantum and classical, required to run the Quantum Approximate Optimization Algorithm (QAOA). First, followi…
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…
Quantum Computing Inspired Iterative Refinement for Semidefinite Optimization
Mohammadhossein Mohammadisiahroudi, Brandon Augustino, Pouya Sampourmahani +1
Iterative Refinement (IR) is a classical computing technique for obtaining highly precise solutions to linear systems of equations, as well as linear optimization problems. In this…
Challenges and Opportunities in Quantum Optimization
Amira Abbas, Andris Ambainis, Brandon Augustino +43
Recent advances in quantum computers are demonstrating the ability to solve problems at a scale beyond brute force classical simulation. As such, a widespread interest in quantum a…
A quantum central path algorithm for linear optimization
Brandon Augustino, Jiaqi Leng, Giacomo Nannicini +2
We propose a novel quantum algorithm for solving linear optimization problems by quantum-mechanical simulation of the central path. While interior point methods follow the central…
Improvements to Quantum Interior Point Method for Linear Optimization
Mohammadhossein Mohammadisiahroudi, Zeguan Wu, Brandon Augustino +2
Quantum linear system algorithms (QLSA) have the potential to speed up Interior Point Methods (IPM). However, a major challenge is that QLSAs are inexact and sensitive to the condi…
Generating Linear, Semidefinite, and Second-order Cone Optimization Problems for Numerical Experiments
Mohammadhossein Mohammadisiahroudi, Ramin Fakhimi, Brandon Augustino +1
The numerical performance of algorithms can be studied using test sets or procedures that generate such problems. This paper proposes various methods for generating linear, semidef…
An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization
Zeguan Wu, Mohammadhossein Mohammadisiahroudi, Brandon Augustino +2
Quantum linear system algorithms (QLSAs) have the potential to speed up algorithms that rely on solving linear systems. Interior Point Methods (IPMs) yield a fundamental family of…
Solving the semidefinite relaxation of QUBOs in matrix multiplication time, and faster with a quantum computer
Brandon Augustino, Giacomo Nannicini, Tamás Terlaky +1
Recent works on quantum algorithms for solving semidefinite optimization (SDO) problems have leveraged a quantum-mechanical interpretation of positive semidefinite matrices to deve…
Quantum Interior Point Methods for Semidefinite Optimization
Brandon Augustino, Giacomo Nannicini, Tamás Terlaky +1
We present two quantum interior point methods for semidefinite optimization problems, building on recent advances in quantum linear system algorithms. The first scheme, more simila…
Co-optimizing the Smart Grid and Electric Public Transit Bus System
Mertcan Yetkin, Brandon R. Augustino, Alberto J. Lamadrid +1
As climate change provides impetus for investing in smart cities, with electrified public transit systems, we consider electric public transportation buses in an urban area, which…