Photo by Claudia on Unsplash
This week: Quantum Algorithms for Portfolio Optimization by Iordanis Kerenidis, Anupam Prakash, and Dániel Szilágyi
Date of publication: 22/08/2019
To cite this paper: arXiv:1908.08040 [math.OC]
Links: Article in PDF: https://arxiv.org/pdf/1908.08040v1.pdf
Date of publication: 22/08/2019
To cite this paper: arXiv:1908.08040 [math.OC]
Links: Article in PDF: https://arxiv.org/pdf/1908.08040v1.pdf
Abstract : We develop the first quantum algorithm for the constrained portfolio optimization problem. The algorithm has running time (see image above), where r is the number of positivity and budget constraints, n is the number of assets in the portfolio, ϵ the desired precision, and δ,κ,ζ are problem-dependent parameters related to the well-conditioning of the intermediate solutions. If only a moderately accurate solution is required, our quantum algorithm can achieve a polynomial speedup over the best classical algorithms with complexity (see image above), where ω is the matrix multiplication exponent that has a theoretical value of around 2.373, but is closer to 3 in practice. We also provide some experiments to bound the problem-dependent factors arising in the running time of the quantum algorithm, and these experiments suggest that for most instances the quantum algorithm can potentially achieve an O(n) speedup over its classical counterpart.