Quantum Portfolio Optimization
On high-level, quantum portfolio optimization is to optimize the selection, weighting, and risk management of financial assets in a portfolio, which is specialized application within optimization problem domain. Therefore, high-level approach should be similar: finding objective function to optimize. This post will focus on portfolio optimization-related financial concepts, common approaches and qiskit approach.
Financial Concepts
Modern Portfolio Theory
Key concepts: expected return, acceptable risk/volatility (The portfolio’s risk is a function of the variances of each asset and the correlations of each pair of assets. To calculate the risk of a four-asset portfolio, an investor needs each of the four assets’ variances and six correlation values (asset returns move together), since there are six possible two-asset combinations with four assets.), efficient frontier (comprises investment portfolios that offer the highest expected return for a specific level of risk.), efficient (Portfolio A (has an expected return of 8.5% and a standard deviation of 8%) is more efficient than Portfolio B (has an expected return of 8.5% and a standard deviation of 9.5%).)
Criticism of the MPT: it evaluates portfolios based on variance rather than downside risk (e.g. same variance, but investors usually prefer frequent small losses than rare but spectacular loss).
Difference with MPT
- The PMPT uses the standard deviation of negative returns (vs. MPT’s standard deviation of all returns) as the measure of risk, while modern portfolio theory uses the standard deviation of all returns as a measure of risk.
- The Sortino ratio was introduced into the PMPT rubric to replace MPT’s Sharpe ratio as a measure of risk-adjusted returns and improved upon its ability to rank investment results.
Mean-variance optimization/MPT is to use diversification to balance the risk and return.
- The expected return of the portfolio. This is the “mean” of mean variance optimization.
- The standard deviation of the return on the portfolio, which is treated as a measure of risk. The square of the standard deviation is the “variance” of mean variance optimization.
- The efficient frontier, which is the set of portfolios with expected return greater than any other with the same or lesser risk, and lesser risk than any other with the same or greater expected return.
asset covariance: relationship between the movement of two asset prices, used to optimize returns by including assets in their portfolio that have a negative covariance. The article has covariance formula, here are intuition of why this formula:
- difference between daily return minus the average daily is used to compute deviation
- difference for each asset for each period is multiplied to determine positive or negative relationship
- sum over all periods is to capture the overall relationship between the two assets across the entire time period
- divided by (n-1) is to normalize, so not impacted by period difference
The Sharpe ratio is the ratio between returns and risk. The lower the risk and the higher the returns, the higher the Sharpe ratio. The algorithm looks for the maximum Sharpe ratio, which translates to the portfolio with the highest return and lowest risk. Ultimately, the higher the Sharpe ratio, the better the performance of the portfolio. (>3)
Common mean-variance optimization algorithms
Quadratic Programming
Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize (minimize or maximize) a multivariate quadratic function subject to linear constraints on the variables. Quadratic programming is a type of nonlinear programming.
The quadratic programming problem with n variables and m constraints can be formulated as follows. Given:
- a real-valued, n-dimensional vector c,
- an n×n-dimensional real symmetric matrix Q,
- an m×n-dimensional real matrix A, and
- an m-dimensional real vector b,
the objective of quadratic programming is to find an n-dimensional vector x, that will
minimize
subject to Ax⪯b,
More intuitively:
x: decision variables to optimize (quantities of products to produce or investments to make)
Q: interaction matrix of decision variables, quadratic part of the objective, which may also represent risk/variance
c: linear cost of decision variables
A: constraint matrix that relates your decision variables x to the constraint conditions (e.g. total production of product 1 and product 2 must be less than or equal to a certain limit)
b: budget, limits or bounds for the constraints (e.g., maximum total production or budget)
solving mean-variance optimization problems via quadratic programming
Gradient Descent Methods
Approximate solution; may require multiple iterations to converge, used for general optimization problems. Generally, gradient descent is a first-order method, which means it utilizes minimal information about the problem (only gradients) and thus converges slowly and might suffer from convergence issues. Taking into account more information about the problem, such as its quadratic nature and linear constraints, can yield faster and more robust algorithms. However, it can deal with non-convex, non-linear, and non-quadratic objective functions in high-dimensional spaces.
Monte Carlo Simulation with Optimization
The Monte Carlo simulation is a mathematical technique that predicts possible outcomes of an uncertain event, probabilistic model that can include an element of uncertainty or randomness in its prediction. Generally it relies on random sampling to approximate the solution.
The Monte Carlo method uses a random sampling of information to solve a statistical problem; while a simulation is a way to virtually demonstrate a strategy, can be used in corporate finance, options pricing, and especially portfolio management and personal finance planning.
Random sampling is not random walk. It is based on Law of Large Numbers (SLLN): the average result obtained from a large number of trials must be close to the expected value and will tend to approach it as more trials are conducted.
Use Monte Carlo method to simulate the future price of a stock
Core idea is to get an unbiased, representative group of samples from large ocean of possibilities, randomly evolving simulation
Qiskit approach
In classical computing, gradient descent and other optimization algorithms work iteratively, and they are often stuck in local optima or may take a long time to converge in high-dimensional spaces.
Key concepts in “The equality constraint is mapped to a penalty term which is scaled by a parameter and subtracted from the objective function. The resulting problem can be mapped to a Hamiltonian whose ground state corresponds to the optimal solution.”
Budget constraint is mapped to penalty term in the objective function, rewarding solutions that favor spending close to budget (common approach when solving optimization problems in quantum computing, especially when using Quantum Approximate Optimization Algorithm (QAOA) or SamplingVQE).
VQE (Variational quantum eigensolver, the problem described seems to quantum chemistry on molecular simulation): promising candidate hybrid-algorithms for observing quantum computation utility on noisy near-term devices. Variational algorithms are characterized by the use of a classical optimization algorithm to iteratively update a parameterized trial solution, or “ansatz”. Chief among these methods is the Variational Quantum Eigensolver (VQE) that aims to solve for the ground state of a given Hamiltonian represented as a linear combination of Pauli terms, with an ansatz circuit where the number of parameters to optimize over is polynomial in the number of qubits. Workflow to setup VQE is like QAOA: Setup Hamiltonian/objective function (like loss function in ML) that represents the problem goal, setup ansatz/model architecture for the problem, initialize model parameters and iterate, setup real objective function to leverage Hamiltonian, model to retrieve outcome from hardware, setup classical optimizer/run.
SamplingVQE: minimize a Hamiltonian (especially continuous objective function (e.g. quantum chemistry)) to find the ground state (the minimum energy state) of a quantum system, which can be translated to finding the optimal solution to an optimization problem. Sampling to estimate the expectation value of the Hamiltonian instead of directly computing it. This makes the algorithm more resilient to noise and allows it to work with noisy intermediate-scale quantum (NISQ) devices.
Key concepts in “Here an Operator instance is created for our Hamiltonian. In this case the paulis are from an Ising Hamiltonian translated from the portfolio problem.”
operator instance: in qiskit, represents a quantum operator, which is a mathematical object that acts on a quantum state. In this context, the Hamiltonian for portfolio optimization will be represented by a series of Pauli matrices (which are operators that act on individual qubits) that encode the problem’s objective.
Ising Hamiltonian: Ising Hamiltonian was originally constructed to understand the microscopic behavior of magnetic materials, particularly to grasp the condition that leads to a phase transition. However, its relative simplicity and natural mapping into QUBO (natural binary formulation and its ability to encode combinatorial relationships between variables) have made the Ising model a fundamental benchmark well beyond the field of quantum physics.
Run notebook
pip3 install qiskit-algorithms qiskit-finance qiskit-optimization qiskit-experimentsSample data for 4 assets
# expected return
array([ 0.01528439, -0.00078095, 0.00051792, 0.00087001])
# covariance
array([[ 2.54138859e-03, 7.34022167e-05, 1.28600531e-04,
-9.98612132e-05],
[ 7.34022167e-05, 2.58486713e-04, 5.30427595e-05,
4.44816208e-05],
[ 1.28600531e-04, 5.30427595e-05, 7.91504681e-04,
-1.23887382e-04],
[-9.98612132e-05, 4.44816208e-05, -1.23887382e-04,
1.97892585e-04]])The objective function of this sample
- The first term represents the negative expected return of the portfolio (to be maximized),
- The second term represents the portfolio risk (variance), λ is the risk aversion parameter. It controls how much the optimization algorithm will penalize risk.
- The third term is the penalty term that enforces the budget constraint, with ααbeing a penalty weight (a constant factor that controls how strongly the constraint is enforced). α: This is a hyperparameter that controls the strength of the penalty. A larger α value will place more emphasis on the budget constraint, making it more costly to exceed the budget.
After running SamplingVQE, I get
Optimal: selection [1. 0. 0. 1.], value -0.0149
----------------- Full result ---------------------
selection value probability
---------------------------------------------------
[1 0 0 1] -0.0149 0.7373
[0 0 1 1] -0.0010 0.0938
[0 1 1 0] 0.0008 0.0771Interpretation:
selection: indicating whether one of 4 asset is selected or not (1/selected, 0/not selected)
value: the value of the objective function
probability: how likely the solution
Includes initial state (initializing the quantum computer in a default state ∣0⟩, then transforming it to some desired (non-parametrized) state ∣ρ⟩ with unitary reference operator), a cost function that describes a specific problem with a set of parameters (usually represented as minimizing the expectation value of the observable representing energy (Hamiltonian), an ansatz to express the search space with these parameters, and an optimizer to iteratively explore the search space.
CCXGate, same as Toffoli gate, 3-qubit gate that generalizes the concept of the CNOT gate.
- The CCX gate has 3 qubits: one control qubit, another control qubit, and one target qubit.
- The gate flips the state of the target qubit (i.e., applies a Pauli-X gate) only if both of the control qubits are in the state ∣1⟩. Otherwise, it does nothing (i.e., the target qubit is unaffected).
RX gate: is a rotation gate that rotates the state of qubit 0 around the X-axis of the Bloch sphere by an angle of θ.
CRZ gate applies a rotation around the Z-axis by an angle θ on the target qubit only if the control qubit is in the state ∣1⟩. If the control qubit is in the state ∣0⟩, the target qubit is unchanged.
