\section{Introduction}

Topology and geometry are among the most classic and fundamental areas in pure mathematics. Despite being abstract and sometimes counter-intuitive, their role in both science and engineering has been impactful. In physics, ideas from topology have provided a framework that explains phases of matter beyond Landau's symmetry-breaking theory~\cite{wen2004quantum}, such as the so-called topological phase of matter, and offered the prospect of fault tolerance with schemes of topological quantum computation~\cite{nayak2008non-abelian}. In engineering and applied sciences, for example, topological data analysis~\cite{wasserman2016topological, dey2022computational} employs techniques from topology to analyze and identify patterns or shapes of high-dimensional data. The foundation of computational conformal geometry has also been laid out~\cite{gu2003genus, gu2008computational, gu2002computing},  providing valuable tools for applications, such as mechanical designs, medical imaging, computer vision, and so on. 

At the same time, the notion of quantum computers~\cite{feynman2018simulating, shor1999polynomial, grover1996fast, arute2019quantum} has generated an entirely new frontier in computational science. By harnessing the enigmatic properties of quantum mechanics, such as entanglement and superposition, quantum computers possess the potential to handle specific challenging computational problems that are not thought  to be efficient within reach of classical computers. Some famous classic problems including factorization~\cite{shor1999polynomial}, unstructured search~\cite{grover1996fast}, and linear system solvers ~\cite{harrow2009quantum}, etc. The use of quantum computers has also been  extended to the modern context, such as machine learning and data science~\cite{lloyd2013quantum, lloyd2014quantum, wittek2014quantum, wiebe2012quantum, cong2019quantum, schuld2018supervised, schuld2014quest, schuld2020circuit, schuld2019machine, schuld2019quantum, havlivcek2019supervised}.  
 In Ref.~\cite{lloyd2016quantum},  quantum computational techniques were applied to topological data analysis; specifically, a quantum algorithm was constructed to estimate Betti numbers of a given simplicial complex, which  yields an exponential speedup compared to classical algorithms.

Inspired by the development in both quantum computation and   computational topology and geometry, here, we attempt to apply quantum approaches to advancing tools and solving problems in topology and geometry. As a small step,  we consider the problem of detecting the homology class of closed curves or 1-cycles.  As  explained below, the ability to detect homologically trivial curves provides a means to a related problem in the homotopy detection.  The precise statement of our main problem is as follows: given a closed surface, represented as a  triangular mesh, and a closed curve (or loop) on the surface, we want to know whether or not the curve is homologous to zero, i.e., trivial homologically.   Remarkably, given a sufficient number of qubits and the oracle that queries the curve, our algorithm can detect a given closed curve' homology class of with certainty at a constant time complexity.  We remark that reducing efficient classical solutions to even more efficient  quantum algorithms is also of interest from the complexity perspective. One such example is the 2D hidden linear function problem~\cite{bravyi2018quantum}.

The structure of this paper is as follows. First in Sec.~\ref{sec: preli}, we introduce and clarify some terms/terminologies that are relevant to our subsequent construction. We mention some assumptions that our algorithm relies on in Sec.~\ref{sec: compumodel}. In Sec.~\ref{sec:quantum}, we explicitly construct the quantum algorithm for detecting the homology class of closed curves. We conclude with some discussions and an outlook in Sec.~\ref{sec:conclude}. Along the way, we have also developed an efficient algorithm that creates a uniform superposition of computational basis states that are in a consecutive sequence; see the Appendix.

\section{Preliminaries}
\label{sec: preli}
\subsection{Overview of essential concepts in homology and cohomology}
\begin{figure}[htbp]
    \centering
    \includegraphics[width = .5\textwidth]{boundaryoperator.png}
    \caption{Illustration of chains and the boundary operation. The subscript of each boundary operator $\partial$ indicates which chain space it acts on (from the higher to lower order). }
    \label{fig: complex}
\end{figure}
Here, we give a quick overview of homology and cohomology concepts. In the language of algebraic topology, see, e.g., Ref.~\cite{hatcher2002algebraic}, we can treat a (discrete) surface as a simplicial complex, consisting of different dimensional simplices. The linear combinations of simplices, in which the coefficients belong to some ring $R$, form chains. Two common rings that are usually used are $\mathbb{Z}_2$ and $\mathbb{Z}$. A curve is then  a 1-chain in the discrete setting. The set of $k$-chains forms a linear vector space called the chain space, denoted by $C_k$. There is a map between two chain spaces  $C_k$ and  $C_{k-1}$  called the \textit{boundary map} $\partial_k: C_k \rightarrow C_{k-1}$, which maps a $k$-chain to its boundaries, as illustrated in Fig.~\ref{fig: complex}. 

A $k$-chain $\sigma_k$ is called \textit{closed} if $\partial_k \sigma_k = 0$, and it is also referred to as a $k$-cycle. A loop  is such an example.  A $k$-chain  $\sigma_k$ is called \textit{exact} if there exists a ($k$+1)-chain $\sigma_{k+1}$ such that
\begin{align*}
 \sigma_k=   \partial_{k+1} \sigma_{k+1}.
\end{align*}
We note that exact chains are closed. Two closed $k$-chains are equivalent if they differ by an exact $k$-chain. The equivalence relation divides $k$-chains into the so-called \textit{homology classes}, denoted as $H_k(M,\mathbb{Z})$ (where we assume the ring is $\mathbb{Z}$, for simplicity). Homology theory reflects the algebraic structure (note that connectivity between points is the key) of a given simplicial complex via the corresponding homology classes, or more precisely, homology groups. 

On the other hand, cohomology is  dual to homology. Given a $k$-chain $\sigma$, a $k$-cochain $w$ maps it to a real number $w(\sigma) \in R$. We can think of cohomology as the association of  elements in homology  with a real number.  
Due to the linearity of their vector spaces, it is convenient to use a basis  in homology and the dual basis in cohomology groups.
For a closed surface of genus $g$, the dimension of homology/cohomology basis is $2g$. Given a homology basis 
$\langle h_1, h_2, \dots, h_{2g}\rangle$,  the corresponding cohomology basis, denoted by as $\langle \Omega_1, \Omega_2, \dots, \Omega_{2g} \rangle$, can be constructed, such that
\[
    \int_{h_i} \Omega_j = \delta_{ij}.
\]

An arbitrary closed curve $\gamma$ is homologous to zero if and only if
\begin{align}
\label{eqn: zerohomology}
    \int_\gamma \Omega_{\alpha} = 0, \quad \forall \alpha \in \{1,2,\dots,2g\}.
\end{align}
More concretely, if the closed curves $\gamma$ has  $L$ oriented edges labeled by  $\vec{e}_j$, such that 
\[
    \partial_1 \left(\sum_{j=1}^L \beta_j\vec{e}_j \right)= \sum_{j=1}^L \beta_j (\partial_1 \vec{e}_j) = 0.
\]    
where $\beta_j \in \mathbb{Z}$. Then the above condition of being homologically zero means that for every $\alpha$,
\begin{equation}
    \Omega_\alpha(\gamma) = \sum_{j=1}^L \Omega_\alpha(\beta_j\vec{e}_j)= \sum_{j=1}^L \beta_j\Omega_\alpha(\vec{e}_j) = 0.
    \label{eqn:discrete}
\end{equation}
This formulation is more suitable for constructing of our quantum algorithm, presented later.

The run time for classical algorithms  is $\mathcal{O}(2g \cdot L)$~\cite{gu2003genus}, where $L$ is the number of edges (1-chains) on the closed curve $r$, and, therefore, the larger the loop is, the more computational time is required~ \cite{gu2002computing}. This seems reasonable, as whether a loop is homologically zero is a \textit{global} and topological property. However, we will provide a quantum algorithm below and show  that it can determine the homology property of a given closed curve (specified by some oracle ${\cal O}_r$ that only checks local properties) with running time $\mathcal{O}(2g)$, where $g$ is the genus of the surface. Thus, as we will show, if there are sufficient  ancillary qubits in the phase estimation step in our algorithm, then the homology class of the given closed curve could be determined in constant time, with respect to the size of the curve. 

\subsection{Mesh  Data Structure}
Despite the fact that surfaces are continuous, in real applications, such as digital geometry processing, they are usually represented as a triangulated polyhedron surface, namely a triangular mesh; see, e.g. Fig.~\ref{fig: bunnymesh} for illustration.
\begin{figure}[htbp]
  
    \begin{tabular}{l}
   
    (a) \\
    \includegraphics[width = 0.3\textwidth]{homobasis.png}\\
    (b) \\
    \includegraphics[width = 0.35\textwidth]{genus2.png}
    \end{tabular}
    \caption{Examples of genus-1 and genus-2 oriented surface, represented as a triangular mesh, with the corresponding homology basis. (a) Top figure: two 1-chains (red and blue) are homology basis. (b) Bottom figure: four 1-chains (red, blue, yellow, purple) are homology basis. }
    \label{fig: bunnymesh}
\end{figure}
A mesh $M = (V,E,F)$ consists of sets of vertices $V$, edges $E$, and faces $F$. We can think of it as a graph with vertices and edges that connect vertices. In terms of the algebraic topology, it is precisely a two-dimensional simplicial complex. 

We denote the set  of vertices as $V=\{v_0,v_1, ..., v_M\}$. For a given edge $e_i$ that connects two vertices $v_j,v_k$, for instance, a half-edge is an oriented edge $\vec{e_i} = [v_j,v_k]$, which implies the orientation $v_j \rightarrow v_k$. We simply denote $-\vec{e_i} = [v_k,v_j]$ for the reverse  order of the edge and vertices and use the vector notation $\vec{e}_i$ just to emphasize the orientation. The importance of half-edges is apparent for the purpose of computation with cohomology. 
Suppose $w$ is a  1-cochain, then for a given 1-chain (edge) $e_i $ connecting $v_j$ and $v_k$, we have $w([v_j,v_k]) = - w([v_k,v_j])$, i.e., $w(-\vec{e_i})=-w(\vec{e_i})$. An exact 1-cochain can be constructed from some 0-cochains $f$ by taking the coboundary map $d$:
\begin{align*}
    df([v_j,v_k]) = f(v_k) - f(v_j).
\end{align*}
Using this, we explain in Appendix~\ref{app:homologycohomology} how the cohomology basis (which is exact) can be constructed simply by subtracting some carefully initialized 0-form. 

\section{Setup for the quantum approach}
\label{sec: compumodel}
Here we describe several assumptions for the input of our quantum algorithm to be described in the next section.

\medskip \noindent {\bf Preprocessing Mesh:} We remark that we do not consider the problem of generating triangulated mesh here. We assume that such a step is done classically. \\

\medskip \noindent {\bf Homology and Cohomology Basis}: Similar to classical algorithms, we assume that the homology basis has been pre-computed classically, and the cohomology basis has also been constructed accordingly. In other words, we have predefined values for each edge (with orientation) of the mesh. In fact, for most such half-edges, these values are 0, except for a few  that connect those neighboring points on and off the homology basis, which can have values 1 or -1, dependent on the orientation of the half-edge; see also Appendix~\ref{app:homologycohomology}. For each cohomology basis $\Omega_{\alpha}$, denote the number of those non-zero values as $c_{\alpha}$. We further assume that two curves in the homology basis only intersects at no more than one vertex, which means that the two cohomology basis elements have nonzero value at no more than one common edge. Those conditions can always be satisfied, using a result of \cite{dey2007computing}.
Moreover, we assume the number edge $E$ is known and that the value of $c_{\alpha}$ (number of edges on which $\Omega_\alpha$ has a nonzero value) is known for all $\alpha$ via classical pre-processing.
\\

\medskip \noindent {\bf Encoding of Cohomology Basis in a Quantum State}: As described above, we can think of cohomology as the association of each half-edge (1-simplex) with a real number. Therefore, in principle, we could map these values to some quantum state with corresponding entries using $\sim  \mathcal{O}(\log_2(E))$ qubits, where $E$ is the total number of edges on the mesh. We remark that the values on most edges are zero, except for those edges that connect points on the homology basis to their neighboring points that are not on the basis~\cite{gu2002computing}; see also Appendix~\ref{app:homologycohomology}. We first need to map such a cohomology basis to the quantum state. A vector corresponding to a basis $\Omega_{\alpha}$ (with $\alpha=1,\dots, 2g)$ has the form 
\begin{align*}
    \vec{\Omega}_{\alpha} =[\omega_1^{(\alpha)},\omega_2^{(\alpha)},\dots]^T = [\pm 1,0, ...,\pm 1, ... 0 ]^T, 
\end{align*}
 where the component in the vector represents the value $\Omega_a(\vec{e_j})=\omega_j^{(\alpha)}$ on each edge. By choosing the orientations of the edges appropriately and using $\Omega_\alpha(-\vec{e_j})=-\Omega_\alpha(\vec{e_j})$, we can make the nonzero entries be uniformly +1. We can also re-arrange the edge labeling so that $\vec{\Omega}_1=[1,1,\dots,1,0,\dots,0]^T$ and $\vec{\Omega}_2=[0,\dots,1,1\dots,1,0,\dots,0]^T$, etc., where if $\vec{\Omega}_2$ overlaps with $\vec{\Omega}_1$ on an edge, we will arrange such that the particular overlapped edge corresponds to the last nonzero entry in $\vec{\Omega}_1$ and the first nonzero entry in $\vec{\Omega}_2$; otherwise, the first nonzero entry of $\vec{\Omega}_2$ will be the next entry to the last nonzero one in $\vec{\Omega}_1$.

Thus, for simplicity, we shall fix the orientation of edges such that all the nonzero entries are +1. That is those oriented edges $\vec{e}_i$ are regarded as the `positive' half-edges, $\Omega_\alpha(\vec{e}_i)=+1$. For any edge $e_i$, we can label it by some computational basis state, which we also denote as $|e_i\rangle$ (e.g. $|0101\dots\rangle$) and its orientation will be flagged by another ancillary qubit,
\begin{align}
\label{eqn:orientation1}
   \ket{\vec{e}_i} \equiv \ket{0}\ket{e_i}, \\
   \label{eqn:orientation2}
   \ket{-\vec{e}_i} \equiv \ket{1}\ket{e_i}.
\end{align}

One can easily see that the quantum state corresponds to each of the vector $ \vec{\Omega}_\alpha$ (normalized to 1) is just a uniform superposition of some basis states that encode the edges that are labelled in a consecutive way, and this superposition can be prepared with a very low cost, as we elaborate further in Appendix~\ref{sec: detailstate}. In the simplest scenario, for example, the number of non-zero values is a power of 2, and all those entries lie in ``perfect'' locations that could give us a simple, convenient way to prepare the corresponding quantum cohomology basi, using Hadamard gates $H^{\otimes n}$ only. For example, we consider the following vector of represent their cohomology basis values on four edges:
\begin{align*}
    \vec{x} = [1,1,0,0]^T,
\end{align*}
whose corresponding quantum state $\ket{x}$ is simply $\ket{0}\ket{+}$, which can be prepared simply by applying $I \otimes H$ to $\ket{0}\ket{1}$. 

However, we may not have those nice conditions in a general mesh. One certainly has the freedom to relabel edges. Still, one may need to locally modify the mesh so that the number of edges (with a nonzero value) in each cohomology basis is a power of two. Even if this is the  case, the nonzero entries may not necessarily range from (in the binary representation)  $|0000....0ab..c\rangle$ to $|0011..1ab..c\rangle$, and their superposition cannot be obtained simply by applying Hadamard gates. But even if it were the case, how could one prepare a corresponding superposition? One could use a two-step procedure of (1) Hadamard gates to create a uniform superposition from $|00...000..0\rangle$ to  $|0011..100..0\rangle$ and then (2) a quantum adder~\cite{cuccaro2004new} to add the appropriate shift $|00...0ab..c\rangle$, which is efficient. 

In Appendix~\ref{sec: detailstate}, we show that even without modifying the mesh structure, by choosing the appropriate labeling of edges (as described above), we can efficiently prepare all the cohomology basis states, as stated below.
\begin{claim}
\label{claim: ampenc}
A quantum state associated  $\ket{\Omega_{\alpha}}=\sum_j \omega_j^{(\alpha)}|e_j\rangle/\sqrt{c_\alpha}$ with the cohomology basis with $c_{\alpha}$ non-zero amplitudes can be prepared using a circuit of depth $\mathcal{O}(\log(c_{\alpha}))$.
\end{claim}
As we will point out later, given a mesh with $M$ points, then the number of edges used for each cohomological basis is small, i.e., $c_{\alpha} \ll M$. The cost to prepare the cohomology basis state is negligible and is of $\mathcal{O}(\log(c_{\alpha}))$, as detailed in Appendix~\ref{sec: detailstate} ,and thus  it does not incur substantial computational time. 

\medskip \noindent {\bf Quantum oracle for loop specification:} We remark that in this problem, we are interested in the homology property of a given closed curve $r$. The orientation of the curve is also important. We have assumed that certain orientation for each edge is fixed, so that  all the cohomology bases have a uniform sign in their nonzero components, as discussed earlier. Classically, we can specify the loop $r$ by listing  all its half-edges.   Naively, on quantum computers, we would like to have a single quantum state in a superposition of basis states that encode the edges on  $r$. 
But this requirement is too strong. Instead we would like to have a quantum oracle that we can use to probe the relation of an edge $e$ to the loop $r$. More precisely, it should be a half-edge $\vec{e}$ (where the arrow indicates a certain orientation, chosen for convenience as  positive). Its representation by a quantum state is illustrated in Eq.~(\ref{eqn:orientation1}) and the corresponding half-edge with the negative orientation $-\vec{e}$ is represented in Eq.~(\ref{eqn:orientation2}). 
The unitary ${\cal O}_r$, or oracle, associated with a given closed curve $r$, is designed so that, when queried with an input of an edge $|\vec{e}_i\rangle$ and an ancillary qubit,
\begin{align}
    {\cal O}_r \ket{\vec{e_i}}\ket{0} = 
    \begin{cases}
   \ket{\vec{e_i}} \ket{1} & \text{if half-edge $\vec{e_i} \in r$}, \\
    \ket{\vec{e_i}}\ket{0} & \text{if half-edge $\vec{e_i} \notin r$}, \\
   
    \end{cases}
    \label{eqn: oracle}
\end{align}
Essentially, the function of the oracle is to check whether a given half-edge $\vec{e_i}$ is on the curve $r$. However, the above functioning of the oracle did not take into account the possibly multiple appearances of some edges on the loop. If the above oracle is given, then we can only deal with the case where the coefficients of chain space belong to $\mathbb{Z}_2$. If we have access to the oracle that performs the following operation instead:
\begin{align}
     {\cal O}_r \ket{\vec{e}_i}\ket{00..0} =
    \begin{cases}
   \ket{\vec{e}_i} \ket{a} & \begin{tabular}{l}\text{if half-edge $\vec{e}_i \in r$ and} \\ \text{appears $a$ times,}\end{tabular} \\
    \ket{\vec{e}_i}\ket{00..0} & \text{if half-edge $\vec{e}_i \notin r$}, 
    \end{cases}
    \label{eqn: oracle1}
\end{align}
where the binary string $a = a_{{n_s}-1}... a_1 a_0$ denotes the time  the given half-edge $\vec{e_i}$ appears on $r$. (In fact, in the above, the top line already includes the bottom line as a special case with $a=0$.)
Then  we can deal with $\mathbb{Z}_{2^{n_s}}$ coefficients. Note that if $a = 0$ or $1$, then we recover the ($\mathbb{Z}_2$) oracle given by Eqn.~\ref{eqn: oracle}. We do not expect our algorithm can work in the case where an edge appears infinite times (for example, a loop winding around infinitely). Therefore, a reasonable assumption is  that each half-edge only appears a bounded number of times less than $2^{n_s} = K $ (with $K$ being a constant) or, alternatively, the oracle only checks the number of times modulo $K$. 


\section{Quantum Algorithm}
\label{sec:quantum}
In this section, we present our main result: a quantum algorithm for the homology detection of a loop. We will employ a Hadamard test procedure and combine it with quantum phase estimation to evaluate whether the sum described in Eq.~(\ref{eqn:discrete}) for each cohomology basis on the curve $r$ is zero or not.




\subsection{
A Hadamard test procedure for estimating phases}
Our primary method is built upon the techniques in Refs.~\cite{grover1996fast},~\cite{brassard2002quantum} and~\cite{kitaev1995quantum}, which were recently employed in the setting of quantum neural networks, e.g., see Ref.~\cite{zhao2019building}. We quickly review the routine as it will be generalized to form the main ideas of our quantum algorithm. 

Suppose we have some unitary $U$ that generates the following ($n$+1)-qubits state by $|0\rangle^{\otimes n+1}$: 
\begin{align}\label{eqn:phi}
   U \ket{0}^{\otimes n+1} = \ket{\phi} = \frac{1}{\sqrt{2}}(\ket{+}\ket{x} + \ket{-}\ket{y}),
\end{align}
where $\ket{x},\ket{y}$ are some $n$-qubits states. 
We can then use it to construct the Grover-like unitary $G = U S_0 U^\dagger (Z \otimes I^{\otimes n}) $~\cite{grover1996fast,brassard2002quantum,zhao2019building}, where $S_0 = I^{\otimes n+1} - 2 (\ket{0}\bra{0})^{\otimes n+1}$,  such that $\ket{\phi}$ can be written as a linear combination below,
\begin{align}
    \ket{\phi} = \frac{-i e^{i\theta}}{\sqrt{2}} \ket{w_+} + \frac{i e^{-i\theta}}{\sqrt{2}} \ket{w_-},
    \label{eqn: basestate}
\end{align}
in which $\ket{w_{\pm}} \sim \ket{0}(\ket{x}+\ket{y})/\Vert \ket{x}+\ket{y}\Vert ) \pm i\ket{1}(\ket{x}-\ket{y})/(\Vert\ket{x}-\ket{y}\Vert)$ are two eigenstates of $G$,
\begin{align}
    G \ket{w_{\pm}} = e^{\pm i 2\theta} \ket{w_{\pm}},
\end{align}
and the angle $\theta$ satisfies the relation
\begin{align}
    \sin(\theta) = \frac{ \sqrt{1+ \Re \braket{x|y} }}{\sqrt{2}},
\end{align}
or equivalently $\cos(2\theta) = -\Re \braket{x|y}$. This relation suggests that the real part of the overlap $\braket{x|y}$ is encoded in the phase $\theta$, which is related to the two eigenvalues. We also note that $e^{-i 2\theta} = e^{ i (2\pi - 2\theta)}$, and therefore, in principle, the phase estimation algorithm~\cite{kitaev1995quantum} allows us to estimate the value of $2\theta$. Furthermore, we do not need to prepare an eigenstate of $G$, as the phase estimation  will  give either $2\theta$ or $-2\theta$ randomly. Estimation of either of the values suffices. We will show shortly that the trivial closeness of a given curve $r$ on the triangulated mesh is encoded in the corresponding phase, and therefore could be revealed by looking at the outcome of the quantum phase estimation algorithm.


\subsection{Algorithm for Detecting Homology Class of a Closed Curve $r$}
\label{sec: algorithm}
We have described our quantum preliminaries  in Sec.~\ref{sec: compumodel}. In our algorithm, all qubits will be divided into five different quantum registers: (1) a single qubit anchor register (denoted by subscript $a$), which plays the same role as the first qubit of  Eqn.~(\ref{eqn:phi}); (2) an orientation flag (denoted by subscript $o$), which is used to indicate the orientation of the edge: $|0\rangle_o |e\rangle_e =|\vec{e}\rangle$ and $|1\rangle_o|e\rangle_e=|-\vec{e}\rangle$; (3) the edge data register (denoted by subscript $e$), such as $|e\rangle_e$ which we have just illustrated in (2); (4) the status register (denoted by subscript $s$), which is used to store the status from querying the oracle about a half-edge; and (5) the extra qubit (labelled by subscript $t$) to implementation rotation corresponding to the status register.
We remind that that for each cohomology basis there is an efficient unitary $U_{\alpha}$ to create the cohomlogy basis state $|\Omega_\alpha\rangle=U_\alpha\ket{0^{\otimes \log_2(E)}}_e=\sum_j \omega_j^{(\alpha)}|e_j\rangle_e/\sqrt{c_\alpha}$ in the edge (e) register without the orientation label (see Claim.~\ref{claim: ampenc} and Appendix~\ref{sec: detailstate}). Moreover, it is also easy to create a superposition of all edges, $\ket{\mathcal{E}} \equiv \frac{1}{\sqrt{E}} \sum_{i=1}^E \ket{e_i}_e =U_E|0\dots 0\rangle_e=H^{\otimes \log_2(E)}|0\dots 0\rangle_e$,
and we have assumed that the total number of edges (without counting the orientation) is a power of two. (If this is not the case, one can always add `fictitious' edges to pad the total number to be a  power of 2.) The goal is to construct a unitary process $U$ that takes $|0\dots0\rangle$ to $(|+\rangle |x\rangle + |-\rangle |y\rangle)/\sqrt{2}$.

We are now ready to describe the  procedure of our algorithm: \\


1. [Initialization]  First, we construct the following state:
\begin{align}
  |\varphi\rangle=\frac{1}{\sqrt{2}}\big(|0\rangle_a |-\rangle_o |\Omega_\alpha\rangle_e  + |1\rangle_a |+\rangle_o |\mathcal{E}\rangle_e \big), 
\end{align}
which can be created from $|0\rangle_a|0\rangle_o|0\dots 0\rangle_e$ by first applying $H\otimes H$ to $|0\rangle_a|0\rangle_o\rightarrow (|0\rangle_a+|1\rangle_a)|+\rangle_o/\sqrt{2}$, followed by a controlled operation $|0\rangle_a\langle 0|\otimes Z_o\otimes U_\alpha + |1\rangle_a\langle 1|\otimes I_o\otimes U_E$. 

We will keep the first qubit ($a$) in the $|0/1\rangle$ basis until the end, where we will turn it into $|+/-\rangle$.
 Equivalently, $|\varphi\rangle$ can be rewritten as 
\begin{align}
 \ket{\varphi} &=\frac{1}{\sqrt{2}}\Big(\ket{0}\frac{1}{\sqrt{2}}\sum_{i} \omega_i (|\vec{e}_i\rangle-|-\vec{e}_i\rangle) \label{eqn: desirestate}\\
 &+\ket{1}\frac{1}{\sqrt{2E}}\sum_{i=1}^E (|\vec{e}_i\rangle+|-\vec{e}_i\rangle) \Big). \nonumber
\end{align}
\\

2. [Applying oracle]. Next we append the status ancillas $\ket{00..0}_s$ and apply the black-box oracle ${\cal O}_r$ to the $e$ register (the $\log_2(E)$-qubit system) plus status register, we obtain:
\begin{eqnarray}
   &&|\varphi_1\rangle\equiv \mathcal{O}_r|\varphi\rangle\ket{00..0}_s=\frac{1}{\sqrt{2}}\Big[ |0\rangle_a \frac{1}{\sqrt{2 c_\alpha}}\sum_i \omega_i \big(|\vec{e}_i\rangle |{\rm st}(\vec{e}_i)\rangle_s  \nonumber\\
  && \quad -|\!-\!\vec{e}_i\rangle|{\rm st}(-\vec{e}_i)\rangle_s\big) 
   +
    |1\rangle_a \frac{1}{\sqrt{2 E}}\sum_i \big(|\vec{e}_i\rangle |{\rm st}(\vec{e}_i)\rangle_s\nonumber \\
  &&  \quad +|\!-\!\vec{e}_i\rangle|{\rm st}(-\vec{e}_i\big)\rangle_s)\Big], 
\end{eqnarray}
where ${\rm st}(\pm\vec{e}_i)$ is used to denote the status value after the query.
\\

3. [Conditional rotation]. Append an ancilla $\ket{0}_t$ (noting the subscript $t$) to  $|\varphi_1\rangle$ and apply a  rotation on qubit $t$, conditioned on the anchor qubit $a$ being $|0\rangle_a$ and the degree of rotation on the
status qubit $|{\rm st}(\pm\vec{e}_i)\rangle_s$, so that: $|0\rangle_t\rightarrow \ket{{\rm Rot}(\vec{e})}_t\equiv\frac{{\rm st}}{K}|0\rangle_t + \sqrt{1-{\rm st}^2/K^2}|1\rangle_t$. 

This operation only affects the part entangled with $\ket{0}_a$, which  becomes 
\begin{align}
& \frac{1}{\sqrt{2 c_\alpha}}\sum_i \omega_i \Big(|\vec{e}_i\rangle |{\rm st}(\vec{e}_i)\rangle_s \ket{{\rm Rot}(\vec{e}_i)}_t   - \\
  & \qquad |\!-\!\vec{e}_i\rangle|{\rm st}(-\vec{e}_i)\rangle_s \ket{{\rm Rot}(-\vec{e_i})}_t\Big).
\end{align}
The other part entangled with $|1\rangle_a$ remains unaffected.\\

4. [Oracle unquery] After the conditional rotation, we uncompute or unquery the status register by applying $\mathcal{O}_r$ one more time, assuming that its operation is addition bitwise. We then arrive at a state of the form  $|\varphi_{\rm 2}\rangle=(|0\rangle_a|x\rangle+|1\rangle_a|y\rangle)/\sqrt{2}$. The first part then becomes
\begin{align}
& |x\rangle\equiv\frac{1}{\sqrt{2 c_\alpha}}\sum_i \omega_i \Big(|\vec{e}_i\rangle  \ket{{\rm Rot}(\vec{e}_i)}_t   \nonumber \\
  & \qquad -|\!-\!\vec{e}_i\rangle \ket{{\rm Rot}(-\vec{e_i})}_t\Big)\otimes |0\dots0\rangle_s,
\end{align}
where we have factorized out the status register at the end. The second part becomes
\begin{align}
   |y\rangle\equiv \frac{1}{\sqrt{2 E}}\sum_i (|\vec{e}_i\rangle +|\!-\!\vec{e}_i\rangle)\otimes |0\rangle_t\otimes |0\dots0\rangle_s.
\end{align}
Here we can evaluate the inner product of $|x\rangle$ and $|y\rangle$, and we obtain
\begin{align}
    \langle x|y\rangle=&\frac{1}{\sqrt{4c_\alpha E}}\sum_i\omega_i\big(  \langle {\rm Rot}(\vec{e}_i)|0\rangle_t- \langle {\rm Rot}(-\vec{e}_i)|0\rangle_t\big)\nonumber\\
    =&\frac{1}{\sqrt{4c_\alpha E}\,K}\sum_i\omega_i\big[ st(\vec{e}_i)- st(-\vec{e}_i)\big]\nonumber\\
    =&\frac{1}{\sqrt{4c_\alpha E}\,K}\Omega_\alpha(r).
\end{align}
Note that ${\rm st}(\pm \vec{e}_i)$ is counting the number of times a half-edge $\pm\vec{e}_i$ appears on the curve $r$. 
$K=2$ reduces to the case where the coefficients in half-edges are in $\mathbb{Z}_2$. \\

5. [Hadamard test state] Apply the Hadamard gate to the anchor qubit $a$, and we have the final state,
$$  |\varphi_{\rm 3}\rangle=\frac{1}{\sqrt{2}}\big[\ket{+}_a\ket{x} + \ket{-}_a\ket{y}\big], $$
which  will be used for the Hadamard test. We denote the whole procedure from step 1 to step 5 as a unitary gate $U$, i.e., $|\varphi_3\rangle=U|0\rangle_a|0\rangle_o|0\dots0\rangle_e|0\dots 0\rangle_s|0\rangle_t$.
 What we have achieved  here is to translate our problem directly into the Hadamard test formalism described earlier, including the construction of the operator $G = U S_0 U^\dagger (Z \otimes I^{\otimes N})$, where $N=2+n_s+\log_2(E)$ with $n_s$ being the number of qubits in the status register.  

If the curve $r$ is closed trivially, which means that the sum $\Omega_\alpha(r)$ along the curve vanishes identically  (see Eqn.~\ref{eqn: zerohomology}), i.e., $\cos(2\cdot \theta') = 0$, implying that $2\cdot \theta' = \pi/2 \Rightarrow \theta' = \pi/4$. If we write $\theta' = 2\pi w' \Rightarrow w' = 1/8$, which can be represented by finite bits (more precisely, 3 bits as 1/8 = 0.001 in binary fraction). Therefore, ideally, it means that the phase estimation algorithm can output such a value with certainty, which again, can be used to verify whether or not $\Omega_\alpha(r)= 0$. Moreover, in the case that the curve $r$ is not homologically trivial, the value $\Omega_\alpha(r)$ can still be obtained from quantum phase estimation, given sufficient ancillas to encode the phase.  \\


6.  [Phase estimation]
We run the phase estimation algorithm for the operator $G$. As remarked earlier, it does not require us to prepare an eigenstate of $G$ and the phase estimation procedure will allow us to estimate $\pm2\theta$, which is sufficient for extracting $\Omega_\alpha(r)$. We then repeat the whole procedure for different cohomology basis state $|\Omega_{\alpha'}\rangle$. A curve that is homologically trivial will have all $\Omega_\alpha(r)\vert_{1}^{2g}=0$. Furthermore, complete information for all $\Omega_\alpha(r)\vert_{1}^{2g}$ determines the homology class of the curve $r$. However, whether we can determine nonzero values of $\Omega_\alpha(r)\vert_{1}^{2g}$ with sufficient accuracy remains to be checked.

\bigskip
\noindent {\bf Analysis of accuracy}. In the homologously trivial case, the phase can be represented exactly with finite bits and  our algorithm can return an exact result with certainty. However, we need to distinguish this case from the nontrivial cases and  there is indeed a finite gap in the phase between the two cases as we show below. 
Therefore, $\mathcal{O}(1)$-time running of quantum phase estimation can already determine whether or not the curve is homologous to zero. 
More specifically, the analysis of~\cite{brassard2002quantum} shows that generally, the phase register returns two closest values to our true phase value with high probability ($> 4/\pi^2$). In particular, the success probability of measuring best approximated phase value could be amplified to arbitrarily closed to 1 using additional qubits in phase registers~\cite{nielsen2002quantum}. Therefore, in principle, $\mathcal{O}(2g)$ (since we need to repeat the procedure for all cohomology basis $\{\Omega_i\}$) repetitions are enough to determine if the curve $r$, which is specified by $U_r$, is closed. 

Let us further analyze the precision, as in the case of homologously non-trivial curve, the value of angle $\theta'$ might be very closed to $\pi/4$, which means that the outcome of phase estimation circuit with low number of precision bits might not suffice to determine the phase and hence the value $\Omega_\alpha(r)$. 
If the curve $r$ is homologous to zero, we definitely have $\braket{x|y} = 0$. Since the value of $w_i$ is either -1, 0, or 1 (taking the orientation into account), if the curve is not homologously zero, then the minimum absolute value of such overlap is $|\braket{x|y}| = 1/(2\cdot \sqrt{c_{\alpha}\cdot E}\cdot K)$. More specifically, let:
\begin{align*}
   & |\cos(2\cdot \theta_{0})| = 0, \\
   & |\cos(2\cdot \theta_{m})| = 1/(2\cdot \sqrt{c_{\alpha}\cdot E}\cdot K),
\end{align*}
where $\theta_0$ refers to the case if the curve is homologically trivial, and $\theta_m$ refers to the smallest angle in the non-trivial case. We apply the following  inequality
\begin{align}
    |x-y| \geq |\cos(x)-\cos(y)|,
\end{align}
and obtain that $|2(\theta_0 - \theta_m)| \geq 1/(2 \cdot \sqrt{c_{\alpha}\cdot E} \cdot K)$. This means that there is a  gap $\Delta$ between the trivial phase value and non-trivial phase value. To distinguish between those phases, we require our phase estimation algorithm to have the error $\delta \leq \Delta$ (the smaller the better). Therefore, the number of qubits $p$ in the phase register required to have the desired accuracy is ${\Omega}(\log(1/\delta)) = {\Omega}(\log(\sqrt{c_{\alpha}\cdot E}\cdot K))$. We can simply choose $p = \lfloor \log(\sqrt{c_{\alpha}\cdot E} \cdot K) \rfloor + k$, where $k$ is some integer. We recall that $c_{\alpha}$ is the number of edges with non-zero values for a given cohomology basis element $\Omega_\alpha$. This number is usually much smaller than $E$, which is the total number of edges on the mesh. We also have the condition that $K$ is bounded above. Assume that the mesh has $M$ vertices, then $E$ is $\mathcal{O}(M)$, which means that $\log(\sqrt{ c_{\alpha}\cdot E }\cdot K)$ is  $\mathcal{O}\big(\log(M)\big)$. Therefore, in our algorithm, as long as we can have enough qubits $\sim \mathcal{O}(\log(M))$ 
in the phase estimation algorithm, then the accuracy $\Delta$ is always guaranteed. 

We summarize our main result with the following theorem. 
\begin{theorem}[Homology detection]
Given a closed triangular mesh $M$ of genus $g$, cohomology basis $\langle \Omega_1, \Omega_2, ..., \Omega_{2g} \rangle$, and quantum oracle $U_r$ that specifies a given closed curve $r$. There exists a quantum algorithm that determines the homology class of  $r$ in $\mathcal{O}(2g)$ time. 
\end{theorem}

In comparison, the classical running time is $\mathcal{O}(2g\cdot L)$ where $L$ is the `size' of the curve $r$, i.e., the number of edges on it, as 
one needs to sum up all the values $\omega_i$ on the all edges $\vec{e}$ of  $r$ for all cohomology basis elements $\Omega_{\alpha=1\dots 2g}$.  Our quantum algorithm substantially improve the time complexity from linear (in $L$) to constant.  We note that our algorithm  works even if the given curve has a self-crossing, which can be regarded as a sum of 1-cochains that are  loops. 


If two closed curves corresponding to two chains $\sigma_1$ and $\sigma_2$ are homologous, i.e., in the same equivalence class, then they differ by an exact 2-chain. This means for any 1-cochain $\omega$, we have   $\omega (\sigma_1) = \omega (\sigma_2)$. If we decompose the 1-cochain $\omega$ into the basis $\{\Omega_i\}_{i=1}^{2g}$ then for each basis element  we need to have $\Omega_i (\sigma_1) = \Omega_i(\sigma_2)$. We can  compute $\Omega_i(\sigma_1)$ and $\Omega_i(\sigma_2)$ directly and separately using our quantum algorithm (given the respective oracles) to compute $\Omega_i(\sigma_{1/2})$ and check if they equate each other for all $i=1,\dots,2g$.

\subsection{Potential Applications}
\subsubsection{Homotopy Detection}
Given the ability to efficiently determine the homology class of a closed curve, it is natural to seek  applications of the quantum algorithm. 
Here we point out an instance that also arises in the computational conformal geometry and topology context ~\cite{gu2002computing, gu2003genus}, i.e. the so-called homotopy detection. The statement of the problem is the following.
\begin{problem}[Homotopy Detection]
Given a closed triangular mesh M, two loops $\gamma_1$ and $\gamma_2$ through a base point p. Verify whether or not $\gamma_1$ is homotopic to $\gamma_2$, $\gamma_1 \sim \gamma_2$.
\end{problem}
Such a problem also has a linear time classical solution~\cite{lazarus2012homotopy}.
While homology groups are commutative, homotopy groups are usually non-commutative; therefore, homotopy can generally be harder to deal with than homology, such as computing its groups. There are also hard problems related to homotopy. For example,  the shortest word problem ~\cite{parry1992growth} for a given homotopy class is NP-hard ~\cite{yin2011computing}. While we do not know whether we could completely solve the homotopy detection problem with a constant time algorithm, we observe an essential property that, \textit{two loops are homotopic to each other implying that they are homologous} (the reverse may not be true). In particular, in the homotopy detection problem, if $\gamma_1 \sim \gamma_2$, then $\gamma = \gamma_1 \cdot \gamma_2^{-1}$ is homotopic to $e$, i.e, the loop is trivial (constant loop). Thus, if $\gamma \sim {e}$, then $\gamma$ is necessarily homologous to $0$ as well.  As we can only check whether the curve is homologous to $0$, we can apply our algorithm to check the converse, i.e., we can ascertain the case when two curves (on a closed surface) are \textit{not} homotopic to each other by verifying that the loop $\gamma$ is not homologous to zero. 



In Ref.~\cite{gu2008computational},  an alternative classical solution to the homotopy detection problem was described. The key idea is that, we first compute a finite portion of the universal covering space $\tilde{M}$ of $M$. We then lift $\gamma_1 \cdot \gamma_2^{-1}$ to $\tilde{M}$, and denote the lifted path as $\gamma$. If $\gamma$ is a loop, then $\gamma_1 \sim \gamma_2$.  However, converting the above solution into an efficient quantum algorithm is an open problem. 


\subsubsection{Winding Number Estimation}
It is pretty interesting that aside from the homology detection problem, the algorithm that we use in this paper (integration of cohomology basis) can be employed to estimate the numbers of times that a loop winds around the torus. 
\begin{figure}
    \centering
    \includegraphics[width = 0.35\textwidth]{winding.png}
    \caption{A loop r winds around the torus 5 times. }
    \label{fig: winding}
\end{figure}

In Fig.~\ref{fig: winding}, denote the homology and cohomology basis as $(h_1,h_2)$ and $(\Omega_1, \Omega_2)$ (see Fig.~\ref{fig: bunnymesh}a). W.O.L.G., let $h_1$ be the red curve, and $h_2$ be the blue curve. The integration of cohomology basis along the winding loop is:
\begin{align}
    \int_r \Omega_1 = 1, \ \
    \int_r \Omega_2 = m,
\end{align}
where $m$ is the number of times that the given loop $r$ winds around the torus. Given an oracle, the algorithm developed in Sec.~\ref{sec: algorithm} can estimates the above integral (more precisely, a discrete summation). Therefore, our algorithm can estimate the winding numbers of the given loop $r$. In this case, as shown in Fig.~\ref{fig: winding}, no half-edge appears twice, therefore, the simpler  $\mathbb{Z}_2$-version of the oracle (i.e., $K=2$) is sufficient.





\section{Discussion and Conclusion}
\label{sec:conclude}
Topology and geometry are very rich and deep area of mathematics and their  applications  to science and engineering have been increasingly broadened due to the connection from the profound mathematical foundation to classical computational geometry algorithms. This, in turn, yields powerful tools to solve many practical problems. Quantum computer is also undergoing a second wave of fast development, and concurrently, the  potential power and applicability of quantum computers have always been an important question to address. Our work has added to the few existing works and extended the application of quantum computation to  computational topology, in particular, the problem of homology detection. Our quantum method relies on important observation: cohomology assigns real values to half-edges of a mesh, which could be stored efficiently using a logarithmic number of qubits. The summation along a loop (which is specified by an oracle) is done using the orthogonal relation of basis states $\ket{e_i}$. Key tools include the Hadamard test, amplitude amplification, and quantum phase estimation. 

Even though the particular problem we have considered is not a hard one from classical complexity's perspective (i.e., with a running time ${\cal O}(L)$ in the number of edges on the curve), our quantum algorithm achieves a constant time complexity, yielding a substantial speedup.  We note that there are other problems where classical solutions are efficient, but the quantum algorithms are even more efficient, such as the 2D hidden linear function problem, where the classical solution  requires at least a logarithmic depth whereas the quantum solution requires a shallow depth~\cite{bravyi2018quantum}. This problem  was further generalized to yield an exponential separation between the classical fan-out circuits and  shallow-depth quantum circuits~\cite{watts2019exponential}.  

We have also pointed out the potential application of our quantum algorithm in the homotopy detection problem.  As described above, the homotopic relation implies homology relation, therefore, we could check the homology condition as a mean to rule out the non-homotopic relation. We have also suggested an open problem regarding how to construct a quantum algorithm that elevates the (classical) universal-covering-space approach provided in~\cite{gu2008computational}. 

We now discuss an important open point of our work, which appears in most oracle-based quantum algorithms, including Grover's search, namely, the construction of the oracle itself. We have assumed that the oracle ${\cal O}_r$ could efficiently query the half-edge, but left aside the detail of such an oracle. How to implement the oracle explicitly (and efficiently) is an open question. We remark that a mesh is mathematically a graph, therefore, and we could in principle use the graph Laplacian to encode the necessary information of the mesh (i.e., connectivity), for example, in a QRAM~\cite{giovannetti2008quantum}, then  the connectivity (plus proper orientation) could be accessed coherently. If an explicit construction for the oracle ${\cal O}_r$ were known, then we could deal with an arbitrary curve on the graph, which in turn might  provide more flexibility for applications.  


Homology and homotopy detection are critical for a broad range of applications. In medical imaging, for example, virtual colon cancer detection, the colon surface is reconstructed from CT-images. Due to the segmentation error, there are many fake handles and tunnels on the reconstructed surfaces. It is crucial to detect these spurious topological noises and remove them by topological surgery using homological method~\cite{Hong2006, zeng2010supine}. In wireless sensor network field, homology is applied for coverage and hole detection in sensor networks~\cite{1440933} and location tracking~\cite{yin2015decentralized}. It is interesting to see potential applications of quantum algorithms on these practical problems. As a final remark, our work mainly deals with the first homology group $H_1$ and it is natural to ask how to extend our algorithm to deal with arbitrary homology group $H_k$ ($k>1$), which is left for future exploration.



\section*{Acknowledgements}
The research reported in this work was partially supported  by the National Science Foundation  under Grants No. PHY 1915165 (T.-C.W.), No. 2115095 (X.D.G.), and No. 1762287 (X.D.G.), as well as NIH R21EB029733 (X.D.G.).









