Quantum Algorithms for Portfolio Optimization

Iordanis Kerenidis, Anupam Prakash and D\'aniel Szil\'agyi

Papers from arXiv.org

Abstract: We develop the first quantum algorithm for the constrained portfolio optimization problem. The algorithm has running time $\widetilde{O} \left( n\sqrt{r} \frac{\zeta \kappa}{\delta^2} \log \left(1/\epsilon\right) \right)$, where $r$ is the number of positivity and budget constraints, $n$ is the number of assets in the portfolio, $\epsilon$ the desired precision, and $\delta, \kappa, \zeta$ 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 $\widetilde{O} \left( \sqrt{r}n^\omega\log(1/\epsilon) \right)$, where $\omega$ 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.

Date: 2019-08
New Economics Papers: this item is included in nep-cmp
References: View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://arxiv.org/pdf/1908.08040 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:1908.08040

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().