Will quantum computers one day manage international reserves? (Part 3)

The financial sector is an industry that historically relies heavily on computing – from the simple keeping of cash flow records to sophisticated models trying to predict future trends in financial markets. In our December 2021 and March 2022 blog articles, we discussed a new computing tool, the quantum computer, which might find applications in finance. We established that most theoretical proposals, whether for measuring risk or solving systems of linear equations, are not very suitable for use in practice. This is due not to shortcomings in the algorithms themselves, but to the still low level of development of quantum processors, even though rapid progress has been made. Regardless of these teething problems, we concluded that quantum computers might already be useful for handling “almost practical” problems in one particular area – quadratic unconstrained binary optimisation, which can be used to find the optimal portfolio. This conclusion motivated further research into possible applications of quantum optimisation algorithms in banking in general, in our case relating specifically to international reserves management.

In this article, we will first look at the classical portfolio optimisation technique and then describe some quantum algorithms intended for solving this problem. We will go on to deploy those techniques in the search for the optimal international reserves currency structure. Finally, we will look at the future prospects for quantum optimisation in the financial world. However, we should note that the results we obtained have not been put into practice, as our problem is of a research and educational nature only. The process of choosing the currency composition of international reserves is a complex problem involving a large number of expert inputs and certainly cannot rely solely on the purely technical perspective of classical or quantum algorithms.

Published in Working Paper 1/2023

How to find the optimal portfolio?

Before we begin to describe quantum optimisation techniques, we will briefly discuss portfolio optimisation itself. In 1952, Harry Markowitz designed a method based on quadratic programming [1]. Markowitz sought to find the optimal trade-off between the return, as represented by the weighted sum of the returns on the individual assets in a portfolio, and the risk stemming from the volatility of the returns and their correlation.^[1] The risk term is quadratic, hence quadratic programming was applied. Although the Markowitz technique introduces a number of constraints on the input data,^[2] it has become the standard tool for seeking the optimal portfolio structure.

However, a disadvantage of quadratic programming in the general case is its high computational complexity [3].^[3] Although this worst case is relatively rare in practice, it serves as motivation to seek techniques that might reduce it effectively. Moreover, “high-frequency” traders will certainly leverage any additional speedup of the calculations, even in favourable cases. As a result, various studies have attempted to answer the question of whether quantum computers might also be used for Markowitz portfolio optimisation [4, 5, 6, 7].

However, the use of quantum computing entails a need to convert the optimisation problem into binary form. This involves expressing the weight of an asset as a string of binary variables, i.e. ones taking values of either 1 or 0. If we want to obtain sufficient accuracy, the number of variables will be large. In addition, the binary form of quadratic programming is very demanding on computational resources.^[4] However, the performance of quantum computers should be such that even this “artificial increase” in the complexity of the problem will ultimately lead to the optimal portfolio structure being found faster than under the classical approach.

How will quantum computers help?

We can now proceed to describe the quantum algorithms whose capabilities we assessed. The first set of quantum optimisation algorithms consists of variational algorithms. The common feature of these algorithms is that they try to convert the optimisation problem into a simulation of a quantum system. After all, this is the purpose for which the quantum computer was designed. There are huge numbers of quantum systems in nature. However, the one most similar to quadratic binary optimisation is spin glass, a special class of magnetic material lying on the borderline between ferromagnets (e.g. iron) and paramagnets (e.g. copper).^[5]

Every quantum system, including spin glass, is described by a Hamiltonian, which tells us which energy levels the system can be in. When studying a quantum system, we are primarily interested in the state with the lowest energy (the ground state). Here we can already clearly see a link to the optimisation problem – the ground state is linked to the optimal solution. Therefore, once we assign a quantum system to our optimisation problem, we can simulate it and find the optimal solution to the problem.

The simulation itself can be carried out using several different approaches. The Quantum Approximate Optimisation Algorithm (QAOA) [8] and the Variational Quantum Eigensolver (VQE) [9] can be run on universal quantum computers such as IBM Quantum^TM [10]. Whereas the QAOA is designed solely for spin glass simulation, the VQE is more general and lets us work with other quantum systems. However, both algorithms are iterative and combine the quantum approach (for simulating the quantum system) with the classical approach (for calculating the energy of the quantum states)

Besides universal quantum computers, spin glass simulation can be performed on quantum annealers, which are offered by the Canadian company D-Wave Systems [11]. Quantum annealers are single-purpose quantum computers that in essence physically implement spin glass simulation. They can also be combined with classical algorithms (hybrid solvers). In this case, the problem is subdivided into smaller ones, which are solved in “quantum” fashion and then combined back in the “classical” way. Alternatively, the output of a classical algorithm can be used as the input into a quantum one that will make it more accurate. A detailed description of the QAOA and the theoretical foundations of variational algorithms can be found in our previous blog article.

A completely different approach to solving quadratic binary optimisation problems is based on Grover’s algorithm [12, 13]. Originally, this algorithm was designed for rapid search in unstructured databases using a quantum computer.^[6] In the proposed modification, the database is replaced by optimised function values encoded into a quantum superposition [14]. From these, the lowest possible value is selected using a series of quantum operations and the optimal solution is obtained by measuring the output of the quantum computer. However, we should add that the quantum computation is again iterative, with the optimised function value improving with each iteration.

Let’s now look at the theoretical speedup which the algorithms described above offer by comparison with the classical approach. Variational algorithms are heuristics, which means they provide no guarantee of finding the optimal solution, and they have been rigorously proven to provide no speedup. Nevertheless, a number of studies suggest that they perform better than classical algorithms in solving some specific problems [7, 15, 16, 17]. On the other hand, the approach based on Grover’s algorithm has been theoretically proven to provide quadratic speedup.  Putting it simply, instead of 10,000 operations in the classical case, just 100 are sufficient in the quantum case. However, variational algorithms have the advantage of lower susceptibility to noise present in the quantum processors. This is, however, a problem for Grover’s algorithm. In addition, Grover’s algorithm requires more qubits than variational algorithms to solve a given problem (for example, variational algorithms need 6 qubits for 6 variables, while Grover’s approach required 13 qubits in our case).

Which particular problem did we solve?

We used the algorithms described above to find the optimal currency composition of the CNB’s international reserves. Our aim was to maximise the return on the reserves in koruna terms while minimising its volatility. Moreover, our problem involved dynamic portfolio optimisation. In other words, we looked for the optimal portfolio composition in different time periods. In our exercise, these periods were defined by the ends of major global crises, which usually bring about a change in the market regime and create a “new normal”. For the purposes of our problem, we chose the following crises: the Great Recession of 2007–2009, the euro area debt crisis of 2011–2013 and the Covid crisis of 2020 and 2021. Besides maximisation of the return and minimisation of its volatility, the dynamic form of the optimisation problem required another optimisation criterion – minimisation of the transaction costs arising from the change in the currency composition between periods. All the currencies that currently feature in the international reserves – AUD, CAD, CNY, EUR, GBP, JPY, SEK, USD and gold – were included in the optimisation.

The binary form of the problem had a total of 378 binary variables.^[7] As not every quantum algorithm can work with such a large number of variables, we also created a simpler version involving only one period (the Great Recession) but all the above nine currencies. For the purposes of testing IBM Quantum^TM, we had to simplify the problem further to just three currencies (AUD, CAD and gold). We also lowered the requirements regarding the accuracy of the currency weights. The number of binary variables thus decreased to 90 in the first case and just 6 in the second case (the IBM processors we used had only seven quantum bits each).

To compare the algorithms’ ability to find the optimal solution to the problem and the speed of finding that solution, we first performed the optimisation using the classical continuous gradient method [18] implemented in MS Excel.^[8] We then solved the binary form of the problem using classical exact and heuristic algorithms. Our representative exact algorithm is the branch and bound method [19], which tries to search the space of possible solutions to a problem by eliminating solutions where the objective function value is worse than the best one found so far.^[9] This approach saves time, as it is not necessary to test all the possible solutions to the problem.^[10] As regards heuristic algorithms based on random search, we used simulated annealing [20], a method based on the simulation of the cooling of a material, and genetic optimisation [21], which is based on the simulation of evolutionary processes. All this provided us with a benchmark for assessing the capabilities of the quantum algorithms.

What did we find?

Let’s start with the results of the algorithms designed for universal quantum computers. All the calculations were performed on IBM Quantum^TM. The good news is that both the VQE and the QAOA were able to find the solution to our problem. However, given the small number of qubits (we used the processors code-named Nairobi and Oslo, which have only seven qubits each), we were only able to test a very simplified version of the problem with three currencies. The solver based on Grover’s algorithm could only be run on a simulator, as it would require 13 qubits in our case. However, the simulated calculation produced the optimal solution. In principle, therefore, this solver can be applied. We also solved the three-currency problem using the D-Wave annealer in both purely quantum and hybrid form. This approach was also able to find the optimum.

In terms of run time, however, the best method was classical simulated annealing, followed by the D-Wave annealer, genetic optimisation, the MS Excel solver and the branch and bound method. The hybrid D-Wave solver finished second to last. The VQE and the QAOA came last. However, the solution to a problem with only six binary variables has hardly enough information value to enable us to assess the algorithms’ behaviour in the “practical dimensions” of problems. The algorithms for IBM-style universal quantum computers can thus be better tested once processors with more qubits become available.

Despite the limitations imposed by the imperfections of universal quantum processors, the quantum world can still help us with portfolio optimisation, as quantum annealers can already work with even several hundred binary variables. We thus tested the D-Wave annealer on the problem with one time period but nine currencies. The quantum annealer by itself was relatively far from the optimum, but when used in combination with classical algorithms (i.e. in hybrid form) it came very close, even outperforming classical simulated annealing, genetic optimisation and the branch and bound method. In terms of run time, though, the MS Excel solver was significantly better (about 13 times faster).

In the case of the “full” problem (the one with three time periods), we compared the outputs of MS Excel, the branch and bound method, simulated annealing and the D-Wave hybrid solver, as the other algorithms were “extremely” far from the optimum. Again, MS Excel offered a better solution than D-Wave in less time. However, the difference between the solutions obtained using D-Wave and the Excel solver was not significant. The time advantage of Excel also decreased – it was now “only” three times faster. Simulated annealing remained a long way behind, with a run time almost 1,000 times longer than D-Wave and an offered solution far from the optimum. The branch and bound method produced roughly the same results as D-Wave, but at the cost of a several-hour run time, whereas D-Wave managed to find a solution in seconds.

What are the prospects for quantum portfolio optimisation?

Overall, it may seem that quantum computers have no place in portfolio optimisation at the moment, as we can easily make do with MS Excel, which is available on any office computer. However, this conclusion would be too categorical.

First, the above results show that the gap between the classical and quantum (or hybrid) approaches closes as the dimension of the problem increases. In the case of a very simple problem with six variables, the hybrid solver is at the back of the field. However, the performance of this solver increases as the number of variables rises.

Second, we need to take into account the above-mentioned fact that “binarising” an optimisation problem makes it far more difficult to solve. However, if we compare the algorithms purely in terms of binary optimisation, the hybrid approach is the clear winner. Despite having no direct practical applications, similarly complex problems as the one we solved may serve as good tests for newly developed quantum computers, be they universal machines or single-purpose annealers.

Third, although quantum annealers are much more advanced than universal quantum computers, they, too, are largely experimental devices. For this reason, we will keep track of their development and carry out more tests at some point in the future.

Overall, classical computers are sufficient for our purposes at the CNB for the time being, at least as far as international reserves management is concerned. However, commercial banks and other financial institutions are interested in quantum computing, so we need to have a good understanding of this new technology and be aware of its capabilities and limitations.

References:

• [1] MARKOWITZ, H. (1952): “Portfolio Selection.” Journal of Finance, 7(1):77-91.
• [2] MANDELBROT, B (1963). “New Methods in Statistical Economics.” Journal of Political Economy
  71(5):421-
• [3] VAVASIS, S. A. (1990): “Quadratic Programming Is in NP.” Information Processing Letters, 36 (2):73-77.
• [4] ELSOKKARY, N., F. S. KHAN, D. L. TORRE, T. S. HUMBLE, AND J. GOTTLIEB (2017): “Financial Portfolio Management using D-Wave Quantum Optimizer: The Case of Abu Dhabi Securities Exchange.” IEEE High-performance Extreme Computing 2017 Conference Proceedings.
• [5] ROSENBERG, G., P. HAGHNEGAHDAR, P. GODDARD, P. CARR, K. WU, AND M. L. DE PRADO (2016): “Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer.” IEEE Journal of Selected Topics in Signal Processing, 10(6):1053-1060.
• [6] PALMER, S., S. SAHIN, R. HERNÁNDEZ, S. MUGEL, AND R. ORÚS (2021): “Quantum Portfolio Optimization with Investment Bands and Target Volatility.” arXiv:2106.06735v3 [q-fin.PM].
• [7] MUGEL, S., C. KUCHKOVSKY, E. SÁNCHEZ, S. FERNÁNDEZ-LORENZO, J. LUIS-HITA, E. LIZASO, AND R. ORÚS (2022): “Dynamic Portfolio Optimization with Real Datasets using Quantum Processors and Quantum-Inspired Tensor Networks.” Physical Review Research, 4(1):013006.
• [8] FARHI, E., J. GOLDSTONE, AND S. GUTMANN (2014): “A Quantum Approximate Optimization Algorithm.” arXiv:1411.4028v1 [quant-ph].
• [9] PERUZZO, A., J. MCCLEAN, P. SHADBOLT, M.-H. YUNG, X.-Q. ZHOU, P. J. LOVE, A. ASPURU-GUZIK, AND J. L. O’BRIEN (2014): “A Variational Eigenvalue Solver on a Photonic Quantum Processor.” Nature Communications, 5(5):4213.
• [10] https://quantum-computing.ibm.com/
• [11] https://www.dwavesys.com/
• [12] GROVER, L. K. (1996): “A Fast Quantum Mechanical Algorithm for Database Search.” Proceedings, 28th Annual ACM Symposium on the Theory of Computing (STOC), 212-219.
• [13] GROVER, L. K. (2001): “From Schrödinger’s Equation to the Quantum Search Algorithm.” Pramana: Journal of Physics, 56(2):333-348.
• [14] GILLIAM, A., S. WOERNER, AND C. GONCIULEA (2021): “Grover Adaptive Search for Constrained Polynomial Binary Optimization.” Quantum, 5:428.
• [15] DING, Y., J. GONZALEZ-CONDE, L. LAMATA, J. D. MARTÍN-GUERRERO, E. LIZASO, S. MUGEL, X. CHEN, R. ORÚS, E. SOLANO, AND M. SANZ (2019): “Towards Prediction of Financial Crashes with a D-Wave Quantum Computer.” arXiv:1904.05808v3 [quant-ph].
• [16] HARWOOD, S., C. GAMBELLA, D. TRENEV, A. SIMONETTO, D. BERNAL, AND D. GREENBERG (2021): “Formulating and Solving Routing Problems on Quantum Computers.” IEEE Transactions on Quantum Engineering, 2:1-
• [17] EGGER, D. J., J. MAREČEK, AND S. WOERNER (2021): “Warm-Starting Quantum Optimization.” Quantum, 5:479.
• [18] LEMARÉCHAL, C. (2012): “Cauchy and the Gradient Method.” Documenta Mathematica, Extra Vol. Optimization Stories:251-254.
• [19] LAND, A. H. AND A. G. DOIG (1960): “An Automatic Method of Solving Discrete Programming Problems.” Econometrica, 28(3):497–520.
• [20] CORANA, A., M. MARCHESI, C. MARTINI, AND S. RIDELLA (1987): “Minimizing Multimodal Functions of Continuous Variables with the Simulated Annealing Algorithm.” ACM Transactions on Mathematical Software, 13(3):262-280.
• [21] KATOCH, S., S. S. CHAUHAN, AND V. KUMAR (2021): “A Review on Genetic Algorithm: Past, Present, and Future.” Springer: Multimedia Tools and Applications, 50(5):8091-8126.

Keywords

Foreign exchange reserves, portfolio optimization, quadratic unconstrained binary optimization, quantum computing

JEL Classification

C61, C63, G11

^[1] Mathematically speaking, the problem is -r^Tw + λw^TCw → MIN , where w are asset weights, r are the expected returns, C is the covariance matrix and λ > 0 is risk appetite.

^[2] It is assumed, for example, that asset returns are normally distributed. This assumption was criticised by the renowned mathematician Benoit Mandelbrot [2].

^[3] In general, quadratic programming is an NP-complete problem. The number of operations required increases exponentially with the number of variables.

^[4] A quadratic binary programming problem is always NP-complete.

^[5] A ferromagnet remains magnetised when removed from a magnetic field, whereas a paramagnet loses its magnetisation exponentially quickly. The magnetisation of spin glass decreases linearly.

^[6] An unstructured database has no index. This means that when searching the database, we have to go through its items one by one. A good analogy of an unstructured database is a pile of unlinked documents in which we are searching for one particular document by, for example, its folder number.

^[7] Let’s assume we go through the solutions one by one (the brute force method). Furthermore, let’s consider that it takes one nanosecond (corresponding to a processor clock speed of roughly 1 GHz) to verify whether a solution is better than the best one found so far. It will then take 10⁹⁹ years to find the optimum. The age of the universe is only 13.77x10⁹ years. It is therefore clear that to solve such problems, we need sophisticated exact algorithms or heuristics, whether classical or quantum.

^[8] You can try this yourself, as it is a commonly used “solver” in Excel: Data => Analysis => Solver.

^[9] We used the implementation of the branch and bound method in the IBM CPLEX Studio optimisation software tool, which is available free of charge for solving problems with fewer than 1,000 variables.

^[10] However, the branch and bound method may degenerate into the brute force method in the worst case.