119 citations · 825 across the 44 of their papers we have counts for
51 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…
Quantum algorithms for orthogonal polynomial transforms
Anupam Prakash, Shree Hari Sureshbabu, Dylan Herman +1
A quantum orthogonal polynomial transform (QOPT) is an algorithmic primitive that maps a superposition of standard basis states coherently to a basis of norm…
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…
Cycle Codes and Decoded Quantum Interferometry
Anuj Apte, Shouvanik Chakrabarti, Andi Gu +6
Decoded Quantum Interferometry (DQI) reduces optimization problems with two-variable constraints to decoding cycle codes. For one such problem, namely MaxCut, prior work showed tha…
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…
Anytime Training with Schedule-Free Spectral Optimization
Anuj Apte, Pranav Deshpande, Niraj Kumar +2
Standard neural network training relies on learning-rate schedules tied to a fixed horizon, leading to strong path dependence and costly re-tuning as data availability changes. Sch…
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…
Digital signatures with classical shadows on near-term quantum computers
Pradeep Niroula, Minzhao Liu, Sivaprasad Omanakuttan +15
Quantum mechanics provides cryptographic primitives whose security is grounded in hardness assumptions independent of those underlying classical cryptography. However, existing pro…
Quantum Speedups for Derivative Pricing Beyond Black-Scholes
Dylan Herman, Yue Sun, Jin-Peng Liu +5
This paper explores advancements in quantum algorithms for derivative pricing of exotics, a computational pipeline of fundamental importance in quantitative finance. For such cases…
Realization of a Quantum Streaming Algorithm on Long-lived Trapped-ion Qubits
Pradeep Niroula, Shouvanik Chakrabarti, Steven Kordonowy +30
Large classical datasets are often processed in the streaming model, with data arriving one item at a time. In this model, quantum algorithms have been shown to offer an unconditio…
Certified randomness amplification by dynamically probing remote random quantum states
Minzhao Liu, Pradeep Niroula, Matthew DeCross +49
Cryptography depends on truly unpredictable numbers, but physical sources emit biased or correlated bits. Quantum mechanics enables the amplification of imperfect randomness into n…
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…
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…
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…
A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values
Tyler Chen, Akshay Seshadri, Mattia J. Villani +7
Shapley values have emerged as a critical tool for explaining which features impact the decisions made by machine learning models. However, computing exact Shapley values is diffic…
Threshold for Fault-tolerant Quantum Advantage with the Quantum Approximate Optimization Algorithm
Sivaprasad Omanakuttan, Zichang He, Zhiwei Zhang +9
Optimization is often cited as a promising application of quantum computers. However, the low degree of provable quantum speedups has led prior rigorous end-to-end resource analyse…
Certified randomness using a trapped-ion quantum processor
Minzhao Liu, Ruslan Shaydulin, Pradeep Niroula +29
While quantum computers have the potential to perform a wide range of practically important tasks beyond the capabilities of classical computers, realizing this potential remains a…
Applications of Certified Randomness
Omar Amer, Shouvanik Chakrabarti, Kaushik Chakraborty +8
Certified randomness can be generated with untrusted remote quantum computers using multiple known protocols, one of which has been recently realized experimentally. Unlike the ran…
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…
qReduMIS: A Quantum-Informed Reduction Algorithm for the Maximum Independent Set Problem
Martin J. A. Schuetz, Romina Yalovetzky, Ruben S. Andrist +8
We propose and implement a quantum-informed reduction algorithm for the maximum independent set problem that integrates classical kernelization techniques with information extracte…