QuantumHermit interviewed Cohen et al on their work on using Google’s D-Wave for portfolio optimization . Following is the interview …
We were motivated by the idea of well understood and valuable challenge, financial portfolio optimization, and solve it both classically and with a quantum computer. We set our sights on a problem that was challenging classically, a universe of 40 liquid US equities with one year of historical data, and we solved it on a D-Wave quantum annealing computer. Our goal as a team is not to beat the stock market, but to help asset managers and individual investors build optimal portfolios, and improve investment productivity.
What is financial portfolio optimization? It is the art of building an investment portfolio which delivers the highest expected return for each measure of risk. The decades-old formulation is the Sharpe ratio, which divides expected return (%) by standard deviation of returns (%). Put into regular language, can we earn more profit for each unit of risk taken?
To simplify the problem and eliminate much of the guesswork of picking your expectation of market returns, or the risk free rate set by the US Treasury, we created a ratio that divides the market momentum by the standard deviation of returns. Market momentum is made up of covariances of stocks against the market for that portfolio. This gives us an effective and conservative way to build portfolios that is only based on the movements of stocks, and we call this the Chicago Quantum Ratio (CQR).
However, quantum annealing computers run off a QUBO, or a quadratic, unconstrained binary optimization problem. This is matrix mathematics that is linear…so it cannot divide a ratio. Our team’s first significant innovation was to reformulate the problem into a linear formulation, which nets portfolio variance against the expected return of the portfolio, raised to a power. This builds a metric that allows a user to find effective portfolios on or near the efficient frontier, and can be run effectively on a quantum annealing computer. We see this in figure 1.
The second significant innovation was to tune and engineer the solution to run on the D-Wave effectively so we have enough ‘valid portfolios’ to answer the question, and pick the best portfolios with confidence. We build multiple matrices to solve the problem. We apply affine transformations to shift the values of each matrix, while keeping our valid portfolios exactly accurate. Finally, we learn how to scale and apply negative and positive signs to our matrix values. These three steps allow us to maintain a binary problem, and enable the D-Wave to more often see the energy levels and solutions we want.
Let’s step back and see how we solve the problem classically.
We use brute force to evaluate every portfolio option. For 28 assets, or 2^28 portfolios, this takes a few hours on a desktop. For 32 assets, or 2^32 portfolios, this takes days on our laptop. For 40 assets, 2^40 portfolios, or 1.1 trillion portfolios, this would take a long time to complete, but we can validate the quantum results.
We use a genetic algorithm to find the one best solution, in a timeframe competitive with a quantum computer. It gave us a 3 out of 40 asset solution consistently after 80 generations of 60 solutions, and 1028 initial seeds. We modify the level of mutation to look for deeper solutions. Interestingly enough, when we seed the genetic algorithm with the D-Wave results, it came to the same answer in 2/3 of the time.
We used random sampling, a form of Monte Carlo analysis, and found good solutions, but not as good as the D-Wave system. By comparison, we ran 950M random samples against the D-Wave running 60,000 samples. To ensure the D-Wave was not giving us random solutions, we compared the averages for each portfolio size (e.g., the number of stocks to receive an even amount of investment). For solutions under 25 assets, the D-Wave had better answers (see figure 6). For the largest portfolios, random samples did better.
We also found a heuristic approach where we find portfolio ‘Allstars’ that appear most often in the best portfolios. We also find portfolio ‘Dogstars’ that appear most often in the worst portfolios. We can build larger and better portfolios by gathering and pre-selecting Allstars and avoiding Dogstars. We plan to leverage this learning, or what we see as the value of stock picking, when we run our algorithm on gate-based quantum computers.
Overall, the answers were best from the genetic algorithm (one best solution), followed by D-Wave, then random sampling. In terms of timing, the genetic algorithm was comparable to D-Wave, but was far faster than random sampling for equivalent quality answers.
Our next steps include increasing the portfolio size to 60 assets, then potentially 80 assets. This take the problem outside the scale where we can solve it classically with brute force knowing all the answers, at least without use of a supercomputer. We will also link together a synthetic annealer with a genetic algorithm, which will improve our classical speed, and give the quantum computer a tougher comparison. Finally, we will invest to improve our engineering to accelerate and improve our quantum results.
Although this work was all self-funded by the team over the course of a year, we would like to acknowledge and thank the writers, maintainers, and community contributors for Python, Numpy, Pandas, Matplotlib, Scipy and DWave Ocean, Julia and R. We also thank D-Wave Systems, Google, Slack, Anaconda, and Jupiter for the use of their tools in this research effort.
Our data was 40 US traded liquid stocks as of 1536 CT, on June 24, 2020. We have the data if other researchers would like to replicate our research.
The paper can be found here : https://arxiv.org/abs/2007.01430