{'fraction_non_alphanumeric': 0.04151028713542844, 'fraction_numerical': 0.017770743839023287, 'mean_word_length': 4.339449541284404, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A quantum Poisson solver implementable on NISQ devices

Solving differential equations is one of the most compelling applications of quantum computing. Most existing quantum algorithms addressing general ordinary and partial differential equations are thought to be too expensive to execute successfully on Noisy Intermediate-Scale Quantum (NISQ) devices. Here we propose a compact quantum algorithm for solving one-dimensional Poisson equation based on simple Ry rotation. The major operations are performed on probability amplitudes. Therefore, the present algorithm avoids the need to do phase estimation, Hamiltonian simulation and arithmetic. The solution error comes only from the finite difference approximation of the Poisson equation. Our quantum Poisson solver (QPS) has gate-complexity of 3n in qubits and 4n^3 in one- and two-qubit gates, where n is the logarithmic of the dimension of the linear system of equations. In terms of solution error {\epsilon}, the complexity is log(1/{\epsilon}) in qubits and poly(log(1/{\epsilon})) in operations, which is consist with the best known results. The present QPS may represent a potential application on NISQ devices.


INTRODUCTION
Quantum computing is capable of solving problems efficiently which are intractable for classical computing. Since the discovery of Shor's factoring algorithm [1], quantum algorithms demonstrating advantages over classical methods have been developed for a substantial variety of tasks [2]. One of the most compelling applications is for solving differential equations which is the main task in high-performance scientific computing.
A series of quantum algorithms for solving ordinary and partial differential equations (ODEs and PDEs) have been developed, which promise an exponential speed-up over classical algorithms in the dimension of equations and solution errors [3][4][5][6][7][8][9]. The main idea of these algorithms is that encoding the differential equations as a linear system, and solving it by Quantum Linear Systems Algorithm (QLSA) [10][11][12] or Hamiltonian simulation [13,14]. These algorithms are general methods for a class of differential equations. They are considered to be out of reach without large-scale fault-tolerant quantum computers.
In present paper, we focus on the problem of solving the one-dimensional Poisson 2 equation by discretizing it into a linear system of equations using the finite difference approximation. The Poisson equation, usually expressed as 2 f  , is a widely used PDE across many areas of physics and engineering [15]. Many quantum algorithms are proposed to solve the general Poisson equation [7,9,[16][17][18]. Compared with them, the present algorithm has a much lower gate-complexity. It would be implementable on Noisy Intermediate-Scale Quantum (NISQ) devices. The inspiration of our method is from the observation that the eigenvalues of the discretized matrix of the Poisson equation are square of sine values and sine values can be prepared as the probability amplitudes easily by Ry rotation. The QLSA is actually to produce a quantum state with probability amplitudes being the reciprocals of eigenvalues. There should exist a simple way of accomplishing it by operating Ry rotation only. That is, all the transformations are performed on the probability amplitude. With such a way, we could eliminate the need for phase estimation, Hamiltonian simulation [13,14] and quantum arithmetic [19][20][21], which are the major contributors to the gate-complexity.
It is intriguing that the above inspiration is realized quite naturally from the fact that the product of all eigenvalues of the discretized matrix equals constant. The product is a sine formula which is derived from the study of Cartan matrix in Lie algebra [22]. Benefiting from the Ry rotation and the sine formula, we establish an efficient quantum Poisson solver (QPS) with the complexity of 3n in qubits and 5/3n 3 in one-and twoqubit gates, where n is the logarithmic of the dimension of the linear system. With the rapid developments of quantum hardware and techniques [23][24][25][26], our QPS should be able to be executed successfully on NISQ devices. This paper is organized as follows. In Section 2, we provide an overview of the problem we address and the main idea of our algorithm. In Section 3, we describe the quantum algorithm and circuit in detail, including the implements of each module. The gate-complexity, depth and error analysis of the algorithm are discussed in Section 4. Section 5 shows the demonstration results of the present circuits on a quantum virtual system. Finally, conclusions are discussed in Section 6.

OVERVIEW OF THE PROBLEM AND METHOD
The problem we address is solving the one-dimensional Poisson equation with Dirichlet boundary conditions, which can be described as The b(x) is a given smooth function representing, say, charge distribution in electrostatics problems or velocity distribution in fluid dynamics problems, and v(x) is the unknown to solve.
We choose the simple central difference approximation to discretize the second-order derivative, then Eq. (1) in the finite difference form is, The number of discrete points is N+1 and the mesh size h equals to 1/N. The εi is the truncation error induced by the finite difference approximation which can be shown to [ 27]. When b(x) is smooth enough, the norm of the fourth derivative is bounded uniformly independent of h. It is worth noting that this truncation error is the only error of the solution solved by our algorithm. So the final solution error is ε = h 2 = 1/N 2 , which will be discussed subsequently.
Ignoring the truncation error in Eq. (2), now the problem of solving one-dimensional Poisson equation transfers into solving a linear system of equations as follows, 1 Matrix A is a well-studied tridiagonal Toeplitz matrix. The eigenvectors and corresponding eigenvalues are ( ) 2 sin( ) respectively [27]. Such a linear system of equations can be, of course, solved using the standard QLSA as done in Refs. [16,18]. The solution state|v would be expressed as In order to produce such state, the HHL algorithm first estimates the eigenvalue λj for each eigenvector uj through phase estimation, then calculates the reciprocal of λj and converts it from binary string to probability amplitude.
Here we propose a much simple way of producing the solution state based mainly on Ry rotations. The sine formula derived from Cartan matrix [22] is as follows, where n is the logarithmic of the dimension of the Cartan matrix. Note that each sine square term on the equation is actually the eigenvalue λj of matrix A. So the reciprocal of one eigenvalue equals to the product of all the other eigenvalues.
However, Eq. (5) cannot be used directly to inverse the eigenvalues because the number of terms equals to the dimension of the linear system of equations, namely exponential with n. By exploiting the distribution characteristics of the terms, Eq. (5) can be simplified to 2 where n>2, and m is an integer belonging to [0, n-2] used to make 2 -m j to be an odd 4 number. Details about the derivation of the equation are described in appendix A. Now the reciprocal of eigenvalues can be regarded as the product of 2(n-1) sine values. Each sine value of Eq. (6) is prepared on the probability amplitude easily through controlled Ry rotation. So the amplitude 1/λj in the solution state can be prepared by implementing the probability amplitude directly. There are no phase estimation, Hamiltonian simulation and arithmetic in the algorithm. The gate-complexity is low and the solution error comes only from the initial discretizing process of the Poisson equation.

QUANTUM ALGORITHM AND CIRCUIT DESIGN
Our algorithm consists of three stages: basis conversion, inversing the eigenvalues on the probability amplitudes, and uncomputing the basis conversion. The overall circuit is shown in Fig. 1. It is assumed that has been prepared and stored in register B.
By and large, the main produces of our algorithm goes as follows: (1) The state| n b in register B can be expressed as (2) The sine values sin(jπ/2 n+1 ) is prepared as the probability amplitudes of register E using controlled Ry rotations. After this step, the computational bases | j are entangled with the 2(n-1) sine terms on the right hand side of Eq. (6).
(3) The state of |1 j C   on the ancillary qubit are prepared using the controlled NOT operation controlled by the 2(n-1) sine terms in register E.  [28] can be applied before measurement to increase the success probability of obtaining the solution.

Basis conversion
The initial state of register B can be expressed as using the computational basis | j and eigenstates | j u  of matrix A, respectively. A unitary operator U is required to accomplish the following transform, That is, the j th row of the operator U is uj, 12 21 [ , , , ] .
Apparently, U is the sine transform [16,29]. More specifically, we can design the basis conversion circuit by the discrete sine transform (DST) of type I in Ref. [29]. The DST is related to discrete Fourier transform (DFT) as follows, † 2 1 1 ( ).
The TN is a basis change matrix, and the FT2N,  can be implemented using Eq. (9) as shown in Fig. 2. Details about this circuit can be found in Ref. [18].

Inversing the eigenvalues
The reciprocal of eigenvalues are calculated using Eq. (6). The sine terms are indexed by two variables, namely m and k. So the circuit to inverse the eigenvalues contains two 6 levels. For the first level, the circuit consists of n-1 modules, as shown in Fig. 3, which corresponds to m being from 0 to n-2. Note that in each module 2 -m j is an odd number. Fig. 3 The overall circuit to calculate the reciprocal of eigenvalues. In general, the circuit consists of (n-1) controlled RY modules numbered with m from 0 to n-2. Each RY module is controlled by two kinds of control qubits called global and local control qubits. The global control qubits are the lower (m+1) qubits in Reg. B which are represented by the red dots and circles. The global control qubits are actually used to pick out such j that 2 -m j is an odd number. The local ones are the higher (n-m) qubits of Reg. B inside the X modules which are described below. Note that the (n-1) RY modules are computed serially. They can turn to be parallel by adding n-2 ancillary qubits, and then the depth of the circuit is reduced from O(n 3 ) to O(n 2 ), see appendix B for a feasible design.
The second level is the controlled RYm module which actually implements Eq. (6) with the corresponding m. Each RY module contains n-1 terms of square of sine values.
The sine values can be prepared as probability amplitudes easily using the Ry rotation. And the square of sine values can be obtained using two qubits as follows, 2 2 2 2 (2 )|0 cos |00 cos sin |01 +sin cos |10 +sin |11 . Fig. 4 shows the circuit design for the controlled RY0 and RY1 modules. For r from 0 to m-1, it is to produce the constant terms of sin 2 (/6); and for r from m to n-2, it is to produce the terms that k being from n-m down to 2. The NOT gates are used to calculate the complements of j. 7 The circuit to implement the controlled 2 y R  operation is rather simple as shown in  (11) where jk is the local control qubit. Fig. 5 is designed based on this equation by adding the global control qubit. The state evolution during the produce of inversing the eigenvalues can be expressed as follows, Finally, the basis conversion is uncomputed and the system state evolves into 21 (14) Before the measurement, the variable time amplitude amplification technique can be used to increase the success probability of obtaining the solution. If the measurement result of the Ancillary qubit in Fig. 1 is |1 , then the system state collapses into Therefore, the solution state is created in register B.

GATE-COMPLEXITY, DEPTH AND ERROR ANALYSIS
Now we analyze the complexity, depth and error of our algorithm. As can be seen from Fig. 1, the present algorithm needs 3n qubits, where n=logN and N-1 is the dimension of the linear system of equations. Considering the ancillary qubits, the least number of qubits required is 3n+1 [30]. In general, we can add less than n ancillary qubits to reduce the complexity of decomposition of gates.
For the gate-complexity, the total number of gates required is 5/3n 3 in one-and twoqubit gates. Furthermore, if the multi-controlled one-qubit and one-controlled multiqubit gates can be applied, like the new methodologies of i-Toffoli/CNOT n operations [31], the number of gates required can be reduced sharply.
The depth of our QPS mainly depends on the way of implementing the controlled Ry rotation as shown in Fig. 1. If the RY modules are executed serially as shown in Fig. 3, the depth of the circuit is 5/3n 3 . After parallelizing the RY modules as discussed in appendix B, the depth is reduced to 10n 2 . This improvement is achieved by simply adding another n-2 ancillary qubits.
Since the cost of our circuit is small and the depth can be shallow, the present QPS has the potential to solve a non-trivial problem on NISQ devices. For example, if solving the one-dimensional Poisson equation by discretizing it with 2 15 points, our QPS can be implemented using 46 qubits and tens of thousands of elementary gates. After parallelization, the depth of the QPS circuit is several thousand with a need of 60 qubits. This cost is acceptable for the NISQ devices with fidelity of 99.99% [32]. The output state encodes the solutions of more than 32 thousand points into the probability amplitudes.
Throughout our algorithm, the operations related to eigenvalues are performed on the probability amplitude, which induces no errors as that in phase estimation and arithmetic. Therefore, the solution error of our algorithm comes only from the finite difference approximation of the Poisson equation. As mentioned above, the truncation error is ε=1/N 2 . Considering n=logN, we have n=1/2log(1/ε). So the complexity of our algorithm is log(1/ε) in qubits and poly(log(1/ε)) in quantum operations. Such performance of the complexity on the error is consist with the best known result [5][6][7]. Additionally, any direct or iterative classical algorithms for solving the Poisson equation with error ε have a cost of at least ε -α , where α > 0 is a smoothness constant [33]. So our algorithm offers an exponential speedup over classical method in terms of error. 9

DEMONSTRATION
We demonstrate our algorithm on a quantum virtual computing system installed on the Sunway TaihuLight Supercomputer in Wuxi, China [34]. Comparing with Eq. (6), Eq. (5) is a more direct way of calculating the reciprocal of eigenvalues, but it has exponential number of terms. Fig. 6 (a) and (b) show the circuits for the case of n=2 corresponding to Eq. (5) and (6), respectively. Circuit (a) costs 12 qubits and 130 oneand two-qubit gates. In comparison, (b) costs just 6 qubits and 90 gates. The number of qubits used in register E is 2(2 2 -1) and 2(2-1), respectively. It is an exponential reduction. With further optimizations, e.g. simplifying the QFT [35] in basis conversion, the cost of the circuit can be reduced.

CONCLUSIONS
We present a compact quantum Poisson solver (QPS) for solving the onedimensional Poisson equation. Through the algorithm, the major operations related to eigenvalues are performed on probability amplitudes by single-qubit Ry rotation. The expensive procedures of phase estimation, Hamiltonian simulation and quantum arithmetic can be circumvented. The solution error comes only from the finite difference approximation of the Poisson equation. The idea of executing function calculations on probability amplitude by single-qubit rotation should be inspirational in many ways for optimizing quantum algorithms.
The costs of our QPS is nearly optimal, that is, 3n in qubits and 5/3n 3 in one-and two-qubit gates, where n is the logarithmic of the dimension of the linear system of equations. And the dependence of the gate-complexity on solution error is log(1/ε) in qubits and poly(log(1/ε)) in quantum operations, which consists with the best known results and achieves an exponential speedup over classical method. When solving the Poisson equation by discretizing it into 2 15 points, our algorithm needs only 46 qubits and tens of thousands of one-and two-qubit gates. The solution error is, in theory, 2 -30 . So the present QPS should be capable of running on Noisy Intermediate-Scale Quantum (NISQ) devices.
An open question is how to extend the present algorithm to d-dimensional Poisson equation. For higher dimensions, the eigenvalues are the sum of that of one-dimensional case. There should be an intuitive way to inverse the eigenvalues on probability amplitudes, like quantum signal processing [36], and achieve a complexity having nearly linear dependence on d.

APPENDIX A
We use central difference approximation to discretize the one-dimensional Poisson equation, and the resulted linear system of equations is solved by the QLSA. The discretized matrix A is a Cartan matrix, and the product of all its eigenvalues forms a sine formula as shown in Eq. (5) [22]. This equation shows that the reciprocal of each eigenvalue is equal to the product of the remained 2 n -2 eigenvalues. The number of terms can be reduced exponentially as shown in Eq. (6) in the following way.
Firstly, we study the distribution characteristics of the terms on the left hand side of Eq. (A.1) derived from Eq. The angular coefficient j/2 n+1 of each term is listed in the way as shown in Fig. A.1. Apparently, each layer contains 2 n-1 odd terms because j is an odd number, and 2 n-1 -1 even terms. All of the even terms in one layer are actually the ones of the adjacent upper layer, and each even term always corresponds to an odd one of some upper layer. That is, all the terms of one layer, say n=4 layer, are actually the odd terms of the present and upper layers, i.e. layers of n=4, 3, 2, 1. So all the terms are divided into n groups and each group contains only the odd terms of that layer. Using the distribution characteristics, the product can be re-organized with only the odd terms of each layer as follows, Secondly, we analyze the reciprocal of each term sin 2 (jπ/2 n+1 ). The following discussions are divided into two conditions for j being an odd number and an even number.
When j is an odd number belonging to [1, 2 n -1], starting from Eq. (A.1) we have The above derivation contains a recursive process that cut the number of terms of the product by half utilizing the symmetry of distribution in each layer as shown in Fig.  A.1. The two trigonometric formulas, i.e. sin2θ = 2sinθcosθ and sinθ = cos(π/2-θ), are used repeatedly in the derivation. So the reciprocal of eigenvalues with j being an odd 12 number can be calculated by the (n-1) terms as follows, When j is an even number, it can be transformed to an odd one in some upper layer. Suppose j = 2 m i, where i is an odd number and m is an integer belonging to [1, n-2], then the even term j corresponds to the odd term i in the upper m th layer. In such case, sin -2 (jπ/2 n+1 ) can be calculated as 1  This is pretty intriguing. The reciprocal of 8/λj is the product of (n-1) terms and each term is a square of sine value. The first m terms are constants, namely sin 2 (/6). Put it another way, we can inverse the eigenvalues through 2(n-1) sine terms. The number of terms of the product is reduced exponentially from 2(2 n -2) to 2(n-1), and this guarantees that the complexity of our algorithm is 3n in qubits.

APPENDIX B
In Fig. 3, the RY modules are executed serially. The gate-complexity of the circuit is low, but the depth is high to run efficiently on NISQ devices. Here we propose a feasible way of paralleling the RY modules to reduce the depth from O(n 3 ) to O(n 2 ). The parallelization consists of three aspects as follows.
Firstly, parallelize the control qubits in Fig. 3. One more register C with (n-2) qubits is allocated to store the global control qubits. The control qubits are parallelized by the CP (Control-qubits Parallelization) module as shown in Fig. B.1.
Secondly, break up each RY module in Fig. 4 into the basic unit of controlled 2 y R  and assemble new module called RYP (RY Parallelization). Let Ry(m,r) represent the controlled 2 y R  indexed by m and r as shown in Figs. 3 and 4, respectively. The assembling rule is that the Ry(0,r), Ry(1, r+1mod(n-1)), …, Ry(m, r+m mod(n-1)), …, and Ry(n-2, r+ n-2 mod(n-1)) constitute the module RYPr. Fig. B.1 shows the circuit for RYP0 and RYP1. In this way, all the 2 y R  are rearranged to be parallel in each RYP module. 13 Thirdly, as shown in Fig. 5, the controlled 2 ( 2 ) i y R   in each RYP are also rearranged to be parallel. The basic idea is illustrated in Fig. B.2 for RYP0 module.  Fig. 3. The CP module is used to parallelize the control qubits and RYP represent the parallelized RY modules. The depth of CP is 5(n-2) 2 when the multi-controlled NOT gates are decomposed into one-and two-qubit gates. . The depth of the RYP 0 is reduced from 4n 2 to 8n when decomposed by one-and two-qubit gates. The numbers imply that the depth of RYP depends on RY 0 . The total depth of RYP modules is 5n 2 .
As we can see, the depth of our parallel-version QPS mainly depends on the RY0 and 14 CP modules. Note that the qubits in register E can also be used to do the decomposition of multi-qubit gates before RYP modules, then there is no need to adding more ancillary qubits. Hence, the gate-complexity of RY modules turns to 4n in qubits and the depth reduces from 5/3n 3 to 10n 2 . When n=15, the depth of inversing eigenvalues based on serial and parallel RY modules is about 8000 and 1800, respectively. Since the decomposition of the multi-controlled one-qubit and one-controlled multi-qubit gates constitutes the major cost, the depth of TN in BC and CP in RY can be reduced to O(n) using the technology of iToffoli/CNOT n gates [31]. Additionally, the depth of FT2N in BC can also be reduced to O(n) even O(logn) [37,38].