Publications (29)
Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing
Atithi Acharya, Romina Yalovetzky, Pierre Minssen +10
Industrially relevant constrained optimization problems, such as portfolio optimization and portfolio rebalancing, are often intractable or difficult to solve exactly. In this work…
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…
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…
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…
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…
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…
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…
Solving Linear Systems on Quantum Hardware with Hybrid HHL++
Romina Yalovetzky, Pierre Minssen, Dylan Herman +1
The limited capabilities of current quantum hardware significantly constrain the scale of experimental demonstrations of most quantum algorithmic primitives. This makes it challeng…
Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
Pradeep Niroula, Ruslan Shaydulin, Romina Yalovetzky +4
Realizing the potential of near-term quantum computers to solve industry-relevant constrained-optimization problems is a promising path to quantum advantage. In this work, we consi…
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…
A Survey of Quantum Computing for Finance
Dylan Herman, Cody Googin, Xiaoyuan Liu +5
Quantum computers are expected to surpass the computational capabilities of classical computers during this decade and have transformative impact on numerous industry sectors, part…
Constrained Optimization via Quantum Zeno Dynamics
Dylan Herman, Ruslan Shaydulin, Yue Sun +6
Constrained optimization problems are ubiquitous in science and industry. Quantum algorithms have shown promise in solving optimization problems, yet none of the current algorithms…
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…
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…
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…
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…
Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti +4
Quantum alternating operator ansatz (QAOA) has a strong connection to the adiabatic algorithm, which it can approximate with sufficient depth. However, it is unclear to what extent…
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…
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…
Expressivity of Variational Quantum Machine Learning on the Boolean Cube
Dylan Herman, Rudy Raymond, Muyuan Li +3
Categorical data plays an important part in machine learning research and appears in a variety of applications. Models that can express large classes of real-valued functions on th…
Quantum Machine Learning for Finance
Marco Pistoia, Syed Farhan Ahmad, Akshay Ajagekar +10
Quantum computers are expected to surpass the computational capabilities of classical computers during this decade, and achieve disruptive impact on numerous industry sectors, part…
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…
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…
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…
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…
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…
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…
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…
Quantum Deep Hedging
El Amine Cherrat, Snehal Raj, Iordanis Kerenidis +12
Quantum machine learning has the potential for a transformative impact across industry sectors and in particular in finance. In our work we look at the problem of hedging where dee…