A bridge between quantum and classical difficulty in portfolio optimization using the Quantum Approximate Optimization Algorithm

The Quantum Approximate Optimization Algorithm (QAOA) has established itself as the most promising method for solving combinatorial optimization problems on near-term gate-based quantum computers. As the quality of algorithms and hardware has continued to improve, the financial sector has taken notice due to the algorithm's ability to solve a myriad of concrete financial problems. This interest ranges from small hedge funds and quant-shops all the way to multinational banks. Within these financial problems (and other related problems), it is not currently known how classical notions of problem difficulty translate into the quantum setting. I.e, are problems which are more difficult to solve via classical means also more difficult for the QAOA? Answering this question is clearly vital for the larger success of the QAOA and adoption in the mainstream financial sector. In this work, we show how to solve an important financial problem with the QAOA: discrete Markowitz portfolio optimization (MPO). We evaluate the success of the approach and address the parity between classical and quantum difficulty. To do so, we develop a new problem and application-agnostic benchmark: the normalized and complementary Wasserstein distance (NCWD). Using the NCWD, we show that the average quality of portfolios yielded from the QAOA is a function of the number of viable (constraint satisfying) solutions of the classical problem; increasing the total number of viable portfolios deteriorates the average portfolio quality produced the QAOA. Although emerging in the finance setting, this is an important result for the QAOA in general as it is evidence that more difficult discrete problems in the (exhaustive search) classical setting are also more difficult in the quantum setting. We finish by demonstrating deployment of QAOA-based MPO on a trapped ion quantum computer and evaluate its success using the NCWD.