{'fraction_non_alphanumeric': 0.0396311780539488, 'fraction_numerical': 0.009735983047935399, 'mean_word_length': 4.534706814580032, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Forecasting financial crashes with quantum computing

A key problem in financial mathematics is the forecasting of financial crashes: if we perturb asset prices, will financial institutions fail on a massive scale? This was recently shown to be a computationally intractable (NP-Hard) problem. Financial crashes are inherently difficult to predict, even for a regulator which has complete information about the financial system. In this paper we show how this problem can be handled by quantum annealers. More specifically, we map the equilibrium condition of a financial network to the ground-state problem of a spin-1/2 quantum Hamiltonian with 2-body interactions, i.e., a Quadratic Unconstrained Binary Optimization (QUBO) problem. The equilibrium market values of institutions after a sudden shock to the network can then be calculated via adiabatic quantum computation and, more generically, by quantum annealers. Our procedure can be implemented on near-term quantum processors, providing a potentially more efficient way to predict financial crashes.

A key problem in financial mathematics is the forecasting of financial crashes: if we perturb asset prices, will financial institutions fail on a massive scale? This was recently shown to be a computationally intractable (NP-Hard) problem. Financial crashes are inherently difficult to predict, even for a regulator which has complete information about the financial system. In this paper we show how this problem can be handled by quantum annealers. More specifically, we map the equilibrium condition of a financial network to the ground-state problem of a spin-1/2 quantum Hamiltonian with 2-body interactions, i.e., a Quadratic Unconstrained Binary Optimization (QUBO) problem. The equilibrium market values of institutions after a sudden shock to the network can then be calculated via adiabatic quantum computation and, more generically, by quantum annealers. Our procedure can be implemented on near-term quantum processors, providing a potentially more efficient way to predict financial crashes.
Introduction.-Imagine a financial network where institutions (banks, companies...) hold a number of assets as well as part of the other institutions in the network. Could a small change in asset value cause a massive drop in the market value of the institutions? Or in other words, could there be a financial crash? At present, we mainly rely on empirical or statistical tools to answer this question [1][2][3][4][5][6]. It is not clear that these methods can systematically and reliably predict financial crashes [7,8], because indicators of a crisis generally fail at predicting the next crisis [9]. Our failure to prevent these events is directly responsible for economic crises and their devastating consequences.
Mathematically, the problem of forecasting a crash is intractable, even for extremely simple financial networks. It was recently shown in Ref. [10] that this problem belongs to the complexity class NP-Hard, meaning that there are no known efficient classical algorithms to solve it. In general, financial crashes cannot be avoided by performing stress-tests or institution evaluations (without a global knowledge of the network). Even given complete knowledge of all the assets and cross-holdings in a simple network of 20-30 institutions, it would take more time than the age of the universe -13.7 billion years! -to compute the effect of a perturbation.
While the situation might seem dire, quantum computing has shown it could tackle this type of problems more efficiently, both in theory [11,12] and in practice [13][14][15][16]. In particular, quantum computing has proved extremely successful at tackling complex financial problems [17].
In this paper, we show that the problem of predicting financial crashes is amenable to quantum annealers. These quantum processors solve problems using the idea of adiabatic quantum computation, which uses nature's remarkable ability to find the lowest-energy eigenstatethe ground state -of complex Hamiltonians [18]. We begin by showing that finding the equilibrium condition of a financial network is equivalent to finding the ground-state of a specific spin-1/2 Hamiltonian with 2-body interactions. This is our problem Hamiltonian, which has the form of a Quadratic Unconstrained Binary Optimization (QUBO) problem, and which commercially available quantum annealers are well suited to solve [12]. Once the annealer finds a candidate ground state, we can forecast a potential crash simply by reading out the system's state, interpreted as a financial equilibrium configuration.
Financial network model.-We consider here a simple model of financial network proposed originally in Ref. [19]. In this model there are n institutions as well as m assets. Institutions could be countries, banks, companies... whereas assets are any object or project with an intrinsic value. Financial institutions can own shares of the underlying assets. Moreover, there are interdependencies between the institutions modelled by linear dependencies. Such cross-holdings model the fact that some institutions may own shares of other institutions, as well as approximate debt contracts between institutions.
Mathematically, we denote by p k the price of asset k, and by D ik ≥ 0 the fraction (percentage) of asset k owned by institution i. We define D as the n×m matrix of ownership. Additionally, let C be the n × n matrix of crossholdings among institutions. The component C ij ≥ 0 is the fraction of institution j owned by institution i. Following the convention in Ref. [10,19], we set C ii = 0, and define C jj ≡ 1 − i C ij as the amount of self-ownership of institution j. Matrix C is thus a diagonal matrix with entries C jj on the diagonal. The model can then be seen in terms of a complex network of interdependencies. Following Ref. [10], we further define the equity value i.e., the value of institution i due to ownership of assets and cross-holdings. In matrix notation, we can then write V = D p + C V , such that V = (I − C) −1 D p. As explained in Ref. [10], matrix I − C is guaranteed to be invertible. Additionally, the market value v i of institution i is its equity value rescaled with its self-ownership, i.e., v i = C ii V i . The market values are then the solution to the linear equation (1) As explained in Refs. [10,19], the model further introduces the notion of failure. This means that if the market value of an institution drops below a certain critical threshold, then the institution suffers an extra discontinuous loss in equity value. This non-linear behavior models the fact that if an institution cannot pay its own operating costs, then it may see a sudden drop in revenues. Moreover, if confidence in the institution is downgraded, then it may also see a sudden drop in its value since it will become difficult to, e.g., attract investors. Mathematically, this is modelled by a step-function such that if the market value v i of institution i drops below a critical threshold v c i , then it incurs a failure and its equity value drops by an additional While Eq. (1) is linear, Eq.(2) is highly non-linear due to the presence of the failure term b( v, p). In practice, this non-linearity is what makes it extremely difficult to determine the market values of institutions after a small change in the prices of assets. Specifically, given an equilibrium which satisfies Eq. (2), if the sum of all assets' prices drop by d, then it is NP-Hard to determine the maximum number of failures that could happen once the new equilibrium is reached [10]. This means that predicting a crash of the financial network due to small changes of the individual prices of assets is a computationallyintractable problem. Financial equilibrium as quantum ground state.-In the following, we will describe how to find a state which satisfies the financial equilibrium condition on a quantum annealer. We begin by stating the financial equilibrium condition, Eq.(2), as a variational problem. We then express this variational problem in terms of classical bit variables, and promote it to the problem of finding the ground state of a spin-1/2 Hamiltonian with many-qubit interactions. Finally, we reduce the many-qubit interactions to 2-qubit interactions, which are easier to implement experimentally [20]. We will also calculate the computational resources necessary to solve this problem.
(i) Variational Setup.-Given set of institutions, holdings and prices, the market values v at financial equilibrium satisfy Eq.(2). This equilibrium may not be unique. In general, though, one would have The above expression is strictly larger than zero away from equilibrium, and equal to zero and therefore minimum at equilibrium. Thus, we have recast the problem of finding the market values in equilibrium as a variational problem: the vector v at equilibrium will be the one that minimizes the classical cost function F ( v) for a given network configuration.
(ii) Bit variables for market values.-We now write F ( v) in terms of classical bit variables. This can be done by approximating the v i variables in terms of 2q + 1 classical bits using the usual binary notation, with bits x i,α = 0, 1. The market value v i of institution i is then codified, up to the desired approximation, by the string of bits (x i,−q , x i,−q+1 , · · · , x i,q ). This sets an upper-bound on market value v i of v max i = q α=−q 2 α .
(iii) Polynomial expansion of failure.-Next, we need a procedure to deal with the failure terms b( v, p), which are highly non-linear and modelled by a discontinuous Heaviside step function. In order to obtain an appropriate Hamiltonian for a quantum annealer, it would be desirable to have a continuous function instead. Moreover, we will need a Hamiltonian that can be efficiently described, even if it has many-qubit interactions. Under these constraints, we have found that the most viable option is to approximate the Heaviside function by a polynomial expansion. Of course, such an expansion is not unique. While it would be possible to find the optimal polynomial of a given degree approximating the function in a given interval and for a given error norm [21], standard approximations exist in terms of, e.g., shifted Legendre polynomials [22], which are sufficient to show the validity of our approach. In particular, one can make use of the Fourier-Legendre expansion in the interval [−1, 1], with P l (x) the lth Legendre Polynomial. As shown in Fig.1, the truncated series produces a reasonable approximation to the sudden discontinuity of the failure for polynomials of moderate-order. In our case, we can choose Thus, from now on we will take the approximation where ]. This approximation makes  (6) together, one can see after some inspection that G(x i,α ) is also a polynomial in the bit variables x i,α . More specifically, i.e., it is a Boolean polynomial of degree 2r. We then define the quantum Hamiltonian by promoting the classical bit variables x i,α = 0, 1 to diagonal qubit operatorsx i,α with eigenvalues 0, 1, i.e.,x i,α |0 = 0,x i,α |1 = |1 . In terms of spin-1/2 Pauli operators, these can be written asx = (1 +σ z )/2, withσ z the z-Pauli matrix. The quantum Hamiltonian is then which is nothing but the left hand side of Eq. (3), with the failure term approximated polynomially as in Eq.(6), and written in terms of qubit operators. This Hamiltonian is automatically hermitian. It is also a polynomial of degree 2r in the qubit operators. Each term inĤ involves many-qubit interactions for different sets of qubits, ranging from 0-qubit terms up to 2r-qubit terms at most. The explicit form of the Hamiltonian can be computed whenever necessary on a case-by-case basis. The number of terms inĤ will be analyzed later in detail.
(v) From many-qubit to 2-qubit.-The Hamiltonian in Eq.(8) could already be used as input for a quantum annealer that allowed for multiqubit interactions [20,23].
However, state-of-the-art quantum processors target, for practical reasons, Hamiltonians with at most 2-qubit interactions. Mathematically, finding the ground state of such Hamiltonians amounts to solving QUBO problems. It would then be desirable to have a Hamiltonian made of at most 2-qubit interactions. Thus, the final step of our derivation is to bring the interactions in the Hamiltonian of Eq.(8) down to 2-qubit terms at most.
To get such a modified Hamiltonian, we use the technique proposed in Ref. [20], which allows to implement effective k-qubit interactions using k extra ancilla qubits and 2-qubit interactions only. Suppose that we are given a k-qubit interactionĤ k of the typê where for convenience we now use the notation in terms of the z-Pauli matrix and J k is the interaction prefactor.
The trick is to write another HamiltonianĤ 2 , made of at most 2-qubit interactions, and such that it reproduces the low-energy spectrum ofĤ k . This is achieved by introducing k extra ancilla qubits and the Hamiltonian The topology of the interactions is shown in Fig.2. All the "logical" qubitsσ z i are all coupled among themselves via 2-body interactions with strength J. Each ancilla qubitsσ z i,a are coupled to every logical qubits, with 2body interactions of strength J a . Moreover, there are magnetic fields h and h a i accounting for 1-qubit terms. The idea, as explained in Ref. [20], is to find the values of J, J a , h and h a i such that the low-energy spectrum ofĤ 2 reproduces the energy spectrum ofĤ k . This is achieved by the choice with any q 0 satisfying the conditons |J k | q 0 < J a and |J k | J a − q 0 < J a . The low-energy sector of the Hamiltonian in Eq.(10), with couplings as in Eq.(11), reproduces the spectrum of the Hamiltonian in Eq.(9) up to an overall additive energy constant. This is guaranteed for the part of the spectrum satisfying |Ĥ k | J a , and allows the annealer to sample over low-energy states effectively reproducing the energy landscape of the manyqubit interactions on logical qubits.
Required resources.-Let us now consider how many qubits are needed. First, 2q + 1 qubits are required to describe each one of the n market values v i , amounting to a total cost in logical qubits of N logical = n(2q + 1). Second, the cost in ancilla qubits N ancilla can be estimated from the number of interaction terms N terms composing the Hamiltonian. A spin Hamiltonian constructed from a Boolean polynomial of degree 2r has 0-qubit terms, 1-qubit terms, . . . , 2r-qubit terms, giving a maximum of interaction terms. For nq r and 2r < n(2q + 1)/2, the leading term of Eq.(12) is the binomial coefficient for α = 2r. Thus, for n(2q +1) 2r together with 2nq n, and using (2r)! ≥ (2r/e) 2r , we have that Therefore, the number of terms to specify the Hamiltonian is a polynomial in n and q, whose degree is controlled by r. This means that the total number of qubits N qubits needed to implement our protocol is where we used N ancilla = O(r · N terms ). Since r is the degree of the polynomial approximating the step function, we see that this is actually acting as a resource truncation parameter: it controls the scaling exponent of the required resources. Two important remarks about Eq. (14) are also in order. First, it is an asymptotic expression which often heavily overestimates the number of qubits required in practice. Second, it implies that for a moderate value of r the failure term can be very strongly non-linear, which is what makes the classical problem NP-Hard, while keeping a polynomial scaling of the required quantum resources. In fact, this problem is NP-Hard for any r ≥ 2, because our derivation shows that it is as hard as finding the ground state of an arbitrary spin-glass [24]. Consequently, the computational running time will depend on the specifics of the instance and of the quantum annealing process, exactly as for the spin-glass problem.
Conclusions and remarks.-Here we have shown how the problem of forecasting financial crashes, which is NP-Hard, can be handled by quantum annealers. Specifically, our procedure allows the efficient construction of a QUBO formula by writing Eq.(3) in terms of z-Pauli matrices and 2-qubit interactions only, and which can be used in state-of-the-art quantum processors to predict a potential massive failure of financial institutions after a small shock to the system. Our result shows that quantum computers could help, at least in principle, in forecasting such situations, in addition to other known applications in finance [17].
While our results are constructed for a minimal financial network model, more complex networks can be handled similarly. Thus, these results show that near-term quantum processors, such as the D-Wave machine, may become useful in the early prediction of financial crashes. From a broader perspective, our results show how quantum computers can be used to handle problems related to financial equilibrium, and in particular to forecast the financial consequences of different courses of action.
There is plenty of room for further research. For instance, we could explore ways of improving the efficiency and accuracy of our procedure. In a future publication, we would like to present an experimental implementation of our algorithm on a commercially available quantum annealing processor, where QUBO formulas are the input. Finally, it would be extremely interesting to extend this protocol to deal with other financial equilibrium problems.