Portfolio Optimization with the Quantum Approximate Optimization Algorithm (QAOA)
Introduction
Portfolio optimization [1] is the process of allocating a portfolio of financial assets optimally, according to some predetermined goal. Usually, the goal is to maximize the potential return while minimizing the financial risk of the portfolio. One can express this problem as a combinatorial optimization problem like many other real-world problems. In this demo, we'll show how the Quantum Approximate Optimization Algorithm (QAOA) [2] can be employed on the Classiq platform to solve the problem of portfolio optimization.
Modeling the Portfolio Optimization Problem
As a first step, we have to model the problem mathematically. We will use a simple yet powerful model, which captures the essence of portfolio optimization:
-
A portfolio is built from a pool of \(n\) financial assets, each asset labeled \(i \in \{1,\ldots,n\}\).
-
Every asset's return is a random variable, with expected value \(\mu_i\) and variance \(\Sigma_i\) (modeling the financial risk involved in the asset).
-
Every two assets \(i \neq j\) have covariance \(\Sigma_{ij}\) (modeling market correlation between assets).
-
Every asset \(i\) has a weight \(w_i \in D_i = \{0,\ldots,b_i\}\) in the portfolio, with \(b_i\) defined as the budget for asset \(i\) (modeling the maximum allowed weight of the asset).
-
The return vector \(\mu\), the covariance matrix \(\Sigma\) and the weight vector \(w\) are defined naturally from the above (with the domain \(D = D_1 \times D_2 \times \ldots \times D_n\) for \(w\)).
With the above definitions, the total expected return of the portfolio is \(\mu^T w\) and the total risk is \(w^T \Sigma w\). We'll use a simple difference of the two as our cost function, with the additional constraint that the total sum of assets does not exceed a predefined budget \(B\). We note that there are many other possibilities for defining a cost function (e.g. add a scaling factor to the risk/return or even some non-linear relation). For reasons of simplicity we select the model below, and we assume all constants and variables are dimensionless. Thus, the problem is, given the constant inputs \(\mu, \Sigma, D, B\), to find optimal variable \(w\) as follows:
\(\begin{equation*} \min_{w \in D} w^T \Sigma w - \mu^T w, \end{equation*}\) subject to \(\Sigma_{i} w_i \leq B\).
The case presented above is called integer portfolio optimization, since the domains \(D_i\) are over the (positive) integers. Another variation of this problem defines weights over binary domains, and will not be discussed here.
Setup
With the mathematical definition in place, we begin the implementation by importing necessary packages and classes. We will use the following external dependencies:
- NumPy
- Matplotlib
- Pyomo - a python framework for modeling optimization problems, which the Classiq platform uses as an interface to these types of problems.
From the classiq package, we require classes related to combinatorial optimization and QAOA.
import numpy as np
import pyomo.core as pyo
The Portfolio Optimization Problem Parameters
First we define the parameters of the optimization problem, which include the expected return vector, the covariance matrix, the total budget and the asset-specific budgets:
returns = np.array([3, 4, -1])
# fmt: off
covariances = np.array(
[
[ 0.9, 0.5, -0.7],
[ 0.5, 0.9, -0.2],
[-0.7, -0.2, 0.9],
]
)
# fmt: on
total_budget = 6
specific_budgets = [2, 2, 2]
The Pyomo Model for the Problem
We proceed by defining the Pyomo model that will be used on the Classiq platform, using the problem parameters defined above:
portfolio_model = pyo.ConcreteModel("portfolio_optimization")
num_assets = len(returns)
# setting the variables
portfolio_model.w = pyo.Var(
range(num_assets),
domain=pyo.Integers,
bounds=lambda _, idx: (0, specific_budgets[idx]),
)
w_array = list(portfolio_model.w.values())
# setting the constraint
portfolio_model.budget_rule = pyo.Constraint(expr=(sum(w_array) <= total_budget))
# setting the expected return and risk
portfolio_model.expected_return = returns @ w_array
portfolio_model.risk = w_array @ covariances @ w_array
# setting the cost function to minimize
portfolio_model.cost = pyo.Objective(
expr=portfolio_model.risk - portfolio_model.expected_return, sense=pyo.minimize
)
Setting Up the Classiq Problem Instance
In order to solve the Pyomo model defined above, we use the Classiq combinatorial optimization engine. For the quantum part of the QAOA algorithm (QAOAConfig) - define the number of repetitions (num_layers):
from classiq import construct_combinatorial_optimization_model
from classiq.applications.combinatorial_optimization import OptimizerConfig, QAOAConfig
qaoa_config = QAOAConfig(num_layers=1)
For the classical optimization part of the QAOA algorithm we define the maximum number of classical iterations (max_iteration) and the \(\alpha\)-parameter (alpha_cvar) for running CVaR-QAOA, an improved variation of the QAOA algorithm [3]:
optimizer_config = OptimizerConfig(max_iteration=60, alpha_cvar=0.7)
Lastly, we load the model, based on the problem and algorithm parameters, which we can use to solve the problem:
qmod = construct_combinatorial_optimization_model(
pyo_model=portfolio_model,
qaoa_config=qaoa_config,
optimizer_config=optimizer_config,
)
We also set the quantum backend we want to execute on:
from classiq import set_execution_preferences
from classiq.execution import ClassiqBackendPreferences, ExecutionPreferences
backend_preferences = ExecutionPreferences(
backend_preferences=ClassiqBackendPreferences(backend_name="simulator")
)
qmod = set_execution_preferences(qmod, backend_preferences)
from classiq import write_qmod
write_qmod(qmod, "portfolio_optimization")
Synthesizing the QAOA Circuit and Solving the Problem
We can now synthesize and view the QAOA circuit (ansatz) used to solve the optimization problem:
from classiq import show, synthesize
qprog = synthesize(qmod)
show(qprog)
Opening: https://platform.classiq.io/circuit/5c17bd7f-2b65-4deb-94a5-6fb8708345d1?version=0.41.0.dev39%2B79c8fd0855
We now solve the problem by calling the execute function on the quantum program we have generated:
from classiq import execute
res = execute(qprog).result()
We can check the convergence of the run:
from classiq.execution import VQESolverResult
vqe_result = res[0].value
vqe_result.convergence_graph
And print the optimization results:
import pandas as pd
from classiq.applications.combinatorial_optimization import (
get_optimization_solution_from_pyo,
)
solution = get_optimization_solution_from_pyo(
portfolio_model, vqe_result=vqe_result, penalty_energy=qaoa_config.penalty_energy
)
optimization_result = pd.DataFrame.from_records(solution)
optimization_result.sort_values(by="cost", ascending=True).head(5)
| probability | cost | solution | count | |
|---|---|---|---|---|
| 98 | 0.003 | -4.8 | [1, 2, 1] | 3 |
| 141 | 0.003 | -4.8 | [1, 2, 1] | 3 |
| 35 | 0.006 | -4.8 | [2, 1, 1] | 6 |
| 5 | 0.010 | -4.8 | [2, 1, 1] | 10 |
| 210 | 0.002 | -4.8 | [1, 2, 1] | 2 |
idx = optimization_result.cost.idxmin()
print(
"x =", optimization_result.solution[idx], ", cost =", optimization_result.cost[idx]
)
x = [2, 1, 1] , cost = -4.800000000000001
And the histogram:
optimization_result.hist("cost", weights=optimization_result["probability"])
array([[<Axes: title={'center': 'cost'}>]], dtype=object)
Lastly, we can compare to the classical solution of the problem:
from pyomo.opt import SolverFactory
solver = SolverFactory("couenne")
solver.solve(portfolio_model)
portfolio_model.display()
Model portfolio_optimization
Variables:
w : Size=3, Index=w_index
Key : Lower : Value : Upper : Fixed : Stale : Domain
0 : 0 : 1.9999999999999998 : 2 : False : False : Integers
1 : 0 : 1.0000000000000002 : 2 : False : False : Integers
2 : 0 : 1.0000000000000002 : 2 : False : False : Integers
Objectives:
cost : Size=1, Index=None, Active=True
Key : Active : Value
None : True : -4.8
Constraints:
budget_rule : Size=1
Key : Lower : Body : Upper
None : None : 4.0 : 6.0
We can see that most of the solutions obtained by running QAOA are close to the minimal solution obtained classically, demonstrating the effectiveness of the algorithm. Also, note the non-trivial solution which includes a non-zero weight for the asset with negative expected return, demonstrating that it sometimes makes sense to include such assets in the portfolio as a risk-mitigation strategy - especially if they are highly anti-correlated with the rest of the assets.
References
[1]: Portfolio Optimization (Wikipedia)
[2]: Farhi, Edward, Jeffrey Goldstone, and Sam Gutmann. "A quantum approximate optimization algorithm." arXiv preprint arXiv:1411.4028 (2014).
[3]: Barkoutsos, Panagiotis Kl, et al. "Improving variational quantum optimization using CVaR." Quantum 4 (2020): 256.