286 citations · 910 across the 29 of their papers we have counts for
32 papers · 1 filter
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…
Decoupling of the QAOA into independent spin-boson systems and high-depth performance on pure and mixed spin glasses
Sami Boulebnane, Abid Khan, Pragna Subrahmanya +4
The Quantum Approximate Optimization Algorithm (QAOA) is regarded as a promising candidate for near-term quantum advantage in combinatorial optimization, yet our ability to study i…
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…
Fault-tolerant execution of error-corrected quantum algorithms
Michael A. Perlin, Zichang He, Anthony Alexiades Armenakas +9
Scaling up quantum algorithms to tackle high-impact problems in science and industry requires quantum error correction and fault tolerance. While progress has been made in experime…
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…
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…
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…
Spin-Boson Mapping of the Quantum Approximate Optimization Algorithm
Sami Boulebnane, Abid Khan, Minzhao Liu +4
The Quantum Approximate Optimization Algorithm (QAOA) achieves monotonically improving performance with circuit depth , yet the study of the high-depth regime has been obstructe…
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…
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…
Iterative Interpolation Schedules for Quantum Approximate Optimization Algorithm
Anuj Apte, Shree Hari Sureshbabu, Ruslan Shaydulin +5
Quantum Approximate Optimization Algorithm (QAOA) is a promising quantum heuristic with empirical evidence of speedup over classical state-of-the-art for some problems. QAOA uses a…
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…
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…
Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
Zichang He, Ruslan Shaydulin, Dylan Herman +4
Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising quantum heuristics for combinatorial optimization. While QAOA has been shown to perform well on small…
Prospects of Privacy Advantage in Quantum Machine Learning
Jamie Heredge, Niraj Kumar, Dylan Herman +5
Ensuring data privacy in machine learning models is critical, particularly in distributed settings where model gradients are typically shared among multiple parties to allow collab…
Quantum option pricing via the Karhunen-Loève expansion
Anupam Prakash, Yue Sun, Shouvanik Chakrabarti +8
We consider the problem of pricing discretely monitored Asian options over monitoring points where the underlying asset is modeled by a geometric Brownian motion. We provide tw…
The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ansätze
Enrico Fontana, Dylan Herman, Shouvanik Chakrabarti +5
Using tools from the representation theory of compact Lie groups, we formulate a theory of Barren Plateaus (BPs) for parameterized quantum circuits whose observables lie in their d…
Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti +26
The quantum approximate optimization algorithm (QAOA) is a leading candidate algorithm for solving optimization problems on quantum computers. However, the potential of QAOA to tac…
Quantum computing for finance
Dylan Herman, Cody Googin, Xiaoyuan Liu +5
Quantum computers are expected to surpass the computational capabilities of classical computers and have a transformative impact on numerous industry sectors. We present a comprehe…
Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
Ruben S. Andrist, Martin J. A. Schuetz, Pierre Minssen +9
Rydberg atom arrays are among the leading contenders for the demonstration of quantum speedups. Motivated by recent experiments with up to 289 qubits [Ebadi et al., Science 376, 12…
Parameter Setting in Quantum Approximate Optimization of Weighted Problems
Shree Hari Sureshbabu, Dylan Herman, Ruslan Shaydulin +4
Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate algorithm for solving combinatorial optimization problems on quantum computers. However, in many cases QAOA…