isaacdevlugt
commented
2 years ago Thank you for your submission! There's still time to populate your submission with code, presentation material, etc. Please make any final adjustments before the deadline tonight at 17h00 EST!
Good luck!
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 the first phase of 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.
In the second phase, to tackle the computational issue of QAOA based on PennyLane, we implement it with AWS Bracket SV1 simulator that supports parallel circuit execution. Unfortunately, the program still runs very slowly and the AWS server crashes when the number of assets is bigger than 17. Therefore, we turn our attention to improving the accuracy of the QAOA implemented with Qiskit. We employ a variant of QAOA based on Conditional Value-at-Risk (CVaR) proposed in [1]. The key point of this method is to replace the original cost function of QAOA with the CVaR expectation value which provides a more natural and efficient way to find the ground state of the diagonal problem Hamiltonian for the case of portfolio optimization. The results of our experiments show that this method has provided for QAOA 12.5% higher accuracy and up to 41% shorter running time. The details of the project can be found in our final presentation. In the current noisy intermediate-scale quantum era, the QAOA has great potential to solve a wide range of difficult real-world business problems such as portfolio optimization. We hope our work constitutes a step in this direction.
[1] Barkoutsos, P. K., et al. “Improving Variational Quantum Optimization using CVaR”.
Presentation:
Please refer to our final presentation
Source code:
Please refer to our GitHub repo
Which challenges/prizes would you like to submit your project for?
IBM Qiskit Challenge Quantum Finance Challenge Hybrid Algorithms Challenge