Quantum Algorithms for Portfolio Optimization

We develop the first quantum algorithm for the constrained portfolio optimization problem. The algorithm has running time widetildeO left( n√r fraczeta kappaδ2 log left(1/εright) right), where r is the number of positivity and budget constraints, n is the number of assets in the portfolio, ε the desired precision, and δ, 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 widetildeO left( √rnωlog(1/ε) right), 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.