by Kerenidis, Iordanis, Prakash, Anupam and Szilágyi, Dániel
Abstract:
We develop the first quantum algorithm for the constrained portfolio optimization problem. The algorithm has running time Õ (n√r ζk/δ2 log (1/ϵ)), 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 Õ (√rnω log(1/ϵ)), 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.
Reference:
Quantum Algorithms for Portfolio Optimization (Kerenidis, Iordanis, Prakash, Anupam and Szilágyi, Dániel), In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, Association for Computing Machinery, 2019.
Bibtex Entry:
@inproceedings{10.1145/3318041.3355465,
abstract = {We develop the first quantum algorithm for the constrained portfolio optimization problem. The algorithm has running time \~{O} (n√r ζk/δ2 log (1/ϵ)), 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 \~{O} (√rnω log(1/ϵ)), 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.},
address = {New York, NY, USA},
author = {Kerenidis, Iordanis and Prakash, Anupam and Szil\'{a}gyi, D\'{a}niel},
booktitle = {Proceedings of the 1st ACM Conference on Advances in Financial Technologies},
date-added = {2021-03-09 21:09:48 +0100},
date-modified = {2021-03-09 21:09:48 +0100},
doi = {10.1145/3318041.3355465},
isbn = {9781450367325},
keywords = {quantum algorithms, quantum optimization, second order cone programs, portfolio optimization},
location = {Zurich, Switzerland},
numpages = {9},
pages = {147–155},
publisher = {Association for Computing Machinery},
series = {AFT '19},
title = {Quantum Algorithms for Portfolio Optimization},
url = {https://doi.org/10.1145/3318041.3355465},
year = {2019},
bdsk-url-1 = {https://doi.org/10.1145/3318041.3355465}}