Portfolio optimization with variational quantum eigensolver (VQE)-(1)
To start, we will first talk about the theory and mathematic behind the models in this part. The following is a brief introduction of portfolio optimization problem and how we can solve it with a quantum computer to gain potential computational advantage.
Morden portfolio theory
Portfolio optimization is the process of selecting the combination of assets in an investment portfolio that maximizes returns while minimizing risk. Morden portfolio theory (MPT) is one of the most known mathematic model to complete this task. In MPT, the expected return is estimated with the mean of historical return distribution, and the risk (volatility) is defined as the standard deviation of the same distribution. For an asset with price {pᵢ} for days i=1~N, the return distribution is {rᵢ}, where
The corresponding mean and variance is thus
Note that this is an simple example for one asset, in practice, there will be multiple assets in the pool, and thus μ and σ² for different assets forms a return vector μ and the variance-covariance matrix ∑. The expected return for a portfolio x=[w₁, w₃,…, wₙ], where wᵢ is the weight for iᵗʰ asset, is μᵀx, and the risk is √xᵀ∑x. Now we plot the risk and return for a variety of portfolios.
The red line is the efficient frontier, representing the portfolio with the highest return for a given risk, or the lowest risk for a given return. The goal of portfolio optimization is the find a portfolio on the efficient frontier.
Objective function
There are several ways to maximizes returns while minimizing risk. We introduce 2 of the most common ones here, the first one is maximizing the Sharpe ratio, and the second one, which we will use to solve with a quantum computer, is minimizing a quadratic programming function.
- Sharpe ratio
Sharpe ratio can be understand as the excess return we get for every unit of risk we bear, which is quite reasonable for a maximization.
2. Quadratic programming (QP)
Another way to do the optimization is to minimize the quadratic objective function:
where B is the budget, which is usually 1, and γ is a risk aversion coefficient that determines the willing of an investor to trade the returns off against risks. The larger the γ is, the more risk-averse you are. Note that one can choose a specific γ such that minimizing this quadratic function become equivalent to maximize the Sharpe ratio. For a quantum computer, we will want to work with this QP problem, since we can easily transform it into solving a fully-connected Ising model, which is natively solvable for a quantum computer. More details will be mention later.
Continuous v.s. discretized
We may have different constraints in our portfolios in different scenarios, here we discuss whether the portfolio is continuous or discretized. A continuous portfolios are the most general ones that one can choose any weight for each asset to make up the portfolio , i.e.
On the other hand, discretized portfolio x is a binary string, which you can only choose to own an asset or not, i.e.
where B is the limit that we want exactly B assets chosen in our portfolio. The budget constraint is always needed since we can not compare two portfolios that normalized to different values.
When x is continuous, the solution of the QP has an analytical form, which we simply take the derivative with respect to x equals 0 to find the minimum, and results in
since ∑ is a positive semi-definite matrix, it can be solved in polynomial time with existing classical algorithms. However, when x is discretized, the story is different, this becomes a NP-hard problem, and there is no efficient algorithms to solve it. This is where quantum computing comes in.
Penalty
Now, the problem we are trying to solve here is
However, in order to handle the constraint, we had to introduce a penalty term, or often called the Lagrange multiplier in mathematic context. We rewrite the equation to become a quadratic binary unconstrained optimization (QUBO) problem.
Quantum Computing
The most important thing a quantum computer now can do is minimizing a Hamiltonian which is composed of tensor product of Pauli operators. The reason that people believe quantum computer has potential to solve this kind of QUBO problem is that we can easily transform a component xᵢ∈{0,1} in x into Pauli Z operator by writing xᵢ in terms of zᵢ∈{1,-1}:
where the right hand side is a fully coupled Ising Hamiltonian. The detail calculation process can be found in the appendix of the next post. We thus calculate the ground state of this Hamiltonian with VQE or QAOA. VQE and QAOA are both common variational quantum algorithms that we construct a parameterized quantum circuit as a ansatz, and iterate and update the parameters with classical optimization method in order to minimize the expectation value of the Hamiltonian. After the ansatz is optimized, we expect the probability distribution to concentrate on low energy states, if not the ground state, and we can obtain a high quality solution within a few samplings. For more details, see the nice introduction written by Qiskit.
Although the quantum advantage of these heuristics are still not guaranteed, it is worth trying since the search space of this problem scales exponentially (2ᴺ), and classical computing (in terms of a guaranteed algorithm) will reach it’s limit with even a small problem size (about N=50).
Measurement grouping
In general cases, a Hamiltonian can contain all different kinds of tensor product of Pauli operators that don’t commute with each others. For example,
where X, Y, Z represent the Pauli X, Y ,Z operator respectively. We thus have to construct 3 different circuit that take measurement in different basis (XY, YZ, ZX), and run each circuit multiple times in order to evaluate the expectation value of this Hamiltonian. However, when two operators in a Hamiltonian commutes, we can evaluate them with the same set of measurement outcomes. For an Ising Hamiltonian, all operators commute with each other (Z, ZZ), we thus only need to measure all qubits in Z basis and evaluate each operator with this set of measurements.
An intuitive though will be that we can reduce (F-1)/K proportion of all measurements if there are F out of all K operators that commutes with each other in a Hamiltonian. Unfortunately, life is hard. The amount of measurements also have to increase in order to evaluate these bunch of operators to the same error as we evaluate a single operator, and even worse, the total measurement may even increase due to the contribution of covariance between operators in the same group. We will stop here without discussing the math and provide some resource for those who are interested in this problem.
[1]Pennylane Measurement optimization
[2]Gokhale, Pranav, et al. “Minimizing state preparations in variational quantum eigensolver by partitioning into commuting families.” arXiv preprint arXiv:1907.13623 (2019).
[3]Crawford, Ophelia, et al. “Efficient quantum measurement of Pauli operators in the presence of finite sampling error.” Quantum 5 (2021): 385.
[4]Wecker, Dave, Matthew B. Hastings, and Matthias Troyer. “Progress towards practical quantum variational algorithms.” Physical Review A 92.4 (2015): 042303.
In the next part, we will implement an example solving discrete portfolio optimization with VQEs via pennylane.
