{'fraction_non_alphanumeric': 0.06050043570272626, 'fraction_numerical': 0.013195568280841528, 'mean_word_length': 4.0940604523356585, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A discrete Schrodinger equation via optimal transport on graphs

In 1966, Edward Nelson presented an interesting derivation of the Schrodinger equation using Brownian motion. Recently, this derivation is linked to the theory of optimal transport, which shows that the Schrodinger equation is a Hamiltonian system on the probability density manifold equipped with the Wasserstein metric. In this paper, we consider similar matters on a finite graph. By using discrete optimal transport and its corresponding Nelson's approach, we derive a discrete Schrodinger equation on a finite graph. The proposed system is quite different from the commonly referred discretized Schrodinger equations. It is a system of nonlinear ordinary differential equations (ODEs) with many desirable properties. Several numerical examples are presented to illustrate the properties.


Introduction
The nonlinear Schrödinger equation (NLS) given in the form of plays vital roles in many areas in physical sciences [3,31]. The unknown Ψ(t, x) is a complex wave function for x ∈ R d , h > 0 is the Planck constant, and V(x) and W(x, y) are real valued functions, referred as linear and interaction potentials respectively. Although the NLS provides accurate predictions to various physical phenomena, its formulation is very different from the classical mechanics, and it cannot be easily interpreted by the Newton's law.
To bridge the difference, Edward Nelson provided an compelling approach in 1966 [27]. He derived the NLS by means in classical mechanics in conjunction with variational principles and stochastic diffusion processes [4,22]. To better understand his idea, we recall that the NLS (1) has a fluid dynamics formulation, named Madelung system [25]. By introducing a change of variables, Ψ(t, x) = ρ(t, x)e iS(t,x)/h , one can rewrite (1) as where ρ, S are unknown real valued functions, δ δρ(x) is the L 2 first variation operator, and I(ρ) = R d (∇ log ρ(x)) 2 ρ(x)dx is the Fisher information [18]. Nelson constructed a Lagrangian in the space of probability density functions, and then used calculus of variation to derive (2). We shall give a brief review on his approach in Section 3. Readers can find more details in [28]. Recently, Nelson's approach is linked to the framework of optimal transport theory [10,32], which has been developed in the past few decades [2,5,19,32]. The theory shows that the probability density space equipped with the optimal transport distance, also known as the Wasserstein metric, becomes a Riemannian manifold, and the NLS is a Hamiltonian system on this density manifold [22,30].
In this paper, we consider similar matters in discrete spaces, such as finite graphs. There are two reasons motivating us to conduct this investigation. On one side, Nelson's derivation is based on a variational principle, which makes his approach more attractive. However, although different formulations of the NLS on graphs have been introduced in physics and mathematics [8,11,15,16,29], not much is known through Nelson's approach, mainly because the theory of discrete optimal transport has not been seriously explored until the past few years [12,24,26]. On the other side, most of the discrete formulations for the NLS, especially those defined on lattices, are obtained by discretizations of the continuous NLS. Some important properties, such as conservation of energy, or dispersion relation, or time transverse (gauge) invariant, can be lost due to the discretizations. As reported in a recent survey on numerical methods for the NLS [3], none of the commonly used schemes has all those features simultaneously. We would like to examine whether Nelson's approach can provide a systematic strategy for constructing the discrete NLS on general graphs in order to retain those desirable properties. Our investigation confirms this assertion.
We follow the settings given in [13,23] to derive the discrete NLS, which turns out to be a system of ordinary differential equations. The derivation utilizes the optimal transport distance and the Fokker-Planck equation on a graph. The main results are sketched here.
Consider a weighted finite graph G = (V, E, ω), where V is the vertex set, E the edge set, and ω jl ∈ ω the weight of edge (j, l) ∈ E satisfying ω lj = ω jl > 0. We assume that G is undirected, contains no self loops or multiple edges. Given a linear potential V j on each note j and an interactive potential W jl , with W lj = W jl , for any two nodes (j, l) ∈ E. Nelson's approach leads to the following ODEs: where ρ j (t) and S j (t) are the probability density and potential function at time t on node j respectively, N (j) = {l ∈ V : (j, l) ∈ E} is the adjacency set of node j, g jl (ρ) = ρ j +ρ l 2 represents the weight of probability density on the edge (j, l) ∈ E, and denotes the discrete Fisher information. Using ρ j (t) and S j (t), we reconstruct a complex wave equation, for the discrete NLS, on the graph. The derived discrete NLS is very different from the commonly seen ones, with the most notable distinction being a nonlinear graph Laplacian, which has not been reported before.
We shall prove that the initial value ODE (3) is well defined with several favorable properties. For example, it is a Hamiltonian system that conserves the total mass and total energy. It is time reversible and gauge invariant. Its stationary solution is related to the discrete ground state, whose formulation has many desirable properties similar to those in the continuous space. In addition, a Hamiltonian matrix is introduced to study the stability of ground states. This Hamiltonian matrix is a symplectic decomposition of two nonlinear graph Laplacian matrices. One is from discrete optimal transport geometry, and the other is induced by the Hessian matrix of discrete Fisher information.
Our paper is arranged as follows. In Section 2, we discuss the necessity of using nonlinear Laplacian on graphs. In Section 3, we briefly review Nelson's approach, and then followed by the derivation of (3) in Section 4. We show several interesting dynamical properties of (3) in Sections 5 and 6. Several numerical examples are provided in Section 7.

Why nonlinear Laplacian on graphs?
To answer the question, we consider the classical linear Schrödinger equation without potentials, It is well known that (4) admits plane wave solutions given in the form of as long as the time frequency µ and the spatial wave number k satisfying the so called dispersion relation: Such a simple property may become problematic on graphs. To illstruate the challenges we face, let us consider the regular lattice in R d for its simplicity, or even periodic lattices if one wishes to avoid dealing with the boundaries. In the lattice, we assume that every node has the same number of adjacent nodes. The weight on each edge is uniformly given by ∆x, and the coordinate value for node j is x j = j∆x.
On the lattice, any linear spatial discretization of (4) can be expressed as where {C jl } s are selected, not all zeros, constants used to approximate the Laplace operator in (4). Assume that the discrete plane wave Ψ j (t) = Ae i(k·x j −µt) satisfies (5), we must have which is equivalent to C jl e ik·(l−j)∆x .
If µ and k satisfy the dispersion relation µ = |k| 2 /2, one gets The left hand side is a quadratic function on the wave number k, while the right hand side is a periodic function consisting of a finite terms of trignometric polynomials. This implies that there are at most a finite number of values for k satisfying this relation. Therefore only a finite number of pairs (µ, k) can form the plane wave solutions for (5). In contrast, any dispersion relation satisfying pair (µ, k) gives a plane wave solution for (4), and there are infinitely many of them. We summarize this observation in the following theorem.
Theorem 1. For any linear spatial discretization of (4), there are at most a finite number of pairs (µ, k) satisfying µ = |k| 2 /2 that can form its discrete plane wave solutions.
An implication of this theorem is that one cannot expect every pair (µ, k), µ = |k| 2 /2, to give a plane wave solution for a given linear spatial discretization. In fact, only a finite number of pairs, which is a measure zero set, can do that. It also suggests that a nonlinear Laplacian on graphs must be used if one wants to construct a spatial discretization scheme that allows any pair (µ, k) to form a plane wave solution. On the other hand, this theorem does not imply that for any given pair (µ, k), one cannot find a linear Laplacian on the graph and use the pair to construct a plane wave solution for (5). However, if a different pair is given, one may have to switch to a different linear Laplacian on the graph.
We also note that nonlinear Laplace operators have been used, and proved to be necessary in the study of Fokker-Planck equations on graphs [12]. These observations motivated us to consider Nelson's approach to systematically construct schemes for (1).

Review of Nelson's approach
In this section, we briefly review Nelson's approach [27,28], and explain its connection with optimal transport [30,32]. To simplify the presentation, we do not consider the interactive potential W(x, y) in this section, even though such a consideration can be obtained in a straightforward manner.
Consider the following stochastic variational problem: where b(t, x) ∈ R d can be any smooth vector field, X t is a stochastic process with prescribed probability densities ρ 0 and ρ 1 at time 0 and 1 respectively, h > 0 represents the noise level, B t is a standard Brownian motion in R d and E the expectation operator. Under suitable conditions given in [27], Nelson showed that (6) is equivalent to By using the probability density function ρ(t, x) defined as in which the density function ρ(t, x) evolves according to the Fokker-Planck equation Noticing the facts ∇ρ = ρ∇ log ρ , (8) can be rewritten into the following optimal control problem where ∂ρ ∂t The key of Nelson's derivation is based on a change of variable given by, Substituting v into (9), the problem becomes such that ∂ρ ∂t Here V(ρ) := R d V(x)ρ(x)dx is the linear potential energy and I(ρ) := R d (∇ log ρ) 2 ρdx is the Fisher information. The integrant in (11) is the Lagrangian for the optimal control problem.
The critical point (in the sense of Guerra-Morato [27]) of (11) satisfies the Madelung equations where v(t, x) = ∇S(t, x) is the optimal volecity field. The first equation in (12) is known as the continuity equation, while the second one is called Hamilton-Jacobi equation in the literature.
Introducing a complex wave function then Ψ(t, x) satisfies the linear Schrödinger equation Compared to the optimal transport distance, which can be defined by the well known Benamou-Brenier formula [5], Nelson's approach can be viewed as a modified optimal transport problem in which the negative of a potential energy and the Fisher information are amended to create the Lagrangian in formulation (11).

A Schrödinger equation on a finite graph
Following Nelson's approach, we shall derive the discrete NLS (3) on a graph via discrete optimal transport.
To do so, we first review some basics of the discrete optimal transport theory developed in recent years. Consider a finite graph G = (V, E, ω). The probability set (simplex) supported on all vertices of G is defined by where ρ j is the discrete probability function at node j. The interior of P(G) is denoted by P o (G).
Following [13], we introduce some notations and operators on G and P(G). A vector field v on G refers to a skew-symmetric matrix on the edges set E: For a probability function ρ ∈ P(G) and a vector field v, define the product ρv, called flux function on G, by ρv : where g jl (ρ) is a chosen function on the edge We remark that g jl may have other choices, such as the logarithmic mean used in [24]. The divergence of flux function ρv on G is defined by .
Given two vector fields v = (v jl ) (j,l)∈E , u = (u jl ) (j,l)∈E on a graph and ρ ∈ P(G), the discrete inner product is defined by, where the coefficient 1/2 accounts for the fact that every edge in G is counted twice, i.e. (j, l), (l, j) ∈ E.
Using the notations, the Wasserstein metric on the graph can be defined by the discrete Benamou-Brenier formula [5], where the infimum is taken over all vector fields v on a graph, and ρ is a continuous differentiable curve ρ : [0, 1] → P o (G).
P o (G) equipped with the metric W is a Riemannian manifold [12,13].

4.1.
Nelson's approach on a finite graph. Now, we are ready to derive the NLS on graph (3) via discrete optimal transport.
In the discrete case, the linear and interaction potentials refer to respectively. We start with a discrete analog of Nelson's problem presented in (8), where the infimum is taken over all discrete vector fields b, ρ(t) satisfies the discrete Fokker-Planck equation [12,13]: and ρ(0) = ρ 0 , ρ(1) = ρ 1 are given in P o (G). Similar to Nelson's change of variable, we define a new vector field v = (v lj ) (l,j)∈E on the graph Substituting v into (13), we can write the objective functional as where v is a vector field on the graph, such that We note that any given feasible path ρ(t) of (14) is determined by v(t), so we denote functional J only in term of v, and call it discrete Nelson's approach.
We also call (v(t), ρ(t)) a critical point of (14) if where In the following theorem, we show that the critical point of the discrete Nelson's approach satisfies (3). (14) in the sense of (15), which are smooth functions with respect to the time variable. Then v(t) and ρ(t) satisfy the following conditions: (a) v(t) is a potential vector field on the graph, i.e. there exists a function S(t) = (S j (t)) n j=1 defined on the nodes, such that v jl (t) = √ ω jl (S j (t) − S l (t)) , for all t ∈ [0, 1] and (j, l) ∈ E .
(b) For every S(t) that induces v(t), there exists a scalar function C(t) ∈ R, independent of the nodes, such that ρ(t) andS(t), defined byS(t) = (S j (t) − C(t)) n j=1 , satisfy (3): where H is the discrete total energy and J = 0 I −I 0 is a symplectic matrix, with I ∈ R n×n being the identity matrix. The symplectic form (16), identical to (3), is the discrete analog of (12). Following the convention, we call the first equation the discrete continuity equation, and the second one the discrete Hamilton-Jacobi equation.
The proof of Theorem 3 requires the following lemma, which can be viewed as the Hodge decomposition on a graph.
Proof. The detailed proof can be found in [24]. For the completeness of this paper, more importantly to introduce some notations that will be used later in the paper, we sketch the proof here. We define a weighted graph Laplacian matrix L(ρ) ∈ R n×n : where D ∈ R |E|×|V | is the discrete gradient matrix otherwise ; the transpose of D, denoted by D T , is the discrete divergence matrix and Θ ∈ R |E|×|E| is the diagonal weighted matrix We emphasize that L(ρ) depends only on ρ. This is different from the commonly seen graph Laplace operator.
We only need to show that there exists a unique gradient vector field ∇ G S, such that div G (ρ∇ G S) = L(ρ)S = div G (ρv) .
Since ρ ∈ P o (G) and the graph is connected, then this implies that value 0 must be a simple eigenvalue of the weighted graph Laplacian matrix L(ρ) with eigenvector {1, · · · , 1}. Thus there exists a unique solution of S up to constant shrift. Therefore ∇ G S is unique.
It is clear that w ∈ D for any > 0 because dρ dt + div G (ρ(v + w)) = 0. Since (v, ρ) is a critical solution of (14), we must have Because ρ(t) keeps the same for the vector field v + w, it implies where the last equality uses the fact div G (ρw) = 0. From (18), we get 1 0 (j,l)∈E u jl (t)w jl (t)g jl (ρ(t))dt = 0 .

Corollary 5. Let (v(t), ρ(t)) be a critical point of (14), and S(t) a function on G that induces v(t), then S(t)) and ρ(t) satisfy (3) if and only if
Proof. From the proof of Theorem 3, we know Then by direct calculations, we obtain We note Combining the calculations together, we have Therefore c(t) = 0 if and only if (22) holds.
In fact, the construction of S suggests S = L(ρ) −1ρ . This implies Thus the discrete Nelson's problem can be re-written as a geometric variational problem on the probability density manifold P o (G) where C is the set of continuous differentiable curve in P o (G). A solutions of (16) is a critical point of (23).

Complex formulations.
In this sequel, we reformulate (3) into a complex wave equation. Let us define where (ρ(t), S(t)) are solutions of (3), then Ψ(t) satisfies the following complex value ODE system.
in which the Laplacian on graph is defined by One may wonder when seeing the Laplace operator in such a nonlinear way. However, a closer examination demonstrates that this graph Laplacian is consistent with the one in the continuous case. In fact, we can show the following relationship in the continuous space. Let Ψ(t, x) be a complex function defined in R d , then Proof of (25). Denote Ψ(t, x) = ρ(t, x)e i S(t,x) h = e 1 2 log ρ(t,x)+i where the first equality uses 1 ρ ∇ρ = ∇ log ρ. while the second to the last equality uses the fact The nonlinearity in the Laplace operator allows the discrete NLS possessing many desirable dynamical properties, which will be shown in the next two sections.

Some Properties
For the convenience of presentation, we do not distinguish (3) and its complex wave version (24) in the discussion. The results here are always proposed for formulation (24) while all proofs are based on (3).
Our first task is examining the dispersion relation in the absence of potentials.
Proposition: For a uniform toroidal graph G, i.e. a graph that every node has the same number of adjacent nodes and the weight on each edge is uniformly given, the plane wave function Ψ(t) = A(e i(k·j∆x−µt) ) n j=1 , with any µ = 1 2 |k| 2 and A ≥ 0, satisfies The proposition can be verified by directly substituting the plane wave function in (3).
In what follows, we show that (3) is a well defined ODE system having several desirable properties such as total mass and energy conservation, time reversibility, and gauge invariant. In addition, its interior stationary solution shares the same property as that for the counterpart in the continuous case. Theorem 6. Given a simple weighted graph G = (V, E, ω), a vector (V l ) n l=1 , a symmetric matrix (W jl ) 1≤j,l≤n , and an initial condition Ψ 0 = (Ψ 0 j ) n j=1 (complex vector) satisfying Then equation (3) has a unique solution Ψ(t) for all t ∈ [0, ∞). Moreover, Ψ(t) satisfies following properties: (i) It conserves the total mass n j=1 |Ψ j (t)| 2 = 1 ; (ii) It conserves the total energy where E is a combination of the discrete Kinetic energy E kin , linear potential energy E pot and interaction potential energy E int , i.e.
They are given by the following definitions: (iii) It is time reversible: Ψ(t) =Ψ(−t) ; (iv) It is time transverse (gauge) invariant: Denote Ψ α (t) as the solution of (3) with V α = (V j + α) n j=1 , where α is a given real constant, then (v) The interior stationary solution of (3) shares a similar property as the one in continuous state: (3), where ν ∈ R and vector ρ * = (ρ * j ) n j=1 ∈ P o (G) are time invariant, then ρ * is the critical point of the minimization problem: Remark 2. E kin in (26) is an analog of the Kinetic energy in continuous case: In fact, we shall show that the boundary of probability set P(G) is a repeller for (3).
Proof. We show that for any given initial condition ρ 0 ∈ P o (G), there exists a unique solution (ρ(t), S(t)) for all t > 0. Since the right hand side of (3) is locally Lipchitz continuous and ρ 0 ∈ P o (G), from Picard's existence theorem, there exists a unique solution (ρ(t), S(t)) in time interval [0, T (ρ 0 )), where T (ρ 0 ) is the maximal time that the solution exists. We will prove T (ρ 0 ) = +∞ by the following claim.
The proof of claim 2 is based on two facts. On one hand, the ODE system (3) is a Hamiltonian system on probability set, which conserves the total mass and total energy; On the other hand, the total energy contains the Fisher information I(ρ). On the boundary of P o (G), I(ρ) is positive infinity, so is the total energy. From the conservation of total energy, it is not hard to see that the boundary of P o (G) is a repeller for ρ(t).
Proof of Claim 2. We construct a set B ⊂ P(G): Obviously, B is not empty.
We will prove that B is a compact set and ρ(t) ⊂ B for all t > 0 by following three steps.
Step 1, we prove (i) and (ii) for t ∈ [0, T (ρ 0 )). Since where E(Ψ) = H(ρ, S). Notice (3) has the following symplectic form Step 2, we show that I(ρ) is positive infinity on the boundary, i.e. lim min j∈V ρ j →0 Assume the above is not true, there exists a constant M > 0, such that if min i∈V ρ j = 0, then Hence for any (j, l) ∈ E, we have Since there exists a j * ∈ V , such that ρ j * = 0, the above formula implies that for any l ∈ N (j * ), ρ l = 0. Since G is connected and V is a finite set, by iterating through the nodes, we get ρ 1 = · · · = ρ n = 0, which contradicts the fact that n j=1 ρ j = 1.
Step 3, we claim that B is a compact set. This can be easily verified because I is a lower semi continuous function, and I(ρ) = +∞ when ρ ∈ P(G) \ P o (G). Hence B is a compact set in R n .
Let us combine above three steps. Since (3) is a Hamiltonian system in P o (G), Thus ρ(t) ∈ B ⊂ P o (G) for all t > 0.
Next, we prove (iii) and (iv). For (iii), since Ψ j = √ ρ j e i S j h , its conjugateΨ satisfies Let us look at (3) by changing t to −t.
5.1. Ground states. Similar to Nelson's idea in [27], we show that the stationary solution of (3) in Theorem 6 (v) is related to the discrete ground state of the NLS.
Corollary 7. If W is a semi positive definite matrix, then the stationary state is a ground state Ψ g = √ ρ g e −iν g t , i.e.
with ρ g = arg min Proof. From Theorem 5 (v), ρ g is a critical point of min ρ∈Po(G) E( √ ρ) and ν g is defined as above. We only need to prove Ψ g is the minimizer of problem (27). In fact, the equality holds if and only if S j = S l , for any (j, l) ∈ E. Since G is a connected graph, then a ground state Ψ g = √ ρ g e i S g h has the following structure: ρ g = arg min ρ∈P(G) E( √ ρ) and S g 1 = S g 2 = · · · = S g n .
Next, we show that the function E( √ ρ) = h 2 8 I(ρ) + W(ρ) + V(ρ) is strictly convex. If this is true, we can conclude that ρ g is a unique minimizer, which is the ground state.
Since the Hessian matrix of I is where t lj = (ρ l − ρ j )(log ρ l − log ρ j ) + (ρ l + ρ j ) > 0 , hence σ T Hess R n I(ρ)σ = 1 2 So Hess R n I is a semi-positive definite matrix. Figure 1. The phase portrait of (ρ 1 (t), ρ 2 (t), S 1 (t) − S 2 (t)) with different initial conditions. The ground state ( 1 2 , 1 2 , 0) is in the center of all these circles, so it is spectrally stable. Example 2 (Ground state). We demonstrate the ground states on a 1-D lattice graph. Set W = 0. Consider the following minimization problem ρ g = arg min where V j = x 2 j 2 . We compute the above minimizer numerically [23] in the interval [−5, 5] with n = 20. From Figure 2, we observe that the ground state approaches to the delta measure supported at 0 when h → 0. This captures the exactly same effect in continuous states, in which the ground state is a Gaussian distribution with variance h 2 [3].

Conclusions
In this paper we have introduced a new NLS on finite graphs (3). Compared to the existing work, (3) has the following distinct features: First, the discrete NLS is introduced via discrete optimal transport. This formulation provides a way to study the discrete NLS from geometric viewpoint; Second, the discrete Fisher information I(ρ) is applied to construct Hamiltonian system. Because of it, (3) conserves total energy and matches the stationary solution. Last but not the least, it introduces the ground state on graph by (30). Studying the stability problem around the discrete ground state introduces a Hamiltonian matrix, which is a symplectic composition of two modified graph Laplacian matrices. These give insights of the system that can be explored in the future.