Remember me

Register  |   Lost password?


 

arXiv logo for blog page


Quantum Algorithms for Portfolio Optimization. (arXiv:1908.08040v1 [math.OC])

Thu, 22 Aug 2019 23:02:51 GMT

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.