9 papers
From Quantum Tunneling to Classical Optimization through Instantons
Jiayu Shen, Dylan Herman, Guneykan Ozgul +5
We use an instanton-based analysis to show that Path Integral Stochastic Gradient Descent (PISGD), a classical optimization algorithm instantiated from path integral Monte Carlo (P…
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…
Super-Quadratic Quantum Speedups for Combinatorial Optimization via Tilted Walks
Guneykan Ozgul, Shouvanik Chakrabarti
We introduce quantum tilted walks, a quantum algorithmic framework for solving exact combinatorial optimization problems. The framework applies an average of powers of a tilted Ham…
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…
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…
Quantum Speedups for Sampling and Non-convex Optimization with Stochastic Oracles
Guneykan Ozgul, Xiantao Li, Mehrdad Mahdavi +1
We present quantum speedups for sampling from distributions of the form on . We consider two stochastic oracle models: a stochastic gradient oracle,…
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…
Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions
Guneykan Ozgul, Xiantao Li, Mehrdad Mahdavi +1
We present quantum algorithms for sampling from non-logconcave probability distributions in the form of . Here, can be written as a finite sum $f(x):…