Toward Prediction of Financial Crashes with a D-Wave Quantum Annealer

Noname manuscript No. (will be inserted by the editor) Towards Prediction of Financial Crashes with a D-Wave Quantum Computer Yongcheng Ding 1,2 ·Javier Gonzalez-Conde 2,3 ·Lucas Lamata 2,4 ·Jos´e D. Mart´ın-Guerrero 5·Enrique Lizaso 6·Samuel Mugel 6·Xi Chen 2,1 ·Rom´an Or´us 6,7,8 · Enrique Solano 1,2,8,10 ·Mikel Sanz 2,8,9 Received: date / Accepted: date Abstract Prediction of financial crashes in a complex financial network is known to be an NP-hard problem, which means that no known algorithm can guarantee to find optimal solutions efficiently. We experimentally explore a novel approach to this problem by using a D-Wave quantum computer, benchmarking its performance for attaining financial equilibrium. To be specific, the equilibrium condition of a nonlinear financial model is embedded into a higher-order unconstrained binary optimization (HUBO) problem, which is then transformed to a spin-1/2 Hamiltonian with at most two-qubit interactions. The problem is thus equivalent to finding the ground state of an interacting spin Hamiltonian, which can be approximated with a quantum annealer. The size of the simulation is mainly constrained by the necessity of a large quantity of physical qubits representing a logical qubit with the correct connectivity. Our experiment paves the way to codify this quantitative macroeconomics problem in quantum computers. Keywords Quantum Information ·Physical Systems ·Quantum computation ·Financial networks · Adiabatic quantum optimization Mikel Sanz E-mail: mik[email protected] 1International Center of Quantum Artificial Intelligence for Science and Technology (QuArtist) and Department of Physics, Shanghai University, 200444 Shanghai, China 2Department of Physical Chemistry, University of the Basque Country UPV/EHU, Apartado 644, 48080 Bilbao, Spain 3Quantum Mads, Uribitarte Kalea 6, 48001 Bilbao, Spain 4Departamento de F´ısica At´omica, Molecular y Nuclear, Universidad de Sevilla, 41080 Sevilla, Spain 5IDAL, Electronic Engineering Department, University of Valencia, Avgda. Universitat s/n, 46100 Burjassot, Valencia, Spain 6Multiverse Computing, Pio Baroja 37, 20008 San Sebasti´an, Spain 7Donostia International Physics Center, Paseo Manuel de Lardizabal 4, 20018 San Sebasti´an, Spain 8IKERBASQUE, Basque Foundation for Science, Plaza Euskadi 5, 48009 Bilbao, Spain 9IQM, Nymphenburgerstr. 86, 80636 Munich, Germany 10Kipu Quantum, Kurwenalstrasse 1, 80804 Munich, Germany arXiv:1904.05808v3 [quant-ph] 22 Jun 2021 2 Short form of author list 1 Introduction Economics is a complex science in which the agents’ psychology plays an essential role that is often hardly grasped by mathematical models. However, economists do not relinquish to try to predict market behavior employing sophisticate models, leading to the field of quantitative finance. Following this idea, quantitative finance and economics emerged. They were applied to understand the evolution of financial markets and economies, as well as to forecast their possible future. A realistic question in risk management is: would there be a drastic drop in the market values if the prices of assets suffer some small perturbation? The cross-holdings and nonlinear character of financial network dynamics will cause chain reactions, implying that sudden drops of a market value might affect other nodes in the network resulting in a financial crisis. Presently, the prediction of crashes is mainly performed by studying previous cases in history and comparing with the current configuration [1,2,3,4,5,6]. While this empirical approach has been succesful [7], the economic environment is constantly evolving. Hence, we cannot limit ourselves to predicting economic disasters which are qualitatively similar to past events. Therefore, ab initio simulations of financial networks will become essential for avoiding financial crises. This problem was recently shown to be NP-Hard [8]. Therefore, given the current standpoint on complexity theory, this problem is not expected to be efficiently solvable in a classical computer. Indeed, given the global knowledge of a financial network, the time to compute the consequences of a perturbation would by far exceed the age of the universe. An alternative approach to this problem was presented in Refs. [9,10], where they suggest a possible improvement of the efficiency to tackle this type of problems by using quantum computing. In particular, a mathematically identical problem is simulated and the corresponding result measured [11,12,13,14]. Specifically, it was shown that obtaining the equilibrium configuration of a financial network is equivalent to solving a higher-order unconstrained binary optimization (HUBO) problem, which should be feasible for a quantum annealer allowing for multi-qubit interactions. Unfortunately, this hardware has not been realized yet, as state-of-the-art quantum annealers are restricted to two-qubit interactions [15]. A possible workaround, which comes at the price of introducing ancillary qubits, is to find an effective Hamiltonian with the same low-energy subspace and two-qubit interactions at most. This leaves us with the problem of solving a quadratic unconstrained binary optimization (QUBO) problem whose optimum encodes the equilibrium configuration of a financial network. This problem can be addressed employing a quantum annealer. The D- Wave 2000Q quantum annealer, equipped with a Chimera architecture, requires a large quantity of physical qubits to obtain the desired connectivity and limits the number of institutions and assets considered. An analysis of the changes experienced by the financial network to reach its equilibrium configuration will tell whether a crash has occurred. In this paper, we experimentally benchmark the study presented in Refs. [9,10]. Specifically, we compute the equilibrium configuration of a financial network after perturbation with a D-Wave 2000Q quantum annealer, and compare the result to alternative methods. Although the D-Wave machine has been successfully used to solve problems in engineering [16], cryptography [17], biology [18], and quantitative finance [19,20] among others, it is the first time that quantum annealing is applied to solve a problem of macroeconomics. This should attract more attention from the finance and economic disciplines towards quantum computing [21,22,23,24,25,26,27], as well as enlarge the amount of feasible problems for quantum annealers. The contents are organized as follows: in Sec. 2, we introduce the model of financial network that will be considered. Sec. 3 reviews the quantum annealing algorithm to find financial equilibrium. Sec. 4 experimentally proves the validity of the scheme by finding the financial equilibrium of a random network of the largest implementable size with a D-Wave 2000Q quantum annealer; for this network, we also show experimentally how the scheme allows to compute the financial equilibrium. Sec. 5 analyzes the achieved results and discusses further possible improvements. The conclusions drawn from the work are shown in Sec. 6. Towards Prediction of Financial Crashes with a D-Wave Quantum Computer 3 · · ·· · · Fig. 1 Example of a financial network: the yellow nodes and green nodes denote institutions and assets, respectively. Links denote ownerships and cross-holdings, described by the ownership matrices Dand C, respectively. Diagonal matrix ˜ Crepresents the self-ownership of institutions, which would be plotted as self-loops in the graph representation. The equity value Viof institution iis defined by summing up its ownership of all assets and cross-holdings. 2 Financial network model A nonlinear network model for financial markets is proposed in Ref. [9]. It is made up of ninstitutions and massets, and aims at representing the market values of institutions by mapping it onto a network, as shown in Fig. 1. We codify the prices of the massets by an m−dimensional vector ~p ∈Rm, where the element pk represents the price of asset k. Moreover, an n×mownership matrix Dcan be defined such that the element Dik ≥0 corresponds to the percentage of asset kowned by institution i. There is also an n×nownership matrix Cthat describes the cross-holdings and self-ownerships between institutions. The coefficients Cij denote the percentage of institution jowned by institution i. By considering all self-ownerships (i.e., the diagonal elements) from Cone forms a new diagonal matrix ˜ Cwhich represents the self-ownership only, such that matrix C=C − ˜ Ccodifies all cross-holdings. The equity value Viof institution iis defined by summing up its ownership of all assets and cross-holdings, Vi=ΣkDikpk+ΣjCij Vj. One thus obtains a matrix equation ~ V=D~p +C~ V, where equity value vector ~ V∈Rnis an n−dimensional vector. Accordingly, the market value is the equity value rescaled with its self-ownership, resulting in the n−dimensional market value vector ~v =˜ C~ V. The solution to the linear matrix equation thus reads ~v =˜ C(I−C)−1D~p. (1) We introduce the nonlinear effect of panic in the model via a Heaviside-theta function Θ; if the market value vidrops below the critical value vi c,failure of institution ioccurs and its equity value drops by βi(~p) which is governed by the price vector of assets. Once we define the failure vector ~ b(~v, ~p) = βi(~p)(1−Θ(~v−~vc)), the market value vector with nonlinearity can be written as ~v =˜ C(I−C)−1(D~p −~ b(~v, ~p)).(2) Mathematically, it is the nonlinearity of ~ b(~v, ~p) which makes financial networks so hard to be predicted. This drop may cause an institution’s value to crash, a behavior which can infect other nodes in the network. Under our definition, a financial crash happens when, after a perturbation in the assets price, the market value of an institution considering the nonlinear term is lower than those pre-perturbation prices calculated with the linear model. 4 Short form of author list 3 Quantum annealing algorithm As proposed in Ref. [9] finding financial equilibrium can be represented as the minimization of an objective function, which is equivalent to finding the ground state of a classical spin Hamiltonian. By squaring Eq. (2), we obtain an objective function that meets its minimum value when the market value state is set to be the equilibrium state (3) Thus, our task is now to find the ~v that minimizes Obj(~v) for a given financial network. Next, we need to deal with the nonlinear terms (modeling failure) of the objective function. The reason is that once the objective function is transformed to a spin-1/2 Hamiltonian, it should ideally be made of polynomial terms only, due to the limitations of quantum annealers. Thus, one expands the failure terms with Heaviside-theta functions in terms of polynomials. This expansion is not unique, and here we choose the Legendre expansion [9], Θ(x) = 1 2+∞ X l=1 (Pl−1(0) + Pl+1(0))Pl(x),(4) in the domain [−1,1], with Pl(x) to be the l-th Legendre polynomial. By setting x= (vi−vc i)/vi max, Eq. (4) enables us to expand Θ(vi−vc i) in the range of vi∈[0, vi max]. Using this expansion as an example, we take the approximation bi(vi, ~p)≈βi(~p) 1 2− r X l=0 Γl2l l X k=0 l kl+k−1 2 l¯vk i!(5) where Γl=√π 2Γ(2−l 2)Γ(3+l 2)and ¯vi=vi−vc i vi max .The polynomial expansion removes the discontinuity while maintaining the strong nonlinearity of the network. We now encode the continuous variables viwith classical bits. This will allow rewriting the resulting objective function in digital form. The expansion is straightforward, and reads vi=P∞ α=−∞ xi,α2α. However, due to the limited resources in real-world devices, one must truncate this expansion, i.e., vi≈Pq α=−qxi,α2α, where xi,α are classical bits with binary values 0 or 1. In this way, the market value of institution iis encoded with 2q+ 1 classical bits. The maximal market value vmax iis given by Pq α=−q2α. Considering (vi−vc i)k=Pk h=0(−1)hk hvk−h i(vc i)hand vn i=Pm0+...+mp=nn m0,...,mpQmα6=0 0≤α≤p2αmαxi,α, the resulting objective function is a polynomial of binary variables xi,α of degree 2r. ˆ H=X i  q X α=−q xi,α2α−γi+X j ¯ Cijbj(xj,α, ~p)  2 (6) with γi=Pj¯ Cij PkDjkpkand ¯ Cij =˜ Cii(I−C)−1 ij . To express it as a spin-1/2 Hamiltonian, we replace the binary variables xi,α by qubit operators ˆxi,α with eigenvalues 0 and 1, i.e., ˆxi,α|0i= 0, ˆxi,α|1i=|1i. The Pauli-zoperator satisfies ˆxi,α = (1 + ˆσz i,α)/2, and therefore the Hamiltonian reads ˆ H= Poly2r(ˆσz i,α),(7) which is equivalent to our objective function but written with Pauli matrices. This Hamiltonian includes all types of multi-spin interactions, up to 2r-body terms. Towards Prediction of Financial Crashes with a D-Wave Quantum Computer 5 ˆσz 1 ˆσz 2 ˆσz 3 ˆσz 4 ˆσz 1,a ˆσz 2,a ˆσz 3,a ˆσz 4,a Ja J Fig. 2 Recast of quantum Hamiltonian with k-qubit interactions into a modified, effective Hamiltonian with the same lowenergy spectrum with two-qubit interactions at most. We illustrate the particular case of a k= 4-qubit interactions, which requieres the introduction of 4 ancilla qubits to obtain the effective Hamiltonian. The Hamiltonian obtained in Eq. (7) is appropriate for a quantum annealer that allows many-qubit interactions. However, state-of-the-art quantum annealers only accept inputs with at most two-qubit interactions. Finding the ground state of a spin-1/2 Hamiltonian, as the one obtained in Eq. (7), is equivalent to solving a Quadratic Unconstrained Binary Optimization (QUBO) problem, which is the input of the quantum annealer. Thus, we should recast our quantum Hamiltonian into a modified, effective Hamiltonian with at most two-qubit interactions. Some protocols achieving exactly this are proposed in Refs. [28,29,30,31,32,33, 34], in particular we base our protocol in Ref. [34], where kancilla qubits are introduced to implement an effective k-qubit interaction. Suppose that there is a k-qubit interaction term ˆ Hk=JkΠk i=1σz iwith the same low-energy spectrum of another Hamiltonian term ˜ Hkwith at most two-qubit interactions. We can express ˜ Hkwith klogical qubits and kextra ancilla qubits as ˜ Hk=J k X i=2 i−1 X j=1 ˆσz iˆσz j+h k X i=1 ˆσz i +Ja k X i=1 k X j=1 ˆσz iˆσz j,a + k X i=1 ha iˆσz i,a,(8) as represented in Fig. 2. This two-qubit Hamiltonian has the same low-energy spectrum than ˆ Hkwhen J,Ja,hand ha iare set to some appropriate values. As Ref. [34] suggested, this can be achieved once qi= (−1)k−i+1Jk+q0,h=−Ja+q0,ha i=−Ja(2i−k) + qiand J=Ja, with any q0that satisfies |Jk|  q0< Jaand |Jk|  Ja−q0< Ja. These conditions can be relaxed to |Jk|< q0< Jaand |Jk|< Ja−q0< Jaif one aims at having the same ground state only, instead of the whole low-energy sector. 4 Implementation in a D-Wave 2000Q quantum annealer Once shown that it is possible to recast the problem of finding financial equilibrium into a language that is amenable to quantum annealers, this section deals with its implementation using a state-of-the-art quantum annealer, namely, the D-Wave 2000Q. This quantum annealer consists of 2048 qubits connected according to the Chimera graph topology (see Fig. 3). It is designed to solve embedded Ising problems or QUBO problems. Two simulations were produced: 6 Short form of author list 0 1 2 3 4 5 6 7 Fig. 3 Chimera graph topology implemented by the D-Wave 2000Q quantum annealer. The 2048 qubits are partitioned into subgraphs of 8 qubits. The connection between subgraphs is sparse, in each of these subgraphs there are two sets of four qubits; each qubit connects to all qubits in the other set but to none in its own, forming a K4,4bipartite graph. 1. A financial network without failure term, which is simple to solve on a classical computer in order to benchmark the performance of the quantum processor. 2. A financial network with the inherently nonlinear risk of failure. We will perturb the asset price vector in this network to compute the new equilibrium configuration using the quantum annealing algorithm. We initially generate a financial network with 10 institutions and 15 assets. To demonstrate the algorithm, we randomize the ownership matrix Dwith a Dirichlet distribution that satisfies Pn i=1 Dij = 1, where Dij are random variables. The cross-holding matrix Cis generated in a similar way but with a constraint that all diagonal elements should be larger than 0.5, ensuring that all institutions can make decisions according to their own wills. Thus, we randomize ˜ Cii between 0.5 and 1 and randomize Pn i=1 Cij = 1−˜ Cjj with a rescaled Dirichlet distribution. The price vector ~p is also random, with pi∈[10,40]. The network configuration is shown in Figs. 4 and 5. We can calculate the equilibrium state ~vqand the equity value vector ~ Von a classical computer using ~vq=˜ C(I−C)−1D~p, (9) ~ V= (I−C)−1D~p. (10) The objective function shown in Eq. (3) was implemented, for benchmarking reasons, both in a quantum annealer and a classical simulator. Variables viwere encoded, vi=P6 α=0 2αxi,α, on seven qubits. As such, this constrains the vito be integers smaller than 127. A quantum implementation of this algorithm does not require ancilla qubits, as there are no many-qubit interactions. The QUBO for this linear problem is a 70×70 matrix, with 210 couplers which cannot be solved directly due to the topology structure of the quantum annealer. D-Wave provides a software named qbsolv that allows to combine the classical computer with its quantum annealer by splitting the QUBO matrix into partition matrices that can be embedded in the quantum annealer. As a decomposing solver, it finds a minimum value of a large QUBO problem by splitting it into pieces solved either via a D-Wave system or a classical tabu solver (both approaches were considered here for comparison purposes). Since the D-Wave 2000Q processor is a quantum annealer, 20 results would be obtained from a qbsolv process with a default setting; these results should be handled by a correction process, e.g., majority voting, to help us identify the most plausible answer. The result of this QUBO problem is shown in Fig. 6, where the exact solution via solving a linear matrix equation, qbsolv solution with classical tabu solver, and qbsolv solution with D-Wave quantum annealer, are compared. It is straightforward to observe that a quantum annealer provides a similar solution to the exact solution than the classical tabu solver. While the failure-free model only has linear and quadratic terms in vi, the nonlinear model has powers of viup to order 2r, as shown in Eq. (7). For large r, this can be extremely resource-consuming in terms of Towards Prediction of Financial Crashes with a D-Wave Quantum Computer 7 Asset j Institution i Ownership Matrix 0 0.2 0.4 0.6 0.8 1.0 Fig. 4 Ownership matrix Dfor the linear model. The element Dik ≥0 corresponds to the percentage of asset kowned by institution i. We randomize the ownership matrix Dwith a Dirichlet distribution that satisfies Pn i=1 Dij = 1. Institution j Institution i Cross-holding Matrix 0 0.2 0.4 0.6 0.8 1.0 Fig. 5 Cross-holding matrix Cfor the linear model that describes the cross-holdings and self-ownerships between institutions. Cross-holding matrix is generated in a similar way to ownership matrix but with a constraint that all diagonal elements should be larger than 0.5, ensuring that all institutions can make decisions according to their own wills. ancillary qubits due to the requested connectivity. An estimation of the number of qubits can be made by counting the number of interaction terms; Eq. (7) indicates that ˆ Hcan have up to P2r α=0 n(2q+1) αterms, where n(2q+ 1) denotes the logical qubits that are required. In each term, 3-to-2rnew ancilla qubits are needed, depending on the number of logical qubits in this term. Therefore, the number of necessary qubits grows rapidly with the degree of the polynomial expansion r. Note that the aforementioned QUBO problem is NP-hard for any n≥2. In practice, this is an upper bound to the required resources, calculated assuming that ˆ Hhas all possible terms up to order O(2r). Here, we implement an enhanced model with failure terms on the basis of the linear model previously simulated. We perturb the vector of asset prices, leaving the ownership matrix Dand cross-holding matrix C invariant, and recompute the equilibrium state. Specifically, we set the price of some random assets to zero (to 8 Short form of author list Market Values v_i Equilibrium State 21 28 35 42 49 56 Fig. 6 Linear-model result. The first row shows the result if the matrix equation is solved exactly, the second row if qbsolv with tabu classical solver is used, and the third row if qbsolv with D-Wave 2000Q solver is employed. We observe that a quantum annealer provides a similar solution to the exact solution than the classical tabu solver. Asset j Institution i Ownership Matrix 0 0.2 0.4 0.6 0.8 1.0 Fig. 7 Ownership matrix Dfor the implemented network with failure terms. The element Dik ≥0 corresponds to the percentage of asset kowned by institution i. We randomize the ownership matrix Dwith a Dirichlet distribution that satisfies Pn i=1 Dij = 1. simulate, e.g: the assets’ destruction). In this study, we will use an expansion of ˆ Hto third order, which still characterizes the phenomenon of sudden drop near the critical value. Moreover, this approach provides strong nonlinearity while saving plenty of qubit resources. As a result, 70 logical qubits and 872,690 ancilla qubits are required with 4,446,575 couplers in the problem. This results in the requirement of about 6TB memory, since each element has an accuracy of double float in qbsolv. Due to the limitations of state-of-the-art techniques, the network is reduced to three institutions and each market value viis encoded by five qubits, bounding the maximum market value to be 31. New 3 ×7 ownership matrix Dand 3 ×3 cross-holding matrix Care generated while the price vector ~p before perturbation is ~p ={8.43,14.47,6.75,8.09,19.11 ,11.32,7.19}T. The network configuration is shown in Figs. 7 and 8. The equilibrium state before perturbation without nonlinearity is given as ~vq={21.18 23.33,30.83}T, and the critical value vector is still set to be 80% of the original equilibrium state, while the failure strength ~ βis considered to be 30% of the original equity value. The corresponding perturbed price vector is given as ~p ={8.43,14.47,0,8.09,0,11.32,7.19}T. Before calculating the new equilibrum state with nonlinearity and perturbation, some parameters, like Ja and q0, must be set. For the minor embedding of a submatrix in the D-Wave quantum annealer, this is done by introducing a penalty function between qubits in the Chimera graph requiring Jm≥Ja, which means that the Jafor mapping multi-qubit interactions to two-qubit interactions should be in the proper scale. Meanwhile, as we mentioned in the theory part, we need to sample out the thermal fluctuation by assuming that |ˆ Hk|is much smaller than Ja, or the protocol will break down because those ancilla qubits will not be in the corresponding ground state anymore. Thus, in the implementation we took Ja= 20Jkand q0= 10Jk, such that this could ensure that either q0or Ja−q0would be at least 10 times larger than Jk. Towards Prediction of Financial Crashes with a D-Wave Quantum Computer 9 Institution j Institution i Cross-holding Matrix 0 0.2 0.4 0.6 0.8 1.0 Fig. 8 Cross-holding matrix Cfor the implemented network with failure terms that describes the cross-holdings and selfownerships between institutions. Cross-holding matrix is generated in a similar way to ownership matrix but with a constraint that all diagonal elements should be larger than 0.5, ensuring that all institutions can make decisions according to their own wills. For this problem, the QUBO matrix had the size of 8280 ×8280, with 15 logical qubits, 8265 ancilla qubits and 38,790 couplers. Remark that the available quantum annealer structure is not optimized for this problem and, also, that the translation is not efficient because of sparse connectivity of the quantum processor. Therefore, the only benefit here is to explore the possibility of having certain sub-exponential speedup in the implementation of the problem in a quantum annealer [35], by optimizing submatrices generated by the partition algorithm in qbsolv. Finally, we compare our results from the quantum annealer with the integer equilibrium solution calculated with a straightforward method by trying 323times in Fig. 9, which shows a good agreement and the accuracy of the proposed method. Comparing the results after the perturbation with the pre-perturbation values, we can conclude that we have detected the financial crash.