Quantum portfolio optimization

Welcome to the first blog post of “Entangled Portfolios”, a series about the applications that
quantum computing can have in finance.

This first post is about portfolio optimization, the task of selecting the optimal combination of
financial assets. It’s a bit like putting together the ultimate team for a project – you want
players with different strengths who work well together to get the best result without taking
on too much risk. This is called diversification and is the core idea behind portfolio
optimization, and it’s a major challenge in the world of finance.

Portfolio Optimization

Imagine you have some money to invest, and you’re looking at a bunch of different options –
maybe stocks from different companies. You don’t want to put all your eggs in one basket,
right? If that one company does badly, you could lose everything. So, you spread your
money around, creating a portfolio of different investments.

Portfolio optimization is all about figuring out the best way to spread your money across
different assets to achieve your financial goals. This usually means trying to get the highest
possible return on your investment while keeping the risk as low as possible. It’s a delicate
balancing act!

Think about it: some investments might offer potentially high returns but are also super risky.
Others might be safer but offer lower returns. The goal is to find the right mix that fits your
comfort level with risk and your desired return.

The challenge however is that there are too many possible combinations of financial assets
(and therefore too many portfolios) one can theoretically build and finding the absolute best
combination among all these possibilities is a type of problem called an optimization
problem. Classical computers can indeed face significant challenges when performing
portfolio optimization with a large number of assets and the reason lies in the rapidly
increasing computational complexity of the underlying mathematical problems (i.e. the
amount of calculation required) as the number of assets grows, in particular if you
incorporate real-world constraints such as transaction costs, limitations on asset holdings, or
regulatory requirements, resulting in further layers of complexity to the optimization problem.
To better understand why quantum computers can help handle this computations, let me
briefly introduce you to quantum annealing.

Quantum annealing

Quantum annealing is a specialized type of quantum computing designed to tackle complex
optimization problems. Unlike general-purpose quantum computers that use quantum gates
to perform a wide range of computations, quantum annealers are specifically engineered to
find the lowest energy state of a system, which corresponds to the optimal (or near-optimal)
solution to a problem.

To solve a problem using a quantum annealer, the problem must first be formulated as an
energy function, represented in the Quadratic Unconstrained Binary Optimization (QUBO)
form. This involves mapping the problem’s variables and their relationships onto the qubits
and their connections (couplers) in the quantum annealer. The biases applied to individual
qubits and the strengths of the couplers represent the costs and constraints of the
optimization problem, creating a unique energy landscape.
The QUBO model is:

$$\min_{\mathbf{x} \in {0, 1}^n} \left( \sum_{i=1}^n Q_{ii} x_i + \sum_{i<j} Q_{ij} x_i x_j\right)$$

or, in matrix formula:

$$\underset{x\in {0,1}^n}{min}{x}^{T}Qx$$

Where:

• x is a vector of n binary variables, where each xi can only take the value of either 0 or or 1. These variables represent the decisions or choices in the optimization problem

• Q is an N x N matrix, typically treated as upper triangular or symmetric
  because the quadratic term $$Q_{ji}x_jx_i$$ is equivalent to $Q_{ij}x_ix_j$ for binary
  variables. The entries of this matrix encode the problem’s structure and costs. In fact:
  • The diagonal elements $Q_{ii}$ represent the linear coefficients or biases
    associated with each individual binary variable $x_i$. If $Q_{ii}$ is positive,
    setting $x_i=1$ increases the objective function value; if negative, it
    decreases it.
  • The off-diagonal elements ($Q_{ij}$ for $i<j$): These represent the quadratic
    coefficients or coupling terms between pairs of binary variables $x_i$ and
    $x_j$. If it is non-zero, there is an interaction or relationship between the
    decisions represented by $x_i$ and $x_j$. The sign and magnitude of
    $Q_{ij}$ determine how the combination of $x_i=1$ and $x_j=1$ affects the
    objective function. A positive $Q_{ij}$ penalizes setting both $x_i$ and $x_j$
    to 1, while a negative $Q_{ij} encourages it

This formula is simply a way to say: we want to choose between 0s and 1s (which can
represent «yes» or «no» for each asset) in a way that makes the total cost as small as
possible. Every decision you make (like choosing to include an asset or not) has a cost
associated with it. Plus, there’s an additional cost or benefit when certain pairs of choices are
made together.

The «unconstrained» part of QUBO means there are no explicit constraints on the variables
other than them being binary. However, many problems with constraints can be transformed
into a QUBO formulation by incorporating the constraints into the objective function as
penalty terms. These penalty terms are designed to significantly increase the objective
function value if a constraint is violated, making solutions that violate constraints less
favorable during the minimization process.

The annealing process begins with the qubits in a state of superposition, influenced by a
strong initial quantum mechanical field that allows for easy tunneling across the energy
landscape. As the annealing progresses, this field is slowly reduced, and the problem’s
energy landscape (defined by the biases and couplers) becomes more prominent. If the
annealing process is carried out slowly enough, the system ideally stays in its ground state,
guided by the evolving energy landscape. At the end of the process, the quantum state of
the qubits collapses into a classical information (either 0s or 1s), representing a candidate
solution to the optimization problem.

Quantum annealing is particularly well-suited for combinatorial optimization problems, where
the goal is to find the best combination of discrete variables from a large set of possibilities
and among the best resources to learn more about this algorithm and play with it there’s
D-Wave SDK and documentation:
https://docs.dwavequantum.com/en/latest/quantum_research/quantum_annealing_intro.html

Portfolio Optimization as a QUBO problem

As we’ve seen, quantum annealing reduces to mapping the specific problem to a QUBO
problem. In the portfolio optimization setting we can have:

Binary Variables: The core of the mapping involves representing the decision of
whether or not to include a particular asset in the portfolio using binary variables. For
each potential asset i, a binary variable xi is introduced, where $x_i=1$ if asset $i$ is
selected for the portfolio and $x_i=0$ if the asset is not selected.

Objective Function: the standard portfolio optimization problem, particularly the
mean-variance approach introduced by Markowitz, has objectives that fit well into the
quadratic form of a QUBO: in fact we want minimize the risk of the portfolio
(measured by its variance of the portfolio’s return) while maximizing the return. When
we talk about the Objective Function, we’re essentially defining what makes a
portfolio «good» or «bad» in mathematical terms. Think of it as a scoring system. Our
goal is to reward good choices (like aiming for a high return on investment) and
simultaneously penalize bad combinations (such as taking on too much risk). This
formula acts as a balancer, helping us find the best spot between these two
competing goals.

Portfolio risk is typically measured by the variance of the portfolio’s return. This involves the
covariance between the returns of different assets. The covariance term between asset $i$
and asset $j$ is a quadratic term involving $x_i$ and $x_j$. The sum of all such pairwise
covariances (weighted by the investment in each asset) forms a quadratic expression. If we
assume a simplified scenario where $x_i=1$ means a fixed unit of investment in asset $i$,
the risk term in the QUBO would look something like $\sum_{i<j}Q_{ij}x_ix_j$, where $Q_{ij}$
is related to the covariance between asset $i$ and asset $j$. The diagonal terms $Q_{ii]$
can be related to the variance of asset $i$.

Coming to maximising the portfolio return, the expected return of a portfolio is the weighted
sum of the expected returns of individual assets and this is a linear term in the optimization
problem. To incorporate this into a minimization problem (as QUBO is defined), we typically
subtract the expected return from the objective function. This adds a linear term to the
QUBO of the form $\sum_{i=1}^n Q_{ii}x_i$, where $Q_{ii}$ is related to the negative of the
expected return of asset i. By minimizing this term, we effectively maximize the expected
return.

Combining these, a basic objective function for portfolio optimization in a QUBO might aim to
minimize ($\text{Risk } – \lambda * \text{Return}$), where$\lambda$ is a parameter that
balances the trade-off between risk and return. This directly translates to setting the
coefficients $Q_{ij}$ based on covariances and $Q_{ii}$ based on negative expected returns
and $\lambda$.

Constrained Portfolio Optimization

While QUBO stands for «unconstrained», real-world portfolio optimization has constraints.
These are typically handled by adding penalty terms to the QUBO objective function. A large
positive penalty is added if a constraint is violated, making those solutions have a higher
energy (objective function value) and thus less likely to be the minimum. Common
constraints include:

Budget Constraint: a constraint on the total investment amount. In a simplified binary
selection model, this could be a constraint on the number of assets selected, e.g.,
exactly $k$ assets must be chosen ($\sum x_i=k$). This can be converted to a
quadratic penalty term, like $M(\sum x_i−k)^2$, where $M$ is a positive number.
Expanding this term results in quadratic and linear terms that are added to the QUBO
matrix $Q$

Diversification Constraints: constraints to ensure diversification across different asset
classes or sectors (this is sometimes the case for institutional investors). These can
also be formulated as penalty terms. For example, limiting the number of assets from
a specific sector can be encoded quadratically

Conclusion

Transforming a portfolio optimization challenge into its QUBO equivalent enables its
resolution using advanced solvers, such as quantum annealers. These computational tools
operate by minimizing the QUBO objective function to determine the ideal set of binary
variables, which directly correspond to the selected assets for the portfolio. The resulting
output is an optimal or near-optimal portfolio that satisfies the defined objectives and
constraints.
However, the effectiveness of this method relies significantly on the precision with which the
problem’s characteristics are embedded within the QUBO matrix, particularly how effectively
constraints are enforced through appropriately weighted penalty terms. Nonetheless, it’s
important to note that some of the more complex constraints encountered in real-world
finance may prove difficult to accurately represent in a QUBO formulation, potentially making this mdoeling approach less suitable for investors bound by stringent and multifaceted regulations.