Quantum option pricing via the Karhunen-Lo\`{e}ve expansion

• URL: http://arxiv.org/abs/2402.10132v1
• Date: Thu, 15 Feb 2024 17:37:23 GMT
• Title: Quantum option pricing via the Karhunen-Lo\`{e}ve expansion
• Authors: Anupam Prakash, Yue Sun, Shouvanik Chakrabarti, Charlie Che, Aditi Dandapani, Dylan Herman, Niraj Kumar, Shree Hari Sureshbabu, Ben Wood, Iordanis Kerenidis, Marco Pistoia
• Abstract summary: We consider the problem of pricing discretely monitored Asian options over $T$ monitoring points where the underlying asset is modeled by a geometric Brownian motion. We provide two quantum algorithms with complexity poly-logarithmic in $T$ and in $1/epsilon$, where $epsilon$ is the additive approximation error.
• Score: 11.698830761241107
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of pricing discretely monitored Asian options over $T$ monitoring points where the underlying asset is modeled by a geometric Brownian motion. We provide two quantum algorithms with complexity poly-logarithmic in $T$ and polynomial in $1/\epsilon$, where $\epsilon$ is the additive approximation error. Our algorithms are obtained respectively by using an $O(\log T)$-qubit semi-digital quantum encoding of the Brownian motion that allows for exponentiation of the stochastic process and by analyzing classical Monte Carlo algorithms inspired by the semi-digital encodings. The best quantum algorithm obtained using this approach has complexity $\widetilde{O}(1/\epsilon^{3})$ where the $\widetilde{O}$ suppresses factors poly-logarithmic in $T$ and $1/\epsilon$. The methods proposed in this work generalize to pricing options where the underlying asset price is modeled by a smooth function of a sub-Gaussian process and the payoff is dependent on the weighted time-average of the underlying asset price.

Related papers

• Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
  This paper considers the problem for finding the $(,epsilon)$-Goldstein stationary point of Lipschitz continuous objective. We construct a zeroth-order quantum estimator for the surrogate oracle function.
  arXiv  Detail & Related papers  (2024-10-21T16:52:26Z)
• Dividing quantum circuits for time evolution of stochastic processes by orthogonal series density estimation [0.0]
  Quantum Monte Carlo integration (QMCI) is a quantum algorithm to estimate expectations of random variables. In this paper, we propose a method to divide $U_X(t)$ based on orthogonal series density estimation. Our method achieves the circuit depth and total query complexity scaling as $O(sqrtN)$ and $O(N3/2)$, respectively.
  arXiv  Detail & Related papers  (2024-06-04T01:50:21Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging [8.990961435218544]
  We propose a first-order algorithm named $B$-sample dual averaging with the logarithmic barrier. For the Poisson inverse problem, our algorithm attains an $varepsilon$ solution in $smashtildeO(d3/varepsilon2)$ time. When computing the maximum-likelihood estimate for quantum state tomography, our algorithm yields an $varepsilon$-optimal solution in $smashtildeO(d3/varepsilon2)$ time.
  arXiv  Detail & Related papers  (2023-11-05T03:33:44Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  We propose a new reward-free algorithm for learning linear Markov decision processes (MDPs) At the core of our algorithm is uncertainty-weighted value-targeted regression with exploration-driven pseudo-reward. We show that our algorithm only needs to explore $tilde O( d2varepsilon-2)$ episodes to find an $varepsilon$-optimal policy.
  arXiv  Detail & Related papers  (2023-03-17T17:53:28Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  We develop quantum algorithms for sampling logconcave distributions and for estimating their normalizing constants. We exploit quantum analogs of the Monte Carlo method and quantum walks. We also prove a $1/epsilon1-o(1)$ quantum lower bound for estimating normalizing constants.
  arXiv  Detail & Related papers  (2022-10-12T19:10:43Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Fermionic partial tomography via classical shadows [0.0]
  We propose a tomographic protocol for estimating any $ k $-body reduced density matrix ($ k $-RDM) of an $ n $-mode fermionic state. Our approach extends the framework of classical shadows, a randomized approach to learning a collection of quantum-state properties, to the fermionic setting.
  arXiv  Detail & Related papers  (2020-10-30T06:28:26Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.