Portfolio Optimization Based on QAOA[AWS Power Up]

Team Name:

cyx

Project Description:

Portfolio optimization is one of the most popular topics in the area of finance. The goal of it is to find the optimal combination of different assets among all available assets so that the expected return is maximized and the financial lost is minimized. Portfolio optimization can be mathematically formulated as a combinatorial optimization problem subject to certain constraints. There exist a few classical methods (e.g. Minimum Eigen solver) to solve this type of problems. But these methods usually have the exponential time complexity and suffer from the computational bottleneck when the problem size is very large. Unfortunately, portfolio optimization problems in the real word usually involve a large number of assets (e.g. 1000 assets) and we have to select an optimal combination of a certain number of assets from them. It would take a very long time (e.g. a few weeks, a few months) to solve these problems, which is impractical in the real-world business.

In this project, we aim to employ the well-known quantum approximate optimization algorithm (QAOA) to deal with the computational issue of portfolio optimization problems and attempt to find the quantum advantage over classical methods. We perform three experiments for this project. In the first two experiments, we implement the QAOA algorithm with Qiskit and PennyLane respectively. In the first experiment, we use the ‘qasm_simulator’and ‘aer_simulator_statevector_gpu’backends for the CPU and GPU simulation respectively. In the second experiment, we choose the PennyLane’s built-in backend ‘default.qubit’that supports more efficient differentiation methods such as back-propagation and adjoint method. In the last experiment, we select NumPyMinimumEigensolver as the benchmark method to compare with the QAOA. To evaluate how these models scale up with the problem size, we choose assets numbers ranging from 2 to 28 in each experiment. To make a fair comparison, we use the same server environment and same data across all experiments.

The first-phase results of our project demonstrate that the QAOA implemented with Qiskit performs better than PennyLane in terms of running time, although Qiskit simulators only support parameter-shift rule or finite difference methods for the gradient computation. The QAOA implemented by either CPU or GPU Qiskit simulators can achieve the quantum advantage over the classical method based on Numpy when the number of assets reaches 24. In particular, the QAOA based on the GPU Qiskit simulator results in a 12x speed-up over the numpy method. In spite of the advantage in running time, QAOA implemented with Qiskit has worse performance than PennyLane in terms of accuracy which is defined as the number of optimal solutions found over the total number of optimal solutions. Our results show that the Qiskit version of QAOA gets an accuracy of 0.625 while the PennyLane version achieves 0.9375. The details of the project can be found in our draft presentation.

Source code:

Please refer to our GitHub repo here

Resource Estimate:

In the next phase, if awarded AWS power-up, we would implement QAOA with PennyLane on AWS Bracket and see if it could solve the problem with number of assets more than 17 with higher speed and achieve a quantum advantage over the classical method. For example, we could use the Amazon Braket simulator SV1 via PennyLane-Braket plugin and take advantage of its capability of computing gradients in parallel. We could also try using QPU devices provided by Amazon Braket and see if the accuracy of the QAOA based on PennyLane would be affected.

XanaduAI / QHack2022