Topological data analysis (TDA) based on persistent homology is an emergent field of data analysis.
The critical step of TDA is computing the persistent Betti numbers.
Existing classical algorithms for TDA have been limited because the number of simplices can grow exponentially in the size of data for higher-dimensional analysis.
In the context of quantum computation, it has been previously shown that there exists an efficient quantum algorithm for estimating the Betti numbers even in high dimensions.
However, the Betti numbers are less general than the persistent Betti numbers, and there have been no quantum algorithms that can estimate the persistent Betti numbers of arbitrary dimensions.
This paper shows the first quantum algorithm that can estimate the persistent Betti numbers of arbitrary dimensions.
Our algorithm is efficient for the construction of simplicial complexes such as the Vietoris-Rips complex and demonstrates exponential speedup over the known classical algorithms.

§ INTRODUCTION

Processing large data has become a highly demanding task in modern society.
Topological data analysis (TDA) is an emergent field of information processing based on topological and geometric methods [44, 17].
In particular,
TDA based on persistent homology  [18, 47, 16, 11, 36]
has been gathering a lot of attentions.
TDA based on persistent homology (hereafter, we just denote TDA when we mean that based on persistent homology)
reveals the “shape of data” with multi-scale analysis of topology.
A crucial property of persistent homology, which is favorable in practical situations, is its stability against the noise concerning how the data is sampled [13].
There have been numerous applications of TDA, including
the protein structure
the quantum many-body dynamics [40],
the cosmic web
[37], and
the string theory
to name a few.
Recently, combinations of persistent homology with supervised or unsupervised machine learning methods have also been actively studied [38].

In the procedure of TDA, data is first converted into a nested family of topological objects.
Such a topological object is called a simplicial complex, and a nested family of simplicial complexes is called filtration.
Then, we can study how topological invariants, such as the number of connected components, holes, voids, and their high-dimensional counterparts, change within the filtration.
Typically, topological invariants that persist longer are considered to be more significant than those persist shorter terms.
The behavior of topological invariants is summarized as diagrams or functions in the form such as the persistent Barcodes [22] and the persistent Landscapes [3].
Therefore, the critical steps of TDA are
(i) constructing a family of topological objects from the given data, and (ii) computing the multi-scale persistence of topological invariants in multiple dimensions.

There are challenges in classical TDA that arise from the combinatorial nature of the topological treatment of data.
Assume that the data is composed of $n$ points.
Then, the number of possible $q$-dimensional elements (i.e. $q$-simplices) that can contribute to topology is ${n \choose q+1}$.
(We say a simplex is $q$-dimensional if it is composed of $q+1$-vertices.)
Therefore, the number of all possible elements is $\sum_{q=0}^{n-1} {n \choose q+1} = \mathcal{O}(2^n)$.
The known classical algorithms for persistent homology works in polynomial time in the number of simplices [47, 34].
For constant dimensional analysis of persistent homology, classical algorithms work in polynomial time in $n$ because the number of constant-dimensional simplices is at most polynomial in $n$.
On the other hand, there can be exponentially many simplices for super constant dimensional analysis.
As a result,
performing such high-dimensional analysis of TDA is a difficult task for classical computers.
The way of reducing the size of simplicial complexes while keeping their homology unchanged is also actively studied [5].
However, such techniques are not enough to overcome the exponential growth of simplices because they need to have a list of all simplices as input to reduce the number of simplices.
Practically, high dimensional simplices are often ignored in classical TDA.

Existing quantum approaches for TDA.
Data learning tasks are also actively studied in the field of quantum computation.
Related to the topological data analysis,
Lloyd, Garnerone, and Zanardi [29]
proposed a quantum algorithm (LGZ algorithm) for estimating the (normalized) Betti numbers.
The $q$-th Betti number is defined as the dimension of a simplicial complex's $q$-th homology group.
The $q$-th Betti number represents the number of “$q$-dimensional holes”.
By estimating the Betti numbers for each step of the filtration, the LGZ algorithm enables us to learn about the topological structures of data.
A function that represents how the Betti numbers varies within the filtration is called a Betti function or a Betti curve [11].
Therefore, the LGZ algorithm enables us to approximately recover the Betti curve of arbitrary dimensions.
The LGZ algorithm demonstrates an exponential speedup over the known best classical algorithm for estimating the high-dimensional Betti numbers.
A proof of principle experiment of the LGZ algorithm has also been done [28].
Very recently, a NISQ-favorable version of the LGZ algorithm is presented [43].

Estimating the Betti numbers for each time of filtration is not enough to fully perform the topological data analysis using the theory of persistent homology.
To perform such a full TDA, it is crucial to have the ability to estimate the persistent Betti numbers.
The $q$-th $(t,s)$-persistent Betti number is
the number of $q$-dimensional holes that exist at scale parameter $t$ that still alive at $s$.
Because the $(t,t)$-persistent Betti number is just the usual Betti number, estimating the persistent Betti numbers is a more general task than estimating the Betti numbers.
It is shown in [32, 35] that the LGZ algorithm can be used to estimate the persistent Betti numbers of the zeroth dimension but fail in higher dimensions in general.
Moreover, the TDA of the zeroth dimension is not the region where we can exploit the benefit of quantum computation
because the classical algorithms run in polynomial time for constant dimensions.
Therefore, constructing a quantum algorithm for persistent Betti numbers for arbitrary dimensions has been a significant open problem for the quantum computational approach for TDA.

Our result.
We present a quantum algorithm for estimating the persistent Betti numbers of arbitrary dimensions for the first time.
We also provide error and complexity analysis. Our strategy is to map the problem of estimating the persistent Betti numbers into the problem of estimating the ground state density of a certain positive-semidefinite hermitian operator.
The positive-semidefinite operator we consider is the recently proposed persistent combinatorial Laplacian [45, 34].
Estimating the persistent Betti numbers allows one to recover the topological summary of data such as the persistent Barcodes, and this resolves the open question of Lloyd et al. [29].
We hope this opens the wide possibility of quantum TDA.
We show our algorithm using the quantum membership oracle that returns whether a simplex is contained in a simplicial complex or not.
This quantum oracle can be removed when we consider specific constructions of simplicial complexes.
For instances of problems that satisfy some promises, our algorithm is exponentially faster than the known classical algorithms for persistent Betti numbers.

Outline of the algorithm.
Because the persistent Betti number is more general than the Betti number, our quantum algorithm is more general than the LGZ algorithm.
We state our algorithm based on the recently developed formalism of the block-encoding and quantum singular value transformation (QSVT)  [25, 33].
The block-encoding is an embedding of matrices into unitaries using ancilla systems.
The quantum circuit used in our algorithm looks as below.

|0⟩      [wires=3,steps=4,style=dashed]

|0^m⟩      [wires=2]   U_Π         -1     [wires=2]   U^†_Π

|0^n⟩    [wires=2]  U_s

Here, $U_s$ is a unitary circuit for state preparation. $U_s$ prepares a state which is the uniform mixture over the eigenvectors of the target hermitian operator, which is the uniform mixture of all simplices at the same time.
$U_\Pi$ is a block-encoding of the projection onto the zero energy space of the persistent Laplacian.
The $m$-qubits are ancilla qubits for the block-encoding.
In the implementation of $U_\Pi$, we provide a new way of constructing the block-encoding of boundary operators.
The boundary operator is a certain operator that maps simplices into lower-dimensional simplices.

The measurement procedure with uncomputing $U_\Pi$, surrounded by the dashed box, is the “block-measurement” procedure introduced in [39].
It suffices to measure only a single qubit due to this block-measurement.

The probability of outputting $1$ with this quantum circuit approximates the persistent Betti number with normalization.

The implementation of $U_\Pi$ includes the inversion of matrices.
More precisely, our algorithm includes the implementation of the Schur complement of a matrix that contains the implementation of Moore-Penrose pseudo-inverse.
The implementation of the Schur complement with quantum computation may be of independent interest.
The fact that our algorithm includes the matrix inversion implies that our algorithm shares the characteristics of both the HHL algorithm [26] and the LGZ algorithm.
Technically, the usage of pseudo-inverse and the Schur complement enable us to properly treat the relationship between the bases of different times of filtration.

It is easy to construct a quantum algorithm for estimating the Betti numbers by slightly modifying our quantum algorithm because the persistent Betti number is more general than the Betti number.
The LGZ algorithm is based on a Hamiltonian simulation of the sparse matrix and the quantum phase estimation algorithm.
Compared to the LGZ algorithm, our algorithms have an exponential improvement in terms of precision of preparing output probability distribution that approximates the normalized Betti number.[
This improvement in precision can be seen in parallel with the exponential improvement of the quantum algorithm for the systems of linear equations of [10] over the original HHL algorithm [26].
Note that, however, the exponential improvement for the linear systems is for outputting a quantum state $\ket{x}$ that corresponds to the answer of linear equations, and not for outputting the sampling expectation values of $\ket{x}$.
The exponential improvement in precision for expectation values is shown to be impossible unless $\textsf{BQP=PP}$ [26].]
Note that, however, the exponential improvement does not contribute to improving the complexity of estimation due to the sampling error.
In [43], similar exponential improvement is presented independently for estimating the Betti numbers based on a stochastic rank estimation method.

The rest of the paper is organized as follows. In Section <ref>, we introduce the preliminaries on persistent homology and TDA. In Section <ref>, we introduce the block-encoding and quantum singular value transformation. Some proofs are given in Appendix <ref>. In Section <ref>, we provide a quantum algorithm for estimating the persistent Betti numbers, which is our main result.
In Section <ref>, we give a summary and discussions.

§ PRELIMINARIES ON PERSISTENT HOMOLOGY

In this section, we introduce persistent homology for simplicial complexes.
An abstract simplicial complex $K$ over a finite ordered set $V$ of vertices is a collection of subsets of $V$ such that for any $\sigma\in K$, if $\tau \subseteq \sigma$ then $\tau \in K$.
An element $\sigma\in K$ is called a $q$-simplex if $|\sigma|=q+1$.
For example, a 0-simplex is called a vertex, and a 1-simplex is called a line.
We denote the set of $q$-simplices of $K$ by $S^K_q$.

An oriented simplex
is a simplex in $K$ with a fixed ordering of vertices inherited from the ordering of $V$.
We denote an oriented simplex of $\sigma\in K$ as $\tilde{\sigma}$.
Let $\Bar{S}^K_q\coloneqq \{\tilde{\sigma}:\sigma\in S^K_q\}$ be a set of oriented $q$-simplices of $K$.
The $q$-th chain group $C^K_q$ of $K$ is the vector space over ${\mathbb R}$ with basis $\Bar{S}^K_q$ [
We work with chain groups with coefficients $\mathbb{R}$,
which is suitable for our quantum algorithm that relies on the Hodge theory and the persistent Laplacian.
The classical algorithms for persistent homology of [47] work for field coefficients such as $\mathbb{Z}_2$.
The Betti numbers of homology groups over $\mathbb{R}$ coefficients do not capture the torsion [30].
Nonetheless, this seems to be enough for many of the situations in TDA.
Let $n^K_q\coloneqq {\rm dim}(C^K_q)=|S^K_q|$ be the dimension of $C^K_q$.

The boundary map $\partial^K_q:C^K_q \rightarrow C^K_{q-1}$
is defined as

\begin{equation}
\partial^K_q([v_0,...,v_q]) \coloneqq
\sum_{i=0}^q
\end{equation}

for each $\tilde{\sigma}=[v_0,...,v_q]$, where the hat indicates that the vertex $v_i$ is omitted.
Then, the $q$-th homology group of $K$ is

\begin{equation}
H_q(K) \coloneqq {\rm ker}(\partial^K_q)/ {\rm im}(\partial ^K_{q+1}).
\end{equation}

and the $q$-th Betti number of $K$ is

\begin{equation}
\beta^K_q \coloneqq {\rm rank}(H_q(K)).
\end{equation}

The $q$-th combinatorial Laplacian $\Delta^K_q:C^K_q\rightarrow C^K_q$ is defined as follows:

\begin{equation}
\Delta^K_q \coloneqq
\underbrace{
\partial^K_{q+1} \circ (\partial^K_{q+1})^{*}
}_{=:\Delta^K_{q,{\rm up}}}
\underbrace{
(\partial^K_q)^{*}\circ \partial^K_q
}_{=:\Delta^K_{q,{\rm down}}},
\end{equation}

where $(\partial^K_q)^{*}:C^K_{q-1}\rightarrow C^K_q$ is the adjoint of $\partial^K_q$ under the inner product $\langle \cdot,\cdot \rangle_{C^K_q}$ such that $\Bar{S}^K_q$ is an orthonormal basis of $C^K_q$.
We have introduced $\Delta^K_{q,{\rm up}}, \Delta^K_{q,{\rm down}}$ for the convenience of notation.
The Betti number can be calculated as the nullity of the combinatorial Laplacian [20]:

\begin{equation}
\label{eq:betti}
\beta^K_q = {\rm nullity}(\Delta^K_q)
= \#\ {\rm of\ zero\ eigenvalues\ of\ } \Delta^K_q.
\end{equation}

This relationship comes from the following elementary result of Hodge theory:

Let $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^{n\times p}$, and assume $AB=0$.
Then we have

\begin{equation}
\rm{ker}(A)/\rm{im}(B) \cong \rm{ker}(BB^*+A^*A).
\end{equation}

Eq. (<ref>) follows using this claim observing that $\partial^K_q \partial^K_{q+1}=0$.

§.§ Filtration and Persistent homology

A sequence of nested subcomplexes of $K$

\begin{equation}
\emptyset= K_0 \subseteq K_1 \subseteq ... \subseteq K_m = K
\end{equation}

is called a filtration.
Similarly, we say a pair of simplicial complexes $K$ and $L$ is a simplicial pair if $K$ and $L$ are the simplicial complexes over the same ordered set $V$ such that $K\subseteq L$. We denote a simplicial pair by $K \hookrightarrow L$.
For a simplicial pair $K\hookrightarrow L$,
we choose the ordering $\{\sigma^L_q(i)\}_{i=1}^{n^L_q}$ such that $\{\sigma^L_q(i)\}_{i=1}^{n^K_q}=\{\sigma^K_q(i)\}_{i=1}^{n^K_q}$.
We obtain a map between the $q$-th homology group of $K$ and $L$ induced by the inclusion:

\begin{equation}
f^{K,L}_q : H_q(K)\rightarrow H_q(L).
\end{equation}

The $q$-th persistent homology group $H^{K,L}_q$ is defined as the image of the map.
The $q$-th persistent Betti number $\beta^{K,L}_q$ is defined as the rank of the map.
The persistent homology group consists of the homology group of $K$ that are still alive at $L$. That is,

\begin{equation}
H^{K,L}_q= {\rm ker}(\partial^K_q)/
\left( {\rm im}(\partial^L_{q+1})\cap{\rm ker}(\partial^K_q)\right).
\end{equation}

§.§ Persistent Laplacian

The persistent Laplacian is first introduced in [45].
Later, the property and implementations of the persistent Laplacian are further studied in [34]. Here, we introduce the $q$-th persistent Laplacian for a persistent pair $K \hookrightarrow L$.
Consider the subspace of $C^L_q$

\begin{equation}
C^{L,K}_q \coloneqq \{
c \in C^L_q : \partial^L_q(c) \in C^K_{q-1}
\}.
\end{equation}

Then, let $\partial^{L,K}_q$ be the restriction of the boundary operator $\partial^L_q$ to $C^{L,K}_q$ so that the image of $\partial^{L,K}_q$ is contained in $C^K_{q-1}$.
Then, the $q$-th persistent Laplacian is defined as

\begin{equation}
\Delta_q^{K,L}\coloneqq
\underbrace{
\partial_{q+1}^{L,K}\circ (\partial_{q+1}^{L,K})^{*}
}_{=:\Delta^{K,L}_{q,{\rm up}}}
\underbrace{
(\partial_{q}^K)^{*}\circ \partial_{q}^K.
}_{=\Delta^{K}_{q,{\rm down}}}
\end{equation}

It is shown in [34] that the nullity of the $q$-th persistent Laplacian equals to the $q$-th persistent Betti numbers:

For each integer $q\geq 0$,
$\beta_q^{K,L}={\rm nullity}(\Delta_q^{K,L})$

We provide a proof in Appendix <ref> for completeness.

In addition to the persistent Betti numbers from the nullity of the persistent Laplacian, it is suggested in [45] that the spectral property of the persistent Laplacian beyond the zero eigenvalue would provide useful information about the data.

Matrix representation.
We can give a matrix representation of  $\partial^K_q$ with respect to the canonical basis $\{\sigma^K_q(i)\}_{i\in [n^K_q]}$ of $C^K_q$ and $\{\sigma^K_{q-1}(i)\}_{i\in [n^K_{q-1}]}$ of $C^K_{q-1}$.
Then the matrix representation $B^K_q$ of $\partial^K_q$ is $n^K_{q-1}\times n^K_{q}$ matrix with entries from $\{-1,0,+1\}$.
$B^K_q$ is $(q+1)$-column sparse by definition.
The matrix representation of $\left(\partial^K_q\right)^*$ is simply $(B^K_q)^\mathsf{T}$.
Choose any basis of $C^{L,K}_{q+1}$ represented by a column matrix $Z\in \mathbb{R}^{n^L_{q+1}\times n^{L,K}_{q+1}}$ and let $B^{L,K}_{q+1}$ be the corresponding matrix representation of $\partial^{L,K}_{q+1}$.
It is shown in [34] that the matrix representation of $(\partial^{L,K}_{q+1})^*$ is $\left(Z^\mathsf{T}Z\right)^{-1}\left(B^{L,K}_{q+1}\right)^\mathsf{T}$.
Then the matrix representation of the persistent Laplacian is

\begin{equation}
\label{eq:matrixrep}
\Delta^{K,L}_q
\left(B^K_q\right)^\mathsf{T}B^K_q.
\end{equation}

In [45],
the authors have given two algorithms for computing the matrix representation of $\Delta_q^{K,L}$.
We adopt the second algorithm which uses the Schur complement.
The Schur complement is defined as follows.

Let $M\in \mathbb{R}^{n\times n}$ be a block matrix $ M =
\begin{pmatrix}
A & B \\
C & D \\
\end{pmatrix} $ where $D\in \mathbb{R}^{d\times d}$ is a block matrix.
The Schur complement of $D$ in $M$ is

\begin{equation}
M/D \coloneqq
A-BD^+ C,
\end{equation}

where $D^+$ is the Moore-Penrose pseudo-inverse of $D$.
Similarly, for $\emptyset \neq I \subseteq [n]$ and $\emptyset \neq J \subseteq [n]$, we denote the submatrix of $M$ consisting of rows and columns of indices of $I$ and $J$ by $M(I,J)$. Then, the Schur complement of $M(I,I)$ in $M$ is

\begin{equation}
M/M(I,I) \coloneqq
M([n]\backslash I,[n]\backslash I)-
M([n]\backslash I,I)M(I,I)^+ M(I,[n]\backslash I).
\end{equation}

It is shown in [34] that $ \Delta^{K,L}_{q,{\rm up}}$ can be implemented using the Schur complement:

Let $K\hookrightarrow L$ be a simplicial pair.
Assume that $n^K_q<n^L_q$ and let $I^L_K\coloneqq [n^L_q]\backslash [n^K_q]$.

\begin{equation}
\Delta^{K,L}_{q,{\rm up}} = \Delta^{L}_{q,{\rm up}}/\Delta^{L}_{q,{\rm up}}(I^L_K,I^L_K).
\end{equation}

§.§ Correspondence with Quantum computation

We can use the Hilbert space of $n$-qubits to represent a chain complex of a simplicial complex over $n$-vertices.
We can correspond a $q$-simplex to a $n$-bit string of Hamming weight $q+1$,
where the indices of 1s correspond to the indices of vertices of a simplex.
We denote $|\tilde{\sigma}_q\rangle$ where $\tilde{\sigma}_q$ is a $n$-bit string with Hamming weight $q+1$.
We denote the ${n \choose q+1}$ dimensional Hilbert space in
${\mathbb C}^{2^n}$ spanned by computational basis states of Hamming weight $q+1$ by ${\mathcal W}_q$.
Let ${\mathcal H}^K_q$ be the subspace of ${\mathcal W}_q$ spanned by $\{|\tilde{\sigma}_q\rangle : \tilde{\sigma}_q \in \bar{S}^K_q \}$.
We call $\{|\tilde{\sigma}_q\rangle : \tilde{\sigma}_q \in \bar{S}^K_q \}$ the canonical basis of ${\mathcal H}^K_q$.
The superposition of quantum states $\{|\tilde{\sigma}_q\rangle : \tilde{\sigma}_q \in \bar{S}^K_q \}$ is the quantum state representation of the $q$-chain.
The boundary operator maps as $\partial^K_q: {\mathcal H}^K_q \rightarrow {\mathcal H}^K_{q-1}$.
We have summarized the notations in Table <ref>.

Summary of notations

$K\hookrightarrow L$     A simplicial pair
$n$     The number of vertices
$\bar{S}^K_q$     The set of oriented $q$-simplices in $K$
$C^K_q$     The $q$-th chain group of $K$ with  coefficients $\mathbb{R}$
$n^K_q$     ${\rm dim} (C^K_q) = |S^K_q|$
$\{\sigma^K_q(i)\}_{i\in [n^K_q]}$     canonical basis of $C^K_q$
${\mathcal W}_q$     Subspace of ${\mathbb C}^{2^n}$ spanned by Hamming weight $q+1$ states

${\mathcal H}^K_q$     Subspace of ${\mathcal W}_q$ spanned by  $\{|\sigma^K_q(i)\rangle\}_{i\in [n^K_q]}$
$\{|\psi_q(i)\rangle\}_{i\in [n^K_q]}$      Eigenbasis of $\Delta^{K,L}_q$ (in ${\mathcal H}^K_q$) with eigenvalues $\lambda_1\leq \lambda_2\leq...\leq\lambda_{n^K_q}$

§ BLOCK-ENCODING AND QUANTUM SINGULAR VALUE TRANSFORMATION

In this section, we introduce the block-encoding of quantum operators and the quantum singular value transformation (QSVT).
We refer the reader to [25, 33] for more detail.
We use $\|\cdot\|$ as the spectral norm
and $|\cdot|_\diamond$ as the diamond norm.
The diamond norm is defined as $|\Lambda|_\diamond\coloneqq \underset{\rho}{\rm{max}} |(\Lambda\otimes \mathcal{I})(\rho)|_1$, where $|\cdot|_1$ is the trace norm.
We also use the notation of $\tilde{\mathcal{O}}(\cdot)$ which omits  $poly(\log n)$ and $poly(\log(\log\frac{1}{\epsilon}))$ factors.

Let $A=\tilde{\Pi}U\Pi$, where $\tilde{\Pi}$, $\Pi$  are orthogonal projectors and $U$ is a unitary.
We call such $U$ a projected unitary encoding of $A$.
a block-encoding of a quantum operator is defined as follows:

Suppose that $A$ is a $s$-qubit operator, $\alpha,\epsilon\in{\mathbb R}_+$, and $a\in{\mathbb N}$.
We say that the $(s+a)$-qubit unitary $U$ is an $(\alpha,a,\epsilon)$-block-encoding of A, if

\begin{equation}
\|A-\alpha(\langle 0|^{\otimes a}\otimes I)U(| 0\rangle^{\otimes a}\otimes I)\|\leq \epsilon.
\end{equation}

Such encoding is called a block-encoding because $U$ approximates the block matrix

\begin{equation}
\left[
\begin{array}{cc}
A/\alpha & . \\
. & . \\
\end{array}
\right].
\end{equation}

It is shown in [25] how to implement a unitary which realizes polynomial transformation of the singular values of the block-encoded matrices.
Let $A=\tilde{\Pi}U\Pi$, $d\coloneqq {\rm rank}(\Pi)$, $\tilde{d}\coloneqq {\rm rank}(\tilde{\Pi})$ and $d_{\rm min}\coloneqq {\rm min}(d,\tilde{d})$.
Then by the singular value decomposition,
there exists orthonormal bases $\{\ket{\psi_i}:i\in[d]\}$ and $\{|\tilde{\psi}_i\rangle:i\in[\tilde{d}]\}$ of ${\rm img}(\Pi)$ and ${\rm img}(\tilde{\Pi})$ such that

\begin{equation}
A=\sum_{i=1}^{d_{\rm min}} a_i |\tilde{\psi_i}\rangle\bra{\psi_i}.
\end{equation}

Then, the quantum singular value transformation (QSVT) of $A$ is defined
for odd or even polynomial function $f:{\mathbb R}\rightarrow {\mathbb C}$

\begin{equation}
\left\{
\begin{array}{l}
\sum_{i=1}^{d_{\rm min}} f(a_i)|\tilde{\psi_i}\rangle\bra{\psi_i},\ f\ {\rm is\ odd}\\
\sum_{i=1}^d f(a_i)|\psi_i\rangle\bra{\psi_i},\ f\ {\rm is\ even.}
\end{array}
\right.
\end{equation}

The following is shown in [25].

Let ${\mathcal H}_U$ be a finite dimensional Hilbert space and let $U$, $\Pi$, $\tilde{\Pi} \in {\rm End({\mathcal H}_U)}$ be linear operators on ${\mathcal H}_U$ such that $U$ is a unitary, and $\Pi, \tilde{\Pi}$ are orthogonal projectors.
Suppose $f\in {\mathbb R}[x]$ be a degree-$d$ odd or even polynomial satisfying $|f(x)|\leq 1$ for all $x\in [-1,1]$.
Then, there exists an ${\mathcal{O}(poly(d,\log(1/\delta)))}$-time classical algorithm that outputs
the classical description of a quantum circuit $U_{\Phi^+}$ and $U_{\Phi^+}'$ such that

\begin{equation}
\begin{cases}
\big(\langle 0|\otimes\tilde{\Pi}\big)
\big(| 0\rangle\otimes\Pi\big)\ if\ d\ is\ odd,\\
\big(\langle 0|\otimes\tilde{\Pi}\big)
\big(| 0\rangle\otimes\Pi\big)\ if\ d\ is\ even
\end{cases}
\end{equation}

\begin{equation}
\left\|f^{(\rm{SV})}(\tilde{\Pi}U\Pi)-P_{\Re}^{(\rm{SV})}(\tilde{\Pi}U\Pi)\right\|\leq \delta.
\end{equation}

$U_{\Phi^+}$ and $U'_{\Phi^+}$
can be implemented using ${\mathcal O}(d)$ use of $U$, $U^\dagger$, ${\rm C}_\Pi {\rm NOT}$, ${\rm C}_{\tilde{\Pi}} {\rm NOT}$ and other single qubit gates, where ${\rm C}_\Pi {\rm NOT}$ is defined as

\begin{equation}
{\rm C}_\Pi {\rm NOT} \coloneqq
X\otimes \Pi + I\otimes (I-\Pi).
\end{equation}

This is a slightly modified version of Corollary 18 of  [25].
We give a proof in
Appendix <ref>.
The corollary follows when $U$ is a block-encoding of $A$.

Let $U$ be an
$(\alpha,a,0)$-block-encoding of a $n$-qubit operator $A$. Let $f\in {\mathbb R}[x]$ be a degree-$d$ odd or even polynomial satisfying $|f(x)|\leq 1$ for all $x\in [-1,1]$.
Then, there exists an ${\mathcal{O}(poly(d,\log(1/\delta)))}$-time classical algorithm that output a description of a quantum circuit $U_{\Phi^+}$ s.t. $U_{\Phi^+}$ is a $(1,a+1,\delta)$-block encoding of $f^{(\rm{SV})}(A/\alpha)$.
Moreover, $U_{\Phi^+}$ can be implemented with $\mathcal{O}(d)$ use of $U$, $U^\dagger$ and $\mathcal{O}\left(ad\right)$ other elementary quantum gates.

In this paper, we use QSVT with three different polynomials.
First, we introduce the fixed-point amplitude amplification using polynomial approximations of the sign function (Lemma 25 of [25]):

Let $U$ be a unitary and $\Pi$ be an orthogonal projector such that $a|\psi_G\rangle=\Pi U |\psi_0\rangle$, and $a>\delta > 0$.
There is a unitary circuit $\tilde{U}$ such that

\begin{equation}
\left\|
\right\|
\leq \epsilon,
\end{equation}

which uses a single ancilla qubit and consists of ${\mathcal O}(\log{(1/\epsilon)}/\delta)$-use of $U$, $U^\dagger$, $C_\Pi NOT$,
$C_{|\psi_0\rangle \langle \psi_0 |}NOT$ and other quantum gates.

We use this theorem for state preparation of our algorithm in Section <ref>.

Next, we introduce the implementation of the Moore-Penrose pseudo-inverse.
Suppose $\tilde{\Pi}U\Pi=A$ and
$A=W\Sigma V^\dagger$ is a singular value decomposition, where $\Sigma$ is a diagonal matrix with non-negative and non-increasing entries.
Then the pseudo-inverse of $A$ is defined as
$A^+\coloneqq V\Sigma^+W^\dagger$,
where $\Sigma^+$ contains the inverse of the diagonal elements of $\Sigma$ except for $0$, which remains $0$.
We can implement the pseudo-inverse using the polynomial approximation of $1/x$ [25]:

Suppose that $A$ is a $n$-qubit positive-semidefinite hermitian operator and
$U$ is an $(\alpha,a,0)$-block-encoding of $A$.
Assume that the smallest non-zero eigenvalue of $A$ is $\lambda_{\rm{min}}$ and let  $0< 1/\kappa <\lambda_{\rm{min}}/\alpha$ and $0<\epsilon<1/2$.
Then there is a $d={\mathcal O}(\kappa \log{(\frac{\kappa}{\alpha\epsilon}}))$ and an efficiently computable $\Phi\in {\mathbb R}^d$ such that
$U_{\Phi^+}$ is a $(2\kappa/\alpha,a+1,\epsilon)$-block-encoding of $A^+$.

This is a slight modification of Theorem 41 of [25]
for the block-encoding of the positive-semidefinite operator.
A proof is given in Appendix <ref>.

We also use QSVT with a polynomial approximation of the rectangle function in Section <ref> in order to implement the projector.

§ QUANTUM ALGORITHM FOR PERSISTENT BETTI NUMBERS

This section presents a quantum algorithm for estimating the persistent Betti numbers of arbitrary dimensions for a simplicial pair $K \hookrightarrow L$.
We assume we have access to quantum membership oracles $O^K_q$ and $O^L_{q+1}$ that return whether a simplex is contained in $K$ and $L$ for any $\sigma\in\{0,1\}^n$ and $a\in \{0,1\}$, respectively, as

\begin{align}
O^K_q|\sigma\rangle |a\rangle &=
|\sigma\rangle |a\oplus f^K_q(\sigma)\rangle,\\
O^L_{q+1}|\sigma\rangle |a\rangle &=
|\sigma\rangle |a\oplus f^L_{q+1}(\sigma)\rangle,
\end{align}

where $f^K_q(\sigma)=1$ iff $\sigma\in \bar{S}^K_q$ and $f^L_{q+1}(\sigma)=1$ iff $\sigma\in \bar{S}^L_{q+1}$.

For a simplicial complex with $n$ vertices,
the number of all possible simplices is exponential in $n$.
However, we can efficiently implement such a membership function for some constructions of the filtration that is commonly used in TDA, as we see in Appendix <ref>.

§.§ Overview of the quantum algorithm

First, we overview our algorithm.

State Preparation.
We prepare the uniformly mixed state over the canonical basis of $\mathcal{H}^K_q$ i.e.
$\rho^K_q\coloneqq \frac{1}{n^K_q}\sum_{i\in [n^K_q]} |\sigma_q(i)\rangle\langle \sigma_q(i)|$.
$\rho^K_q$ is also a uniform mixture of the eigenvectors of $\Delta^{K,L}_q : \mathcal{H}^K_q \rightarrow \mathcal{H}^K_q $, i.e.,
$\frac{1}{n^K_q}\sum_{i\in [n^K_q]} |\psi_i\rangle\langle \psi_i|$, where we denote the eigenvectors of $\Delta^{K,L}_q$ as  $|\psi_1\rangle,...,|\psi_{n^K_q}\rangle$.
To prepare this state,
we first use a unitary that implements the Dicke state [4], which is the uniform superposition of all the Hamming weight $q+1$ computational basis states.
Then we use QSVT with respect to the sign function (fixed point amplitude amplification) to approximately prepare
$\frac{1}{\sqrt{n^K_q}}\sum_{i\in [n^K_q]} |\sigma_q(i)\rangle\otimes \ket{1}$.
We denote the error that comes from this QSVT as $\epsilon_{sign}$.
We copy the first register to another so that we obtain $\frac{1}{\sqrt{n^K_q}}\sum_{i\in [n^K_q]} |\sigma_q(i)\rangle\otimes\ket{1}\otimes |\sigma_q(i)\rangle$.
Finally, we trace out the latter registers, and we can approximately obtain $\rho^K_q$.

Implementation of the persistent Laplacian operator.
We would like to implement a block-encoding of the persistent Laplacian $\Delta^{K,L}_q$.
This is done as follows:

* Implement the block-encoding of $\partial^K_q$ and its adjoint. Then implement the product of these operators $\Delta^K_{q,down}=(\partial^K_q)^* \circ \partial^K_q$.

* Similarly, implement the block-encoding of $\Delta ^L_{q,up}=\partial^K_{q+1} \circ (\partial^K_{q+1})^*$.
The block-encoding of submatrices of $\Delta ^L_{q,up}$ can be implemented using the membership oracle.

* Implement the pseudo-inverse of $\Delta ^L_{q,up}(I^L_K,I^L_K)$ using QSVT about the polynomial approximation of the inverse function. We denote the error that comes from this QSVT as $\epsilon_{inv}$.

* Take the product of block-encoded operators so far and linearly combine to implement the block-encoding of $\Delta^{K,L}_q=\Delta^L_{q,up}/\Delta^L_{q,up}(I^L_K,I^L_K)+\Delta^K_{q,down}$.

Implementation of the projector, block-measurement, and sampling.
We implement the block-encoding of projection into the zero energy space of $\Delta^{K,L}_q$ and use the “block-measurement” [39] to identify the zero energy space.
The block-measurement is a technique to implement a particular quantum channel by using the trick of “uncomputation” and tracing out the ancilla register for block-encoding.
We use QSVT with respect to a polynomial approximation of the rectangle function in the implementation of the block-encoding of the projector, and we denote the error that comes from this QSVT as $\epsilon_{rect}$.

§.§ State Preparation

First, we explain how to implement the uniform mixture of $q$-simplex states of $K$

\begin{equation}
\rho^K_q=\frac{1}{n^K_q}
\sum_{i\in [n^K_q]} \ket{\sigma^K_q(i)}\bra{\sigma^K_q(i)}.
\end{equation}

For this purpose, we would like to approximately prepare the following state

\begin{equation}
= \frac{1}{\sqrt{n^K_q}}\sum_{i\in [n^K_q]} |\sigma^K_q(i)\rangle,
\end{equation}

which is the uniform superposition of the $q$-simplices in $K$.
In order to implement this state,
we use a unitary $P_q$ s.t.

\begin{equation}
\label{eq:dicke}
P_q \ket{0^n} = \frac{1}{\sqrt{n \choose q+1}}\sum_{x\in W_q} |x\rangle,
\end{equation}

where $W_q$ is the set of Hamming weight $q+1$ $n$-bit strings.

In [23],
the combinatorial number system [41] is used to implement such a unitary.
The uniform superposition of the Hamming weight $k$ states is also known as the Dicke state [14].

Instead of following the construction of [23] using the combinatorial number system,
we can use the construction of
[4]
for the Dicke state.
Then, we can implement $P_q$ with $\mathcal{O}(qn)$ gates and $\mathcal{O}(n)$ depth without using any ancilla qubits.
(The gate complexity of [23] is similar, but it additionally requires $\tilde{\mathcal{O}}(qn^2)$ time of computation for preparing a look-up table.)

Then by adding a qubit and applying the membership oracle $O^K_q$ to the quantum state of (<ref>), we get

\begin{equation}
\frac{1}{\sqrt{n \choose q+1}}
\left(\sum_{x\in S^K_q} |x\rangle|1\rangle +
\sum_{x\notin S^K_q} |x\rangle|0\rangle\right)
\sqrt{d^K_q}|\phi^K_q\rangle\ket{1} +
\frac{1}{\sqrt{n \choose q+1}}\sum_{x\notin S^K_q} |x\rangle|0\rangle
\end{equation}

where we have introduced $d^K_q\coloneqq n^K_q/{n \choose q+1}$. We call $d^K_q$ the $q$-simplex density of $K$.
Let $\tilde{\Pi}=I_n \otimes |1\rangle\langle 1|$, $\Pi=\ket{0^{n+1}}\bra{0^{n+1}}$ and $U=O^K_q P_q$.
Then $\tilde{\Pi}U\Pi=\sqrt{d^K_q}(|\phi^K_q\rangle\ket{1})\langle 0^{n+1}|$.
Now, we can use Theorem <ref> to implement a unitary $\tilde{U}$ s.t.

\begin{equation}
\label{eq:statepreparationunitary}
\left\||\phi^K_q\rangle\ket{1}- \tilde{U}|0^{n+1}\rangle\right\|
\leq \epsilon_{sign}
\end{equation}

with $\mathcal{O}
\left
\sqrt{1/d^K_q}\log{(1/\epsilon_{sign})} \right)$ use of $U$,$U^\dagger$, $\rm{C}_{\tilde{\Pi}}\rm{NOT}$, $\rm{C}_{{\Pi}}\rm{NOT}$, and single qubit gates.
Each of the $\rm{C}_{{\Pi}}\rm{NOT}$ gates, which are the generalized Toffoli gates, can be decomposed into $\mathcal{O}(n)$ number of elementary gates with an ancilla qubit [27].
By copying the $n$-qubit resister to another register, we get a state $|\tilde{\Psi}^K_q\rangle$ that is $\epsilon_{sign}$-close to

\begin{equation}
\label{eq:beforetraceout}
|\Psi^K_q\rangle \coloneqq
\frac{1}{\sqrt{n^K_q}}\sum_{i\in [n^K_q]} |\sigma^K_q(i)\rangle\ket{1}|\sigma^K_q(i)\rangle.
\end{equation}

By tracing out the latter two registers of $n+1$ qubits, we obtain a mixed state $\tilde{\rho}^K_q$ that approximates $\rho^K_q$.

We would like to give a upper bound on
$|{\rho}^K_q-\tilde{\rho}^K_q|_1$, which we use in the error analysis later.
From (<ref>),
$\tilde{U}\ket{0^{n+1}}$ can be written as
$\tilde{U}\ket{0^{n+1}}= a\ket{\psi}+b|{\psi^\perp}\rangle := |\tilde{\psi}\rangle$ for $a,b$ s.t. ${max}\{|1-a|,|b|\}\leq \epsilon_{sign}$, where
$\ket{\psi} \coloneqq |\phi^K_q\rangle\ket{1}$ and
$|{\psi^\perp}\rangle$ is a normalized state orthogonal to $\ket{\psi}$.

\begin{align}
\label{eq:error:statepreparation}
\left|{\rho}^K_q-\tilde{\rho}^K_q\right|_1
&\leq \left||\psi\rangle\langle\psi|-
|\tilde{\psi}\rangle\langle\tilde{\psi}| \right|_1
\leq 2\epsilon_{sign}^2.
\end{align}

The total cost of the state preparation is $\mathcal{O}\left(qn^2\sqrt{1/d^K_q} \log{(1/\epsilon_{sign})}\right)$ gates and
$\mathcal{O}\left(\sqrt{1/d^K_q}\log{(1/\epsilon_{sign})} \right)$ use of $O^K_q$.

§.§ Constructing block-encoding of persistent Laplacian

we see the implementation of the block-encoding of the persistent Laplacian

\begin{equation}
\Delta_q^{K,L}=
\underbrace{
\partial_{q+1}^{L,K}\circ (\partial_{q+1}^{L,K})^{*}
}_{\Delta^{K,L}_{q,{\rm up}}}
\underbrace{
(\partial_{q}^K)^{*}\circ \partial_{q}^K .
}_{\Delta^{K}_{q,{\rm down}}}
\end{equation}

Let us define

\begin{align}
\label{eq:delta1to4}
&\Delta_1\coloneqq \Delta^L_{q,{\rm up}}([n^K_q],[n^K_q])\\
&\Delta_2\coloneqq \Delta^L_{q,{\rm up}}([n^K_q],I^L_K)\\
&\Delta_3\coloneqq \Delta^L_{q,{\rm up}}(I^L_K,[n^K_q])\\
&\Delta_4\coloneqq \Delta^L_{q,{\rm up}}(I^L_K,I^L_K)
\end{align}

for convenience.
By Theorem <ref>,

\begin{equation}
\Delta^{K,L}_{q,{\rm up}}=\Delta^L_{q,{\rm up}}/\Delta^L_{q,{\rm up}}(I^L_K,I^L_K)
\end{equation}

§.§.§ Implementation of the block-encoding of $\partial^K_q$, $\partial^L_{q+1}$ and $\Delta^K_{q,\rm{down}}$

We see the implementation of the block-encoding of $\partial^K_q:\mathcal{H}^K_q\rightarrow \mathcal{H}^K_{q-1}$.
Let us consider the following quantum computation.

* Assume we have $\ket{x}$, where $x\in\{0,1\}^n$ with Hamming weight $q+1$.
Let $U_s$ and $U_t$ be the following unitaries on $\mathcal{O}(\log(n))$ qubits:

\begin{equation}
\label{eq:usut}
U_s:\ket{0}\rightarrow \frac{1}{\sqrt{q+1}}\sum_{s=0}^{q}|s\rangle, \quad
\frac{1}{\sqrt{n}}\sum_{t=0}^{n-1}\ket{t}.
\end{equation}

Then, prepare the following state by applying $U_s$ and $U_t$ to $\ket{x}\ket{0}\ket{0}$:

\begin{equation}
\frac{1}{\sqrt{n(q+1)}}\sum_{s=0}^{q}\sum_{t=0}^{n-1}\ket{x}\ket{s}\ket{t}.
\end{equation}

The unitaries $U_s$ and $U_t$ can be implemented using $\mathcal{O}(1)$ ancilla qubits and $\mathcal{O}(\log(n))$ gates.

* Let $C_t$ be a unitary that maps $\ket{x}\ket{t}\ket{0}\rightarrow \ket{x}\ket{g_t(x)\ket{t}\coloneqq\sum_{i=0}^{t-1} x_i}$ where $x_i\in \{0,1\}$ is the $i$-th bit element of $x$.
This can be implemented using a single ancilla qubit and $\mathcal{\tilde{O}}(n^2)$-gates using the quantum circuit for addition [7].
Then, apply this unitary and add $\ket{1}\ket{1}$ to get
\begin{equation}
\frac{1}{\sqrt{n(q+1)}}\sum_{s=0}^{q}\sum_{t=0}^{n-1}\ket{x}\ket{s}\ket{t}\ket{g_t(x)}\ket{1}\ket{1}.
\end{equation}

* Check whether $s=g_t(x)$ or not, and copy the $t$-th bit of $x$ to another register:

\begin{equation}
\frac{1}{\sqrt{n(q+1)}}\sum_{s=0}^{q}\sum_{t=0}^{n-1}\ket{x}\ket{s}\ket{t}\ket{g_t(x)}|\delta_{s,g_t(x)}\oplus 1\rangle|x_t\oplus 1\rangle,
\end{equation}

where $\delta_{s,g_t(x)}=1$ if $s=g_t(x)$ and $\delta_{s,g_t(x)}=0$ otherwise.
Note that the $t$ such that $\delta_{s,g_t(x)}=1$ and $x_t=1$ represents the index of the $s$-th non-zero bit of $x$.

* Copy the register of $|\delta_{s,g_t(x)}\oplus 1\rangle$ to another register and do uncomputation, and then swap the copied register and the original register, to get

\begin{equation}
\frac{1}{\sqrt{n(q+1)}}\sum_{s=0}^{q}\sum_{t=0}^{n-1}\ket{x}\ket{s}\ket{t}\ket{0}|\delta_{s,g_t(x)}\oplus 1\rangle|x_t\oplus 1\rangle\ket{0}.
\end{equation}

* Apply the membership oracle $O^K_q$ to the register of $\ket{x}$ to get

\begin{equation}
\frac{1}{\sqrt{n(q+1)}}\sum_{s=0}^{q}\sum_{t=0}^{n-1}\ket{x}\ket{s}\ket{t}\ket{0}|\delta_{s,g_t(x)}\oplus 1\rangle|x_t\oplus 1\rangle\ket{f^K_q(x)\oplus 1}.
\end{equation}

* Add phase factor $(-1)^{s}$ by applying a $Z$-gate to the register of $\ket{s}$, and flip the $t$-th bit of $x$ to get

\begin{equation}
\label{ep:beforepostselect}
\frac{1}{\sqrt{n(q+1)}}\sum_{s=0}^{q}\sum_{t=0}^{n-1}
\ket{\hat{x}_t}\ket{s}\ket{t}
\ket{0}
\dboxed{
|\delta_{s,g_t(x)}\oplus 1\rangle|x_t\oplus 1\rangle\ket{f^K_q(x)\oplus 1}}
\end{equation}

where $\hat{x}_t$ means that the $t$-th bit of $x$ is flipped.

Let us denote the whole unitary operation 1$\sim$6 above as $U'^K_q$.
If we project the qubits surrounded by dotted square in (<ref>) to $\ket{0}$, we get

\begin{equation}
\frac{1}{\sqrt{n(q+1)}}\sum_{s=0}^{q}
\ket{\hat{x}_{t(s)}}\ket{s}\ket{t(s)}
\ket{0}\ket{0}\ket{0}\ket{0},
\end{equation}

where we have denoted by $t(s)$ the $t$ s.t. $g_t(x)=s$ and $x_t=1$.
It can be seen that for $\forall x \in \bar{S}^K_q$,

\begin{equation}
( \bra{0^3}\otimes I_{n+a'-3})U'^K_q (\ket{0}^{a'}\otimes \ket{x})
\sum_{s=0}^{q}\frac{(-1)^s}{\sqrt{n(q+1)}}
\ket{\hat{x}_{t(s)}}\otimes \ket{s,t(s),0}\bra{0,0,0},
\end{equation}

for some $a'=\mathcal{O}(\log{(n)})$.
For $x\notin\bar{S}^K_q$,

\begin{equation}
(\bra{0^3}\otimes I_{n+a'-3})U'^K_q (\ket{0}^{a'}\otimes \ket{x})
\end{equation}

This works as a block-encoding of $\partial^K_q$
with factor $1/\sqrt{n(q+1)}$ and with some garbage.
This slightly deviates from the formalism of block-encoding due to the garbage.
The garbage is not good for the quantum singular value transformation later. Therefor, we further modify to fit the block-encoding formalism.
Let us define

\begin{equation}
U^K_q\coloneqq (U_s\otimes I)(U_t\otimes I) U'^K_q
\end{equation}

using $U_s$ and $U_t$ of (<ref>).
($U_s$ and $U_t$ are applied on the same registers as step 1, and $I$ is supposed to be an identity operator for the other registers than $U_s$ and $U_t$ act on, respectively.)
Then $U^K_q$ satisfies for $\forall x\in\bar{S}^K_q$,

\begin{equation}
(\bra{0}^a\otimes I_n)U^K_q (\ket{0}^{a}\otimes I_n)
\ket{x}
=\frac{1}{n(q+1)}\partial^K_q \ket{x}
\frac{1}{n(q+1)}
\sum_{s=0}^{q}
\ket{\hat{x}_{t(s)}}
\end{equation}

for some $a=\mathcal{O}(\log (n))$.
For $\forall x\notin\bar{S}^K_q$,

\begin{equation}
(\bra{0}^a\otimes I_n)U^K_q (\ket{0}^{a}\otimes I_n)
\ket{x}
\end{equation}

This means that $U^K_q$ is a $({n(q+1)},a,0)$-block-encoding of $\partial^K_q$.

It immediately follows that
$(U^K_q)^\dagger$ is a $({n(q+1)},a,0)$-block-encoding of $(\partial^K_q)^*$ because the matrix representation of $(\partial^K_q)^*$ is the transpose of the matrix representation of $\partial^K_q$ whose elements are real.
We can implement the block-encoding of $\Delta^K_{q,\rm{down}}$
using the following lemma:

If $U$ is an $(\alpha,a,\delta)$-block-encoding of a $s$-qubit operator $A$,
and $V$ is a $(\beta,b,\epsilon)$-block-encoding of a
$s$-qubit operator $B$ then $(I_b\otimes U)(I_a\otimes V)$ is an $(\alpha\beta,a+b,\alpha\epsilon+\beta\delta)$-block-encoding of $AB$.

Using this lemma, we can implement a unitary

a      [3,label style=yshift=0.5cm] U^K_q

a         [2](U^K_q)^†

which is a $({n^2(q+1)^2},2a,0)$-block-encoding of $\Delta^K_{q,\rm{down}}$.
(The second line, passing over $U^K_q$, means that this goes through $U^K_q$.)
From the construction above, $V^K_{q,\rm{down}}$ can be implemented with $\mathcal{\tilde{O}}(n^2)$ gates and $\mathcal{O}(1)$ use of $O^K_q$.

§.§.§ Implementation of the submatrices of $\Delta^L_{q,\rm{up}}$ and its Schur complement

We can similarly implement a unitary $V^L_{q,\rm{up}}$ which is a  $({n^2(q+2)^2},2b,0)$-block-encoding of $\Delta^L_{q,\rm{up}}:\mathcal{H}^L_q\rightarrow \mathcal{H}^L_q$ where $b=\mathcal{O}(\log (n))$ with using $\mathcal{\tilde{O}}(n^2)$ number of gates and $\mathcal{O}(1)$ number of $O^L_{q+1}$.
In order to implement the Schur complement $\Delta^L_{q,{\rm up}}/\Delta^L_{q,{\rm up}}(I^L_K,I^L_K)$, we would like to access the submatrices of $\Delta^L_{q,\rm{up}}$.
The membership oracle $O^K_q:\ket{x}\ket{0}\rightarrow \ket{x}\ket{f^K_q(x)}$ can be used to access those submatrices.
Let $\tilde{O}^K_q:\ket{x}\ket{0}\rightarrow \ket{x}\ket{f^K_q(x)\oplus 1}$.
Let us define

\begin{align}
&V_1\coloneqq (I\otimes\tilde{O}^K_q \otimes I_{2b}) (I_2\otimes V^L_q) (\tilde{O}^K_q  \otimes I\otimes I_{2b}),\\
&V_2\coloneqq (I\otimes\tilde{O}^K_q \otimes I_{2b}) (I_2\otimes V^L_q) (O^K_q  \otimes  I\otimes I_{2b}),\\
&V_3\coloneqq (I\otimes O^K_q \otimes I_{2b}) (I_2\otimes V^L_q) (\tilde{O}^K_q \otimes I\otimes I_{2b}),\\
&V_4\coloneqq (I\otimes O^K_q \otimes I_{2b}) (I_2\otimes V^L_q) (O^K_q \otimes I\otimes I_{2b}).
\end{align}

By applying $\tilde{O}^K_q$ with postselecting the ancilla register to $\ket{0}$, we can restrict the space to that is spanned by $\{|\sigma^K_q(i)\rangle\}_{i\in [n^K_q]}$.
Similarly, by applying ${O}^K_q$ with postselecting the ancilla register to $\ket{0}$, we can restrict the space to that is not spanned by $\{|\sigma^K_q(i)\rangle\}_{i\in [n^K_q]}$.
Therefore, $V_1$, $V_2$, $V_3$ and $V_4$
are $({n^2(q+2)^2},2b+2,0)$-block-encodings of $\Delta_1$, $\Delta_2$, $\Delta_3$ and $\Delta_4$, respectively.
$V_1 \sim V_4$ can be implemented using $\mathcal{\tilde{O}}(n^2
)$-gates and $\mathcal{O}(1)$-use of $O^K_q$ and $O^L_{q+1}$.

Pseudo-inverse of $\Delta_4$.
Let $\gamma_{\rm{min}}^q$ be the smallest non-zero eigenvalue of $\Delta_4$ and let $\kappa =\frac{n^2(q+2)^2}{\gamma_q}$ for $\gamma_q$ s.t. $0<\gamma_q<\gamma_{\rm{min}}^q$.
Then, using Theorem <ref>,
we can  implement a
block-encoding of $\Delta_4^+$
with $\mathcal{O}(\frac{q^2n^2}{\gamma_q}\log(\frac{1}{\gamma_q\epsilon_{inv}}))$ use of $V_4$, $V_4^\dagger$ and $\mathcal{\tilde{O}}(\frac{q^2n^2}{\gamma_q}\log(\frac{1}{\gamma_q\epsilon_{inv}}))$ other elementary gates.

We can implement a unitary $V_+$ which is a $(\frac{2n^4(q+2)^4}{\gamma_q},6b+7,n^4(q+1)^4\epsilon_{inv})$-block-encoding of $\Delta_2\Delta_4^+\Delta_3$ using Lemma <ref>.

§.§.§ Linear combination of block-encoding unitaries

Finally, we linearly combine the block-encoding (BE) of $\Delta_1$, $\Delta_2\Delta_4^+\Delta_3$ and $\Delta^K_{q,\rm{down}}$.
We implement such a linear combination in a way similar to Lemma 52 of [25].
What we have prepared so far are the following unitaries:

\begin{equation}
\begin{array}{llcl}
U_0\coloneqq V_1 &\Leftrightarrow &(\alpha_0\coloneqq n^2(q+2)^2,2b+2,0)-\rm{BE}\ \rm{of}\ &\Delta_1\\
U_1\coloneqq V_+ &\Leftrightarrow &(\alpha_1\coloneqq \frac{2n^4(q+2)^4}{\gamma_q},6b+7,n^4(q+2)^4\epsilon_{inv})-\rm{BE}\ \rm{of}\ &
\Delta_2\Delta_4^+\Delta_3\\
U_2\coloneqq V^K_q  &\Leftrightarrow &(\alpha_2\coloneqq n^2(q+1)^2,2a,0)-\rm{BE}\ \rm{of}\ &\Delta^K_{q,\rm{down}} ,
\end{array}
\end{equation}

where we have introduced $U_0,U_1,U_2$ and $\alpha_0,\alpha_1,\alpha_2$ for the convenience of notation.
What we would like to implement is a block-encoding of

\begin{equation}
\Delta^{K,L}_q= \Delta_1-\Delta_2\Delta_4^+\Delta_3+\Delta^K_{q,\rm{down}}.
\end{equation}

Let  $\beta = \alpha_0+\alpha_1+\alpha_2$ and $P_R, P_L$ be state preparation unitaries such that

\begin{align}
&P_R\ket{0}\rightarrow \frac{1}{\sqrt{\beta}}(\sqrt{\alpha_0}\ket{0}+\sqrt{\alpha_1}\ket{1}+\sqrt{\alpha_2}\ket{2}),\\
&P_L\ket{0}\rightarrow \frac{1}{\sqrt{\beta}}(\sqrt{\alpha_0}\ket{0}-\sqrt{\alpha_1}\ket{1}+\sqrt{\alpha_2}\ket{2}).
\end{align}

Suppose $W$ is a unitary such that for all $j\in{0,1,2}$ and any state $\ket{\psi}$,

\begin{equation}
\rightarrow
\ket{j} U_j\ket{\psi}.
\end{equation}

Let $\tilde{W}=(P_L^\dagger\otimes I_{6b+7}\otimes I_n)W(P_R\otimes I_{6b+7}\otimes I_n)$.
Then, this satisfies

\begin{equation}
\left\|\left(\langle0^{6b+9}|\otimes I_n\right) \tilde{W} \left(|0^{6b+9}\rangle \otimes I_n\right)
- \frac{\Delta^{K,L}_q}{\beta}
\right\|\leq
\frac{n^4(q+2)^4 \epsilon_{inv}}{\beta}
\end{equation}

and $\tilde{W}$ is a
$(\beta,6b+9,n^4(q+2)^4\epsilon_{inv})$-block-encoding of $\Delta^{K,L}_q$, and $\beta \in \mathcal{O}(\frac{q^4n^4}{\gamma_q})$.
Let us denote

\begin{equation}
\left(\langle0^{6b+9}|\otimes I_n\right) \tilde{W} \left(|0^{6b+9}\rangle \otimes I_n\right) = \tilde{\Delta}^{K,L}_q /\beta
\end{equation}

for $\tilde{\Delta}^{K,L}_q$ s.t. $\left\|\Delta^{K,L}_q-\tilde{\Delta}^{K,L}_q\right\|\leq n^4(q+2)^4 \epsilon_{inv}$.

§.§ Implementing the block-encoding of the projector

Using the block-encoding of $\Delta^{K,L}_q$, we implement the block-encoding of the projector onto the zero energy space of $\Delta^{K,L}_q$: $\Pi= \sum_{j:\lambda_j=0}
\ket{\psi_j}\bra{\psi_j}$.
Let $\lambda_{\rm min}^q$ be the smallest non-zero eigenvalue of $\Delta^{K,L}_q$.
In [25], the following polynomial approximation of the rectangle function is shown:

Let $\delta,\epsilon\in(0,1/2)$ and $t\in [-1,1]$. There exist an even polynomial $P\in {\mathbb R}[x]$ of degree ${\mathcal O}(\log{(1/\epsilon)}/\delta)$, such that $|P(x)|\leq 1$ for all $x\in[-1,1]$, and

\begin{equation}
\left\{
\begin{array}{ll}
P(x)\in [0,\epsilon], & \forall x\in[-1,-t-\delta]\cup [t+\delta,1],\ and\\
P(x)\in [1-\epsilon,1], & \forall x\in [-t+\delta,t-\delta].
\end{array}
\right.
\end{equation}

We take $t=\frac{\lambda_{\rm min}^q}{2\beta}$ and $\delta=\frac{\lambda_q}{2\beta}$ for such $\lambda_q$ that satisfies $0<\lambda_q<\lambda_{\rm min}^q$.
Because the block-encoding of $\Delta^{K,L}_q$ is not exact, we need to introduce the following lemma on the robustness of singular value transformation:

If $P\in\mathbb{C}[x]$ is a degree-$n$ polynomial satisfying the following conditions:

* $P$ has parity-($d$ mod 2),

* $\forall x \in [-1,1] : |P(x)|\leq 1$,

* $\forall x \in (-\infty,-1]\cup [1,\infty):|P(x)|\geq 1$,

* if $d$ is even, then $\forall x\in {\mathbb R}:P(ix)P^*(ix)\geq 1$

and moreover,
$A,\tilde{A}\in \mathbb{C}^{\tilde{d}\times d}$ are matrices of operator norm at most 1, then we have that

\begin{equation}
\left\|
P^{\rm SV}(A)-P^{\rm SV}(\tilde{A})
\right\|
\leq
\end{equation}

Using Lemma <ref> and  Corollary <ref>,
we can implement a unitary $\tilde{U}_\Pi$
which is a QSVT of $\tilde{\Delta}^{K,L}_q/\beta$ with respect to the rectangle function:

\begin{equation}
P^{\rm(SV)}\left(\tilde{\Delta}^{K,L}_q/\beta\right) =
\left(\langle0^{6b+10}|\otimes I_n\right) \tilde{U}_\Pi \left(|0^{6b+10}\rangle \otimes I_n\right).
\end{equation}

Using Lemma <ref> it can be seen that

\begin{equation}
\left\| P^{\rm(SV)}\left({\Delta}^{K,L}_q/\beta\right) -P^{\rm(SV)}\left(\tilde{\Delta}^{K,L}_q/\beta\right) \right\|
\leq
4d \sqrt{\|{\Delta}^{K,L}_q/\beta-\tilde{\Delta}^{K,L}_q/\beta\|},
\end{equation}

where $d\in \mathcal{O}(\beta\log(1/\epsilon_{rect})/\lambda_q)$.
$P^{\rm(SV)}\left({\Delta}^{K,L}_q/\beta\right)$ is $\epsilon_{rect}$-close to $\Pi$ in spectral norm.
$\tilde{U}_\Pi$ is a $(1,m\coloneqq6b+10,\epsilon_\Pi\coloneqq\epsilon_{rect} + 4d\sqrt{n^4(q+2)^4\epsilon_{inv} /\beta})$-block-encoding of $\Pi$.
It can be seen that

\begin{equation}
\mathcal{O}(n^2q^2\sqrt{\beta\epsilon_{inv}}\log(1/\epsilon_{rect})/\lambda_q)
\mathcal{O}(q^4n^4\sqrt{\epsilon_{inv}/\gamma_q}\log(1/\epsilon_{rect})/\lambda_q)
\end{equation}

§.§ Block-measurement

Finally, we use the block-measurement which is introduced in [39].
We would like to implement a quantum channel that is close to the following map

\begin{equation}
\label{eq:BMmap}
\rightarrow
|1\rangle\otimes\Pi |\psi\rangle
+|0\rangle\otimes (I-\Pi)|\psi\rangle
\end{equation}

using the approximate block-encoding of $\Pi$.
Let $U_{\Pi}$ be the exact block-encoding of $\Pi$ with $m$ ancilla qubits.
Then, consider the following  circuit $V$:

m    [wires=2]   U_Π         -1     [wires=2]   U^†_Π

where the CNOT gate refers to $X\otimes \ket{0^m}\bra{0^m}+I\otimes (I_m-\ket{0^m}\bra{0^m})$.
We can see that $V$ satisfies

\begin{equation}
(I\otimes\bra{0^m}\otimes I_n) V (\ket{0}\otimes \ket{0^m}\otimes I_n)
\ket{1}\otimes\Pi+\ket{0}\otimes (I_n-\Pi).
\end{equation}

This means that $V$
is the block-encoding of

\begin{equation}
X\otimes \Pi + I \otimes (I_n-\Pi).
\end{equation}

Let us define the  following quantum channel:

\begin{equation}
\Lambda_\Pi(\rho)\coloneqq
\sum_{i\in \{0,1\}^m}
(I\otimes\bra{i}\otimes I_n)
(I\otimes\ket{i}\otimes I_n),
\end{equation}

which can be obtained by tracing out the $m$-qubit ancilla register.
We also define

\begin{equation}
\Lambda_i(\rho)\coloneqq
(I\otimes\bra{i}\otimes I_n)
(I\otimes\ket{i}\otimes I_n).
\end{equation}

$\Lambda_0(\rho)$ realizes the quantum channel of (<ref>).

What we actually have is not an exact block-encoding of $\Pi$ but an approximate one.
Let $\tilde{V}$ and $\tilde{\Lambda}_\Pi$ be the quantum circuit and channel which are similarly implemented as $V$ and $\Lambda_\Pi$ using $\tilde{U}_\Pi$ instead of $U_\Pi$.

The block-measurement theorem gives an upper bound on the diamond norm between $\tilde{\Lambda}_\Pi$ and $\Lambda_0$

Let $\Pi$ be a projector, $V_\Pi=X\otimes\Pi+I\otimes (I_n-\Pi)$ be a unitary and $A$ be a hermitian matrix satisfying $\|\Pi-A^2\|\leq \epsilon$.
Also, $A$ has a block-encoding $\tilde{U}_\Pi$.
Then the channel

\begin{equation}
\tilde{\Lambda}_\Pi(\rho)\coloneqq
\sum_i
(I\otimes\bra{i}\otimes I_n)
\tilde{V}
(I\otimes\ket{i}\otimes I_n)
\end{equation}

approximates the quantum channel $\Lambda_0 (\rho)$ in diamond norm:

\begin{equation}
|\tilde{\Lambda}_\Pi-\Lambda_0|_\diamond\leq 4\sqrt{2}\epsilon.
\end{equation}

In our case, $U_\Pi$ is a $(1,m,\epsilon_\Pi)$-block-encoding of $\Pi$ and

\begin{equation}
\left\|\Pi-
\left((\bra{0^m}\otimes I_{n+1}) U_\Pi ( \ket{0^m}\otimes I_{n+1})
\right)^2
\right\|
\leq
2\epsilon_\Pi-\epsilon_\Pi^2\leq 2\epsilon_\Pi.
\end{equation}

Therefore, it follows from the block-measurement theorem that

\begin{equation}
\label{eq:error:BM}
|\tilde{\Lambda}_\Pi-\Lambda_\Pi|_\diamond\leq 8\sqrt{2}\epsilon_0.
\end{equation}

Let $U_\Pi$ be a $(1,m,0)$-block-encoding of $\Pi$ as above. The probability of measuring $1$ with respect to the block-measurement circuit $V$ of $U_\Pi$, and the ideal state preparation $\rho^K_q$ is

\begin{align}
p_1\coloneqq &
{\rm Tr}_{AB}
\left[
(|1\rangle\langle 1|\otimes I_{m+n})
\Big( \ket{0^{m+1}}\bra{0^{m+1}}\otimes \rho^K_q \Big)
\right]\\
{\rm Tr}_{A}
\left[
(|1\rangle\langle 1|\otimes I_{n})
\Lambda_0
\Big( \ket{0}\bra{0}\otimes \rho^K_q \Big)
\right]\\
\frac{|\{i:\lambda_i=0\}|}{n^K_q}=\frac{\rm{nullity}(\Delta^{K,L}_q)}{n^K_q},
\end{align}

where in the second line we have traced out the ancilla register of $m$-qubits.

The actual state preparation $\tilde{\rho}^K_q$ is $2\epsilon_{sign}^2$-close to $\rho^K_q$ in trace norm.

\begin{align}
\tilde{p}_1
\coloneqq&
{\rm Tr}_{AB}
\left[
(|1\rangle\langle 1|\otimes I_{m+n})
\tilde{V}
\Big( \ket{0^{m+1}}\bra{0^{m+1}}\otimes \tilde{\rho}^K_q \Big)
\tilde{V}^\dagger
\right]\\
{\rm Tr}_{A}
\left[
(|1\rangle\langle 1|\otimes I_{n})
\tilde{\Lambda}_{\Pi}
\Big( |0\rangle\langle 0|\otimes \tilde{\rho}^K_q \Big)
\right].
\end{align}

Let $\mathcal{M}=|1\rangle\langle1|\otimes I_n$.

\begin{align}
\left|
{\rm Tr}
\left[\mathcal{M}\Lambda_0(|0\rangle\langle 0|\otimes\rho^K_q)
\right]
{\rm Tr}
\left[\mathcal{M}\tilde{\Lambda}_{\Pi}(|0\rangle\langle 0|\otimes\tilde{\rho}^K_q)
\right]\right|\\
\left|
{\rm Tr}
\left[\mathcal{M}
\left(\Lambda_0(|0\rangle\langle 0|\otimes\rho^K_q)
\tilde{\Lambda}_{\Pi}(|0\rangle\langle 0|\otimes\rho^K_q)
\right)
\right]\right|
\left|
{\rm Tr}
\left[\mathcal{M}\tilde{\Lambda}_{\Pi}\left(|0\rangle\langle 0|\otimes(\rho^K_q-\tilde{\rho}^K_q\right)\right]
\right|\\
\left|
(\Lambda_0-\tilde{\Lambda}_{\Pi})\left(|0\rangle\langle 0|\otimes\rho^K_q\right)\right|_1
\left|
\rho^K_q-\tilde{\rho}^K_q
\right|_1\\
\left|
\rho^K_q-\tilde{\rho}^K_q
\right|_1\\
8\sqrt{2}\epsilon_\Pi + 2\epsilon_{sign}^2,
\end{align}

where we used
and (<ref>).
Here, $\epsilon_\Pi=\epsilon_{rect} + \mathcal{O}\left(

The total numbers of gates and use of oracles are as follows:

\begin{align}
&O^K_q : \mathcal{O}\left(\sqrt{\frac{1}{d^K_q}}\log\left(\frac{1}{\epsilon_{sign}}\right)\right)
\mathcal{O}\left(
\frac{q^4n^6}{(\gamma_q)^2\lambda_q}\log\left(\frac{1}{\epsilon_{rect}}\right)\log\left(\frac{1}{\gamma_q \epsilon_{inv}}\right)\right),\\
\frac{q^4n^6}{(\gamma_q)^2\lambda_q}\log\left(\frac{1}{\epsilon_{rect}}\right)\log\left(\frac{1}{\gamma_q \epsilon_{inv}}\right)\right),\\
&{\rm gates}:
\mathcal{O}\left(qn^2\sqrt{\frac{1}{d^K_q}}\log\left(\frac{1}{\epsilon_{sign}}\right)\right)
\tilde{\mathcal{O}}\left(
\frac{q^4n^8}{(\gamma_q)^2\lambda_q}
\log\left(\frac{1}{\epsilon_{rect}}\right)\log\left(\frac{1}{\gamma_q \epsilon_{inv}}\right)\right).
\end{align}

If $d^K_q=n^K_q/{n \choose q+1}\in \Omega(1/poly(n))$, $\gamma_{\rm min}^q \in \Omega(1/poly(n))$ and $\lambda_{\rm min}^q \in \Omega(1/poly(n))$,
we can take $\epsilon_{sign}, \epsilon_{inv}, \epsilon_{rect}$ so that $|p_1-\tilde{p}_1|$ is exponentially small while keeping our quantum algorithm efficient.
To summarize, we can state our main theorem as follows:

Let $K\hookrightarrow L$ be a simplicial pair that satisfies the following promises:
(P1) $K$ is $q$-simplex dense: $d^K_q=n^K_q/{n \choose q+1}\in \Omega(1/poly(n))$
(P2) $\Delta^L_{q,{\rm up}}(I^L_K,I^L_K)$ has inverse-polynomial gap: $\gamma_{\rm min}^q \in \Omega(1/poly(n))$
(P3) the $q$-th persistent Laplacian $\Delta^{K,L}_q$ has inverse-polynomial gap: $\lambda_{\rm min}^q \in \Omega(1/poly(n))$.

given access to membership oracles $O^K_q$ and $O^L_{q+1}$,
there is a quantum algorithm that output 1 with probability $\tilde{p}_1$ s.t. for any $\epsilon >0$

\begin{equation}
\left|
\frac{\beta^{K,L}_q}{n^K_q}-\tilde{p_1}
\right|\leq \epsilon
\end{equation}

which uses $\mathcal{O}(n)+\mathcal{O}(\log{n})$ qubits, and $\tilde{\mathcal{O}}\left( poly(n)\left(\log{\frac{1}{\epsilon}}\right)^2 \right)$ number of $O^K_q,O^L_{q+1}$ and other quantum gates.

As a consequence, we obtain the following corollary using the Chernoff-Heoffding inequality.

For any simplicial pair $K\hookrightarrow L$ that satisfies the promises (P1) $\sim$ (P3) of Theorem <ref>,
given access to membership oracles $O^K_q$ and $O^L_{q+1}$,
we can efficiently estimate $\frac{\beta^{K,L}_q}{n^K_q}$ with additive error $\epsilon$ with confidence $\eta$ by taking
samples from the quantum algorithm in Theorem <ref>.

§.§ Comparison with classical algorithms

We see the complexity of the classical algorithms for persistent homology.
The best known classical algorithm for computing the persistent Betti numbers of a simplicial pair $K\hookrightarrow L$  [34] runs in time $\mathcal{O}((n^L_q)^\omega)$ for $\omega < 2.373$ (assuming $n^L_q=\mathcal{O}(n^L_{q+1})$, which holds in many practical cases such as for Vietoris-Rips or Čech complexes).
For an approximation task, the best known classical algorithms for estimating the spectral densities of matrices
[9, 15, 31]
runs time linearly with the number of non-zero elements of the matrices.
The known classical algorithm for computing the matrix representation of the persistent Laplacian  [34] takes $\mathcal{O}((n^L_q)^\omega+n^L_{q+1})$ time.
Therefore, there are no known classical algorithms for computing or approximating the persistent Betti numbers efficiently when $n^L_{q}$ is exponential in the number of vertices $n$.

We can efficiently implement the membership functions for the construction of simplicial complexes such as the Vietoris-Rips complex and the lazy witness complex, as we see in Appendix <ref>.
Therefore, our quantum algorithm demonstrates exponential speedup over the best known classical algorithm for instances of problems that satisfy the promises of Theorem <ref>.

§ DISCUSSIONS

In this paper, we have given the first quantum algorithm for the persistent Betti numbers. Moreover, our algorithm is exponentially faster than the best-known classical algorithms.

Here, we give some discussions.

Betti numbers.
The LGZ algorithm [29] estimates the Betti numbers using the quantum phase estimation algorithm.
Based on our implementation of the quantum algorithm for the persistent Betti numbers,
we can immediately provide a quantum algorithm for the Betti numbers based on the block-encoding and QSVT by slightly modifying our algorithm.

In the estimation of the $q$-th Betti number of $K$, it is enough to have membership oracle $O^K_q$ and $O^K_{q+1}$. We can implement the block-encoding of $\Delta^K_q=\partial^K_{q+1}\circ (\partial^K_{q+1})^* + (\partial^K_q)^* \circ \partial^K_q$. Then we can implement a block-encoding of the projector into the null space and perform the block-measurement.
The gate complexity of implementing a quantum state which outputs $1$ with probability $\tilde{p}_1$ satisfies

\begin{equation}
|\tilde{p}_1 - {\beta^K_q}/{n^K_q}|\leq \epsilon
\end{equation}

is $\mathcal{O}\left(poly(n)\log{(1/\epsilon)}\right)$, which is an exponential improvement in terms of the error compared to the LGZ algorithm. Nonetheless, this exponential improvement does not actually improve the complexity in terms of error due to the sampling error.

NISQ algorithm for persistent Betti numbers.

Very recently, a NISQ algorithm for the Betti numbers is presented in [43]. Their algorithm is based on the following observations: (a) a boundary map can be represented as a sum of Pauli operators;
(b) Instead of using Grover's quantum search to implement the uniform mixture of the $q$-simplex states, a quantum rejection sampling can be used;
(c) a stochastic rank estimation can be used to estimate the Betti numbers instead of the quantum phase estimation.
Based on these observations, their quantum algorithm achieves a depth complexity that is linear in $n$ at the cost of the success probability $1/d^K_q$ of the rejection sampling.
In another very recent paper [6], the authors have pointed out the deep connection between the supersymmetric many-body system and (co)homology problems.
They studied the computational complexity of (co)homology problems.
Especially, they have pointed out the direct connection between TDA and the fermionic hard-core model.
Their implementation of the (co)boundary map is based on the fermionic annihilation operator, and it seems this has some similarities with the implementation of [43].
In [6], they have also proposed a variational quantum eigensolver (VQE) approach to TDA.

It is an open problem to construct a quantum algorithm for the persistent Betti numbers in a way that is more preferable for NISQ devices.

Toward quantum advantage for TDA.
Our algorithm is exponentially faster than the known best classical algorithm under some conditions.
However, the best classical algorithm can be improved.
In the field of quantum machine learning,
some examples of exponential improvements of classical algorithms
inspired by quantum algorithms have been found with the name of
“dequantization” [42, 8].
One nice feature of our algorithm, which inherits from the LGZ algorithm, is that it does not rely on the assumption of quantum access to large data.
Therefore, our algorithm avoids the subtlety
of using the quantum access (QRAM [24])  to the large data [2] and avoids certain routes of dequantization.
Recently in [21],
the authors have shown that a generalized task of estimating the Betti number is as hard as the one clean qubit model of quantum computation ().
Because the class  is believed to be intractable for classical algorithms,
they argue that the LGZ algorithm is safe against dequantization.
(It is unclear at the moment whether the Betti number estimation task itself is -hard or not.)
Our algorithm is also safe against dequantization in a similar sense because our task is more general than estimating the Betti numbers.
It is an important future direction to give more evidence that the quantum algorithm for persistent Betti numbers is truly intractable for classical algorithms.

Spectral analysis of persistent Laplacian.
It is suggested in [45, 34] that the spectral analysis beyond the nullity of the persistent Laplacian might give valuable information about the data. It is interesting to study more about the quantum computational approaches for the spectral analysis of persistent Laplacian.

TDA based on persistent homology is a rapidly growing field.
It is important to understand
for what king of actual problems the quantum algorithm for persistent Betti numbers effectively demonstrates its advantage.
In addition, it would also be interesting to combine our quantum algorithm with classical or quantum machine learning algorithms.
As the original motivation for a quantum computer was to simulate quantum mechanical systems [19], it would be interesting to simulate the topological nature of quantum mechanical systems using quantum TDA.

§ ACKNOWLEDGEMENT

RH thanks Tomoyuki Morimae, Seiichiro Tani, and Yuki Takeuchi for the helpful discussion. RH thanks Tomoyuki Morimae for his comments on the draft.

[1]
Mehmet E Aktas, Esra Akbas, and Ahmed El Fatmaoui.
Persistence homology of networks: methods and applications.
Applied Network Science, 4(1):1–28, 2019.

[2]
Scott Aaronson.
Read the fine print.
Nature Physics, 11(4):291–293, 2015.

[3]
Peter Bubenik et al.
Statistical topological data analysis using persistence landscapes.
J. Mach. Learn. Res., 16(1):77–102, 2015.

[4]
Andreas Bärtschi and Stephan Eidenbenz.
Deterministic preparation of dicke states.
In International Symposium on Fundamentals of Computation
Theory, pages 126–139. Springer, 2019.

[5]
Jonathan Ariel Barmak and Elias Gabriel Minian.
Strong homotopy types, nerves and collapses.
Discrete & Computational Geometry, 47(2):301–328, 2012.

[6]
Chris Cade and P Marcos Crichigno.
Complexity of supersymmetric systems and the cohomology problem.
arXiv preprint arXiv:2107.00011, 2021.

[7]
Steven A Cuccaro, Thomas G Draper, Samuel A Kutin, and David Petrie Moulton.
A new quantum ripple-carry addition circuit.
arXiv preprint quant-ph/0410184, 2004.

[8]
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and
Chunhao Wang.
Sampling-based sublinear low-rank matrix arithmetic framework for
dequantizing quantum machine learning.
In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory
of Computing, pages 387–400, 2020.

[9]
Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau.
Fast matrix rank algorithms and applications.
Journal of the ACM (JACM), 60(5):1–25, 2013.

[10]
Andrew M Childs, Robin Kothari, and Rolando D Somma.
Quantum algorithm for systems of linear equations with exponentially
improved dependence on precision.
SIAM Journal on Computing, 46(6):1920–1950, 2017.

[11]
Frédéric Chazal and Bertrand Michel.
An introduction to topological data analysis: fundamental and
practical aspects for data scientists.
arXiv preprint arXiv:1710.04019, 2017.

[12]
Alex Cole and Gary Shiu.
Topological data analysis for the string landscape.
Journal of High Energy Physics, 2019(3):1–31, 2019.

[13]
David Cohen-Steiner, Herbert Edelsbrunner, and John Harer.
Stability of persistence diagrams.
Discrete & computational geometry, 37(1):103–120, 2007.

[14]
Robert H Dicke.
Coherence in spontaneous radiation processes.
Physical review, 93(1):99, 1954.

[15]
Edoardo Di Napoli, Eric Polizzi, and Yousef Saad.
Efficient estimation of eigenvalue counts in an interval.
Numerical Linear Algebra with Applications, 23(4):674–692,

[16]
Herbert Edelsbrunner, John Harer, et al.
Persistent homology-a survey.
Contemporary mathematics, 453:257–282, 2008.

[17]
Herbert Edelsbrunner and John Harer.
Computational topology: an introduction.
American Mathematical Soc., 2010.

[18]
Herbert Edelsbrunner, David Letscher, and Afra Zomorodian.
Topological persistence and simplification.
In Proceedings 41st annual symposium on foundations of computer
science, pages 454–463. IEEE, 2000.

[19]
Richard P. Feynman.
Simulating physics with computers.
International Journal of Theoretical Physics, 21(6):467–488,
June 1982.

[20]
Joel Friedman.
Computing betti numbers via combinatorial laplacians.
Algorithmica, 21(4):331–346, 1998.

[21]
Casper Gyurik, Chris Cade, and Vedran Dunjko.
Towards quantum advantage for topological data analysis.
arXiv preprint arXiv:2005.02607, 2020.

[22]
Robert Ghrist.
Barcodes: the persistent topology of data.
Bulletin of the American Mathematical Society, 45(1):61–75,

[23]
Sam Gunn and Niels Kornerup.
Review of a quantum algorithm for betti numbers.
arXiv preprint arXiv:1906.07673, 2019.

[24]
Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone.
Quantum random access memory.
Physical review letters, 100(16):160501, 2008.

[25]
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe.
Quantum singular value transformation and beyond: exponential
improvements for quantum matrix arithmetics.
In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
of Computing, pages 193–204, 2019.

[26]
Aram W Harrow, Avinatan Hassidim, and Seth Lloyd.
Quantum algorithm for linear systems of equations.
Physical review letters, 103(15):150502, 2009.

[27]
Yong He, Ming-Xing Luo, E Zhang, Hong-Ke Wang, and Xiao-Feng Wang.
Decompositions of n-qubit toffoli gates with linear circuit
International Journal of Theoretical Physics, 56(7):2350–2361,

[28]
He-Liang Huang, Xi-Lin Wang, Peter P Rohde, Yi-Han Luo, You-Wei Zhao, Chang
Liu, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan.
Demonstration of topological data analysis on a quantum processor.
Optica, 5(2):193–198, 2018.

[29]
Seth Lloyd, Silvano Garnerone, and Paolo Zanardi.
Quantum algorithms for topological and geometric analysis of data.
Nature communications, 7(1):1–7, 2016.

[30]
Lek-Heng Lim.
Hodge laplacians on graphs.
arXiv preprint arXiv:1507.05379, 2015.

[31]
Lin Lin, Yousef Saad, and Chao Yang.
Approximating spectral densities of large matrices.
SIAM review, 58(1):34–65, 2016.

[32]
RHAJ Meijer.
Clustering using quantum persistent homology.
Master's thesis, 2019.

[33]
John M Martyn, Zane M Rossi, Andrew K Tan, and Isaac L Chuang.
A grand unification of quantum algorithms.
arXiv preprint arXiv:2105.02859, 2021.

[34]
Facundo Mémoli, Zhengchao Wan, and Yusu Wang.
Persistent laplacians: properties, algorithms and implications.
arXiv preprint arXiv:2012.02808, 2020.

[35]
Niels Neumann and Sterre den Breeijen.
Limitations of clustering using quantum persistent homology.
arXiv preprint arXiv:1911.10781, 2019.

[36]
Nina Otter, Mason A Porter, Ulrike Tillmann, Peter Grindrod, and Heather A
A roadmap for the computation of persistent homology.
EPJ Data Science, 6:1–38, 2017.

[37]
Pratyush Pranav, Herbert Edelsbrunner, Rien Van de Weygaert, Gert Vegter,
Michael Kerber, Bernard JT Jones, and Mathijs Wintraecken.
The topology of the cosmic web in terms of persistent betti numbers.
Monthly Notices of the Royal Astronomical Society,
465(4):4281–4310, 2017.

[38]
Chi Seng Pun, Kelin Xia, and Si Xian Lee.
Persistent-homology-based machine learning and its applications–a
arXiv preprint arXiv:1811.00252, 2018.

[39]
Patrick Rall.
Faster coherent quantum algorithms for phase, energy, and amplitude
arXiv preprint arXiv:2103.09717, 2021.

[40]
Daniel Spitz, Jürgen Berges, Markus K Oberthaler, and Anna Wienhard.
Finding universal structures in quantum many-body dynamics via
persistent homology.
arXiv preprint arXiv:2001.02616, 2020.

[41]
Abu Bakar Siddique, Saadia Farid, and Muhammad Tahir.
Proof of bijection for combinatorial number system.
arXiv preprint arXiv:1601.05794, 2016.

[42]
Ewin Tang.
A quantum-inspired classical algorithm for recommendation systems.
In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
of Computing, pages 217–228, 2019.

[43]
Shashanka Ubaru, Ismail Yunus Akhalwaya, Mark S Squillante, Kenneth L Clarkson,
and Lior Horesh.
Quantum topological data analysis with linear depth and exponential
arXiv preprint arXiv:2108.02811, 2021.

[44]
Larry Wasserman.
Topological data analysis.
Annual Review of Statistics and Its Application, 5:501–532,

[45]
Rui Wang, Duc Duy Nguyen, and Guo-Wei Wei.
Persistent spectral graph.
International journal for numerical methods in biomedical
engineering, 36(9):e3376, 2020.

[46]
Kelin Xia and Guo-Wei Wei.
Persistent homology analysis of protein structure, flexibility, and
International journal for numerical methods in biomedical
engineering, 30(8):814–844, 2014.

[47]
Afra Zomorodian and Gunnar Carlsson.
Computing persistent homology.
Discrete & Computational Geometry, 33(2):249–274, 2005.

§ PROOFS OF SECTION 2 AND 3

Proof of Theorem <ref>.
Choose any orthonormal basis of $C^{L,K}_{q+1}$ and let $B^{L,K}_{q+1}$ be the corresponding matrix representation of $\partial^{L,K}_{q+1}$.
\left(B^K_q\right)^\mathsf{T}B^K_q$ using (<ref>).
It follows using Claim <ref> that

\begin{equation}
\beta^{K,L}=\rm{dim}\left(
\rm{ker}(B^K_q)/\rm{im}(B^{L,K}_{q+1})
\right)
\end{equation}

with $B^K_qB^{L,K}_{q+1}=0$.

Proof of Theorem <ref>.
This is a slight modification of Corollary 18 of  [25].
Using Corollary 10 of [25],
we can find a degree-$d$ polynomial $P\in {\mathbb C}[x]$ s.t. $|\Re[P(x)]-f(x)|\leq \delta$ for all $x\in [-1,1]$ and $P$ satisfies the following conditions:

* $P$ has parity-($d$ mod 2),

* $\forall x \in [-1,1] : |P(x)|\leq 1$,

* $\forall x \in (-\infty,-1]\cup [1,\infty):|P(x)|\geq 1$,

* if $d$ is even, then $\forall x\in {\mathbb R}:P(ix)P^*(ix)\geq 1$,

with an ${\mathcal{O}(poly(d,\log(1/\delta)))}$-time classical algorithm.
By Theorem 17 of [25],
we can also find a parameter $\Phi=\{\phi_0,\phi_1,...,\phi_d\}\in {\mathbb R}^{d+1}$
in classical ${\mathcal{O}(poly(d,\log(1/\delta)))}$ time
s.t. the parametrized circuit $U_\Phi$

\begin{equation}
P^{({\rm SV})}(\tilde{\Pi} U\Pi)=
\begin{cases}
\tilde{\Pi} U_\Phi\Pi\qquad {\rm if}\ d\ {\rm is}\ {\rm odd}, \\
\Pi U_\Phi\Pi\qquad {\rm if}\ d\ {\rm is}\ {\rm even}.
\end{cases}
\end{equation}

Here, $U_\Phi$ is a unitary defined as

\begin{equation}
\begin{cases}
\left(e^{i\phi_{2j}(2\Pi-I)}U^\dagger
\right)\ {\rm for\ odd}\ d,\\
\prod_{j=1}^{d/2}
\left(e^{i\phi_{2j-1}(2\Pi-I)}U^\dagger
\right)\ {\rm for\ even}\ d.
\end{cases}
\end{equation}

Each of $e^{i\phi(2\Pi-I)}$ can be implemented using a single ancilla qubit and C$_\Pi$NOT as

1     e^-iϕZ      1

[wires=1]Π-1         [wires=1]Π-1

$\quad =|b\rangle\langle b|\otimes e^{(-1)^b i\phi(2\Pi-I)}$

for $b\in \{0,1\}$.
We can linearly combine $U_\Phi$ and $U_{-\Phi}$ by applying Hadamard gates to the ancilla qubit as

$\ket{0}$       H[wires=2,steps=3,style=dashed]$U_{\Phi^+}$      [2]  U_Φ       H    p

where $p$ means to postselect to $\ket{0}$.
Define $U_{\Phi^+}$ for odd $d$ and even $d$ as the above figure.
Let $\Pi'=\tilde{\Pi}$ for odd $d$ and let $\Pi'=\Pi$ for even $d$.
Then $P^{({\rm SV})}(\tilde{\Pi} U\Pi)=\Pi'U_\Phi\Pi$ and $P^{*({\rm SV})}(\tilde{\Pi} U\Pi)=\Pi'U_{-\Phi}\Pi$, and

\begin{equation}
P_\Re^{({\rm SV})}(\tilde{\Pi} U\Pi)
=\frac{P^{({\rm SV})}(\tilde{\Pi} U\Pi)+P^{*({\rm SV})}(\tilde{\Pi} U\Pi)}{2}
\end{equation}

This satisfies

\begin{equation}
\left\|f^{(\rm{SV})}(\tilde{\Pi}U\Pi)-P_{\Re}^{(\rm{SV})}(\tilde{\Pi}U\Pi)\right\|\leq \delta.
\end{equation}

It is clear from the construction that
can be implemented with ${\mathcal O}(d)$ use of $U$, $U^\dagger$, ${\rm C}_\Pi {\rm NOT}$, ${\rm C}_{\tilde{\Pi}} {\rm NOT}$ and single qubit gates.

Proof of Corollary <ref>.
This follows from the construction of $U_{\Phi^+}$ in the proof of Theorem <ref>.

Proof of Theorem <ref>.
This is a slight modification of Theorem 41 of [25]
for the block-encoding of the positive-semidefinite operator.
Let $\epsilon'=\frac{\alpha\epsilon}{2}$.
It is shown in [25, 33] that there exists an odd real polynomial $f(x)$ that $\frac{\epsilon'}{2\kappa}$-approximates the function $\frac{1}{2\kappa x}$ for $\forall x\in [-1,1]\backslash [-\frac{1}{\kappa},\frac{1}{\kappa}]$, and $|f(x)|\leq 1$ for $\forall x\in [-1,1]$ whose degree is $d = {\mathcal O}(\kappa \log{(\kappa/\epsilon')})$.  ($f(x)$ satisfies $f(0)=0$.)

$A=\sum_i \lambda_i |\tilde{\psi}_i\rangle\bra{\psi_i}$ be the singular value decomposition of $A$.

\begin{equation}
= (\bra{0}^a\otimes I_n)U(\ket{0}^a\otimes I_n)
\sum_i \lambda_i/\alpha |\tilde{\psi}_i\rangle\bra{\psi_i}
\end{equation}

By Corollary <ref>,
we can construct $U_{\Phi^+}$ that is a
QSVT with polynomial $P(x)$ that $\frac{\epsilon'}{2\kappa}$-approximates
$f(x)$ with $\mathcal{O}(poly(\kappa\log{(\kappa/\epsilon')}))$-time classical algorithm.
Then, because $\lambda_{min}/\alpha > 1/\kappa$, $U_{\Phi^+}$ satisfies

\begin{equation}
(\bra{0}^{a+1}\otimes I_n)U_{\Phi^+}(\ket{0}^{a+1}\otimes I_n)
\sum_i P(\lambda_i/\alpha) |\tilde{\psi}_i\rangle\bra{\psi_i}
\simeq
\sum_i \frac{\alpha}{2\kappa \lambda_i}|\tilde{\psi}_i\rangle\bra{\psi_i}
= \frac{\alpha}{2\kappa}A^+.
\end{equation}

$(\bra{0}^{a+1}\otimes I_n)U_{\Phi^+}(\ket{0}^{a+1}\otimes I_n)$ is an $(\frac{\epsilon'}{2\kappa}+\frac{\epsilon'}{2\kappa})$-approximation of  $\frac{\alpha}{2\kappa} A^+$.
This means $\frac{2\kappa}{\alpha} (\bra{0}^{\otimes a+1}\otimes I_n)U_{\Phi^+}(\ket{0}^{\otimes a+1}\otimes I_n)$ is $\frac{2}{\alpha}\epsilon'=\epsilon$ approximation of $A^+$.

§ EXPLICIT CONSTRUCTIONS OF THE MEMBERSHIP ORACLES

It is necessary
to be able to construct the membership functions so that we can implement our quantum algorithm efficiently
and exponentially faster than classical algorithms.
Although the number of possible $q$-simplices can be exponential in the size of the data,
we can implement the membership function if we can efficiently verify whether a simplex is contained at some point of the filtration.
There are many ways of constructing simplicial complexes from the given data, such as the point cloud, the digital image, or the network [36].

A $q$-skeleton of a simplicial complex $K$ is a union of $K_p$ for $p=\{0,1,...,q\}$ where $K_p$ is the collection of the $p$-simplices of $K$.
We can see that we are able to construct the membership functions efficiently for a class of the simplicial complex which is entirely determined by its 1-skeleton
such as the flag complex, clique complex, Vietoris-Rips complex, and lazy witness complex.
Besides such simplicial complexes, we are not for sure whether we can efficiently implement the membership functions such as the Čech complex and the Alpha complex.
In the following, we see some constructions of the membership functions.

Vietoris-Rips complex.
Vietoris-Rips (VR) complex is very commonly used in TDA. This is defined as follows.
Let $S$ be a set of $n$ points in $\mathbb{R}^d$.
Then, the VR complex with parameter $\varepsilon$ denoted by $\mathcal{R}_\varepsilon(S)$ is the set of all $\sigma\in S$ such that the largest distance between any of its points is at most $2\varepsilon$.
We can construct a VR complex first by computing the graph by connecting any of the vertices of which pairwise distance is less than $2\varepsilon$.
Then, the VR complex is the clique complex of that graph.

In order to check whether a set of vertices is contained in the VR complex, we just need to check all of the pairwise distances of the vertices are less than $2\varepsilon$, which can be done in $\mathcal{O}(n^2)$ time in the worst-case.

It is also possible to implement the membership function for the Vietoris-Rips filtration of the network input [1].
There, an undirected weighted graph is given as input. Then, filtration is built according to the parameter for the weight of the edges.
The membership verification can be done similarly using the adjacency matrix of the undirected graph of some parameters.

Witness complex.
A small subset of the point cloud is used as a `landmark' to reduce the number of simplices.
Let $S$ be the point set and let $L\subseteq S$ be the landmark set.
Then, the number of possible simplices of the witness complex is $2^{\mathcal{O}|L|}$.
A point $s\in S$ is called a weak $\varepsilon$-witness for $\sigma$ iff
$d(s,a)\leq d(s,b)$ for all $a\in \sigma$
and $b \in L\ \backslash\ \sigma$ where $d(x,y)$ is the distance points $x$ and $y$.
The weak witness complex at scale $\varepsilon$ is the simplicial complex with vertex $L$ such that all the faces of that simplicial complex $\sigma \subset L$ have a weak $\varepsilon$-witness in $S$.
The lazy weak witness complex at scale $\varepsilon$ has the same 1-skeleton as the weak witness complex.
We can efficiently verify membership for the lazy weak witness complex by calculating whether any pair of two points in $L$ has a weak $\varepsilon$-witness.