Quantum Algorithms for Portfolio Optimization
Iordanis Kerenidis, Anupam Prakash, Dániel Szilágyi · 2019
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.