{'fraction_non_alphanumeric': 0.03283072546230441, 'fraction_numerical': 0.009900426742532005, 'mean_word_length': 4.300361881785284, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quantum Persistent Homology for Time Series

Persistent homology, a powerful mathematical tool for data analysis, summarizes the shape of data through tracking topological features across changes in different scales. Classical algorithms for persistent homology are often constrained by running times and memory requirements that grow exponentially on the number of data points. To surpass this problem, two quantum algorithms of persistent homology have been developed based on two different approaches. However, both of these quantum algorithms consider a data set in the form of a point cloud, which can be restrictive considering that many data sets come in the form of time series. In this paper, we alleviate this issue by establishing a quantum Takens's delay embedding algorithm, which turns a time series into a point cloud by considering a pertinent embedding into a higher dimensional space. Having this quantum transformation of time series to point clouds, then one may use a quantum persistent homology algorithm to extract the topological features from the point cloud associated with the original times series.

The topological features discovered via persistent homology are displayed in a persistence diagram, and the efficient computation of such diagrams using packages such as Dionysus [17] and Ripser [18] leverage certain properties of simplicial complexes to create persistence diagrams efficiently [19]. However, these classical algorithms are not easily scalable and tend to deteriorate with the increase in the number of data size. Indeed, a point cloud consisting of n points possesses 2 n potential subsets that could contribute to the topology, so the best classical algorithm for estimating these features with accuracy δ takes time O(2 n log(1/δ)) and requires O(2 n ) bits to encode the subsets [20].
To bypass the computational bottleneck, quantum algorithms for homology (fixed data resolution/scale) [21,22], and more recently, for persistent homology (varying data resolutions/scales) [23,24] use a quantum random access memory (QRAM) to efficiently read a point cloud data set, and encode it into pertinent quantum states. One then uses these quantum states to build membership oracles that identify the features that are present at different scales. The main advantage of these algorithms is that they use relatively small QRAMs of size O(n 2 ), which only require O(log n) calls to access the data [25], as opposed to classical algorithms that need memories of size (O(2 2n ).
These quantum algorithms make use of membership oracles to determine which objects are present at a certain scale. The oracles are simply subroutines that take into consideration a pertinent triangulation of point cloud data, called simplex and a positive number encoded into qubits and return a qubit in state |1 if the simplex is present at scale , or a qubit in state |0 otherwise. On the other hand, the membership oracles that exist in the literature so far are merely restricted to simplicial complexes built from point cloud data sets.
In this paper, a quantum TDA algorithm is proposed by providing a membership oracle for time series. Indeed, a QRAM is queried to access the time series, and a quantum version of the Takens's delay embedding theorem [26] is established for transforming a time series into a point cloud while preserving the relevant topological information. In turn, the oracle is plugged into the quantum algorithm for persistent homology [23] to study time series and their behavior (periodic, chaotic, etc.) by analyzing their corresponding point cloud.
This paper is organized as follows. Section II introduces the background information like the Takens's delay embedding, and summarizes classical and quantum algorithms for TDA. Section III details our novel membership oracle as well as the quantum TDA algorithm for time series. Section IV shows two implementations of the quantum algorithm to time series data sets, and finally, Section V concludes with a brief discussion of our results.

A. Delay Embedding
Consider a time series x t for t = 1, 2, ..., T . The Takens's delay embedding of the time series x t is given by the vector for i = 1, ..., T − τ d, where d is the dimension of the point cloud, and τ is the delay parameter. The Takens's delay embedding theorem guarantees that the map from the time series to point cloud is an embedding and as such all the relevant topological information is retained [26]. The parametric choices of the dimension, d, and the delay, τ, has been widely discussed in the literature, e.g. see [27] and references therein. For example, the time series is typically embedded into a d = 2, 3, space, and the delay parameter may be selected based on the autocorrelation.

B. Vietoris-Rips Filtration and Persistent Homology
An oriented k−simplex or simplex of dimension k is the collection of all convex combinations formed by (k + 1) ordered and linearly independent vertices, a few examples are shown in Fig. 1 such as vertices, edges, triangles, tetrahedrons. They are written as the ordered list of their vertices, and a subset of this list is called a face of the simplex.
Homology studies simplicial complexes and chain complexes. A simplicial complex is a collection of simplices such that the faces of any simplex in the complex are also in the complex and the intersection of any two simplices in the complex is also a simplex in the complex. A commonly used simplicial complex is the Vietoris-Rips (VR) complex, which at scale is defined by all the simplices with a diameter of at most . So, a simplex σ is in the complex S if and only if all the pairwise distances between its points are less than . On the other hand, the chain complex of S over Z 3 = {−1, 0, 1} is the collection of formal sums of simplices in S with coefficients in Z 3 .
Classical algorithms encode the VR complex and chain complex, then compute its corresponding boundary matrix, and finally diagonalize it to extract topological features like the number of connected components, holes, voids, and k dimensional holes in general.
Algorithms for persistent homology consider instead a filtration or nested sequence of VR complexes S 0 ⊆ · · · ⊆ S N and analyze a boundary matrix in which the simplices are ordered according to the sequence [20]. Persistence diagrams are used to display the results of these algorithms. Points on the persistence diagram (b, d) represent the number of k dimensional holes born at scale b that disappear at scale d.

C. Quantum TDA Algorithms for point cloud data
The quantum algorithms appeared in [23,24] established for the first time a quantum implementation for computing the persistent homology of a point cloud to reveal its topological properties across different scales. The study in [23] defines a linear map, the persistent Dirac operator, which tracks topological features across a pair of different scales. The persistent Dirac operator is a generalization of the Dirac operator established in the algorithms of [21,22], which cannot track features across different scales/resolutions, and therefore they cannot obtain any persistent information. The work in [24] builds a block-encoding of the persistent combinatorial Laplacian and uses the quantum singular value transformation to extract the persistent topological features.
All of these quantum algorithms use a QRAM to store and access the data efficiently, they encode the points of a cloud as qubits and use superpositions to represent complexes. They also rely on a membership oracle to identify the simplices that are present at a certain scale and construct projections onto the corresponding VR complexes.

A. Encoding Data and Simplices
Consider a discrete time series x t , t = 1, 2 . . . , T , such that T > 0 is an integer. The data are stored in a QRAM, allowing for their quantum parallel access. The QRAM maps a quantum state |t |0 to the state |t |x t where |x t is a state normalized to reflect the value x t . Such states can be encoded using O(log 2 T ) qubits.
Recall that the point cloud relates to the time series via the vectors v i given in Eq. (1). We use T − τ d qubits to encode these points so that any simplex σ formed with these points is represented by a quantum state |σ , with the qubits corresponding to points in the simplex in state |1 , and all other qubits in state |0 . A balanced superposition of the states represents the maximal simplicial complex S. Define Z 3 = {−1, 0, 1}. Using these quantum states as a basis of the generated Hilbert space over Z 3 encodes the chain complex needed to extract the desired topological features.

B. Quantum Delay Embedding
Considering the time series data x t , along with the embedding parameters, the dimension, d, of the space to which the times series is embedded, and the delay parameter, τ , one may check for membership in a simplicial complex by first computing the distances between points v i in the embedded point cloud, defined in Eq. (1). The distance between two points v i and v j of the delay embedded time series is given by With the ability to create quantum states encoding the values x t , we can construct a quantum circuit that takes input states of the form |t 1 |t 2 |0 and returns the output state |t 1 |t 2 |x t 1 − x t 2 | 2 , where the last register contains an estimate of the difference between x t 1 and x t 2 . To obtain an estimate with accuracy δ it is necessary to make O(δ −1 ) calls to the QRAM and O δ −1 (log 2 T ) 2 [21,25]. Moreover, this circuit can also operate in quantum parallel.
Notice that a simplex σ is in the VR complex S if and only if for each pair of vertices v i and v j in the simplex, D(v i , v j ) ≤ , where the distance, D, is defined in Eq. (2). Being able to compute the difference |x t 1 − x t 2 | allows us to create an oracle O that verifies if the difference |x t 1 − x t 2 | ≤ . Such an oracle takes as input the state |t 1 |t 2 |1 and returns the state |t 1 |t 2 |a , where Given a simplex σ encoded as the quantum state |σ , where the qubits in state |1 correspond to the vertices of σ, we can make repeated calls to the oracle O to check if the simplex belongs to the VR complex at scale . In particular, we need to verify the inequality for all t 1 = i + tτ and t 2 = j + tτ with 0 ≤ t < d and i < j such that v i and v j are vertices of σ, where d and τ as in Eq.
(1) must be chosen according to the data. The vertices v i , v j are obtained from the quantum state |σ , and they correspond to the qubits in state |1 . One concludes that σ is in S if all the calls to the oracle O yield an output with the last qubit in state |1 . However, if at least one of the calls returns an output with the last qubit in state |0 , it means the simplex is not yet present at that scale.
To that end, for fixed d, and τ, a membership oracle O d,τ is constructed such that it acts on a quantum state |σ |1 according to The membership oracle, O d,τ , makes at most dk(k + 1)/2 calls to the oracle O in order to determine whether a simplex σ of dimension k is present in the VR complex at scale .

C. Quantum Algorithm for Persistent Homology
Having established a membership oracle O d,τ , defined in Eq. (4), allows to consider a quantum persistent homology algorithm for time series. First, one uses T − τ d qubits to represent the point cloud points, v i , defined in Eq. (1), which result from the embedding. Then, a simplex σ is represented by the quantum state |σ , where the qubits corresponding to the vertices of σ are in state |1 , and all others are in state |0 . The boundary map ∂ is essential to extract the topological features and it can be encoded using Pauli X operators, which are switches that change state |0 into state |1 and vice versa.
The operator given in Eq. (5) maps a simplex |σ k of dimension k into a superposition of the (k − 1)-simplices that conform its boundary, which are none other than the simplices obtained by removing each of the vertices in σ k , Given two fixed scales ≤ , the membership oracle in Eq. (4) is used to implement the projection operators, P and P , onto the subspaces that encode the VR complexes S and S . The boundary operator and the projections are in turn used to build a persistent Dirac operator where ξ is an integer that is chosen according to the particular data at hand, and ∂ , k+1 is used to denote P ∂ k+1 P .
The parameter ξ in Eq. (6) is an eigenvalue of the persistent Dirac operator and its eigenspace corresponds to the kernel of a generalization of the graph Laplacian [23]. In particular, the multiplicity of this eigenvalue is the persistent Betti number β , k , which counts the number of k-dimensional holes in the point cloud that persist from scale up to at least scale .
To estimate a persistent Betti number, the quantum phase estimation algorithm is performed on the persistent Dirac operator as in [23] to derive the following probability distribution where λ s are the eigenvalues of the persistent Dirac operator in Eq. (6) and N its dimension, while l and M are parameters to be chosen according to the data. Next, one may use the Eq. (7) directly to estimate the persistent Betti numbers. Notice that if l and M are large enough, each of the terms in the sum in Eq. (7) is either equal to 1, if p = lλ s , or very close to 0, if otherwise. Therefore P(p) of Eq. (7) is proportional to the multiplicity of λ s at p = lλ s and 0 everywhere else. The desired persistent Betti number is then given by where the parameters l and M were chosen according to the eigenvalues of the persistent Dirac operators from Eq. (6). Indeed, the parameter l was picked as the inverse of the gap between ξ and the closest eigenvalue, then M was chosen as a power of 2 larger than the greatest eigenvalue (in norm) of the persistent Dirac operator times l.
In order to obtain all persistent Betti numbers at various scales and represent them onto persistence diagrams, one needs to consider an increasing sequence of scales 0 < ... < n , chosen according to the data. Then one implements the aforementioned quantum methodology to obtain the persistent Betti numbers for each pair i , j with 0 ≤ i ≤ j ≤ n. Since the estimations are independent, this can be done in parallel. Finally, once we have all possible Betti numbers, and the scales, which appear and disappear, one may depict them onto persistence diagrams. Indeed, if µ , k denotes the number of k−dimensional holes that appear in scale and disappear at scale , where β k is defined in Eq. (8) for various scales.

IV. Results
Two time series are considered to discover their shape properties. The first data is a simulated periodic discrete time series, and the second is a segment from an electroencephalography (EEG) measurement of a brain taken while the subject listened to music [28]. In both cases the task is to employ the quantum framework of Section III by first embedding the time series into a point cloud using the quantum delay embedding, and then examining the topological features of the corresponding embedded point clouds using the quantum persistent homology algorithm.

A. Periodic time series example
Consider the discrete time series based on the periodic function sin(2πt). Using a delay d = 2, τ = 1, the time series is embedded into the 2-dimensional point cloud as shown in Fig. 2. Notice that this function has one maximum (or minimum) per period, which translates to one hole in the corresponding embedded point cloud, constructed by the quantum Taken's delay embedding.
To construct the persistence diagram, an increasing sequence of twenty-five different scales starting at 0 = 0.0 < 1 = 0.1 < · · · < 24 = 2.4 with step size 0.1 taken into account. Using the quantum persistent homology algorithm, the persistent Betti numbers of dimensions 0 and 1 for each possible pair of scales are computed, and depicted in Fig. 4. As expected, a single one dimensional hole exists due to periodicity, and this is born at scale 1 and died at scale 2. On the other hand, the number of connected components, which is initially four, is reduced to one when the one dimensional hole is formed at scale 1.

B. An electroencephalogram example
A segment of fifty measurements from an electroencephalogram (EEG) signal while the subject listened to music is considered in Fig. 5.
The point cloud obtained using the quantum delay embedding algorithm for a delay τ = 8 and d = 2 is shown in Fig. 5. Next, the persistence diagrams are constructed using the quantum survive past scale 6 which indicates the presence of clusters in Fig. 5 (b).

V. Conclusion and Discussion
This paper makes possible for the first time, the topological data analysis of a time series by providing a quantum delay embedding of a time series into a point cloud. We introduced a new membership oracle for time series data, by changing the way in which the data is stored in the QRAM, and how it is used in the quantum topological data analysis algorithms to construct the relevant linear operators. The membership oracle provided here is for Vietoris-Rips complexes, but it is possible that a similar approach could be extended for other types of complexes dependent on the the data. For example, lazy witness complexes are similar to VR complexes and retain the same topological characteristics, but in order to check for membership it suffices to consider only a subset of the vertices. This could further reduce the amount of resources that the quantum algorithm requires to extract the persistence information, and we plan to examine this in the future.