Quantum Walks on Simplicial Complexes and Harmonic Homology: Application to Topological Data Analysis with Superpolynomial Speedups
Ryu Hayakawa Kuo-Chin Chen Min-Hsiu Hsieh



 YITP-24-46
Deep multi-prototype capsule networks
    [
    Received September 15, 1996; accepted March 16, 1997
========================================================



Deep multi-prototype capsule networks
    [
    Received September 15, 1996; accepted March 16, 1997
========================================================





Incorporating higher-order interactions in information processing enables us to build more accurate models, gain deeper insights into complex systems, and address real-world challenges more effectively. However, existing methods, such as random walks on oriented simplices and homology, which capture these interactions, are not known to be efficient. This work investigates whether quantum walks on simplicial complexes exhibit quantum advantages. 
We introduce a novel quantum walk that encodes the combinatorial Laplacian, a key mathematical object whose spectral properties reflect the topology of the underlying simplicial complex. Furthermore, we construct a unitary encoding that projects onto the kernel of the Laplacian, representing the space of harmonic cycles in the complex's homology. Combined with the efficient construction of quantum walk unitaries for clique complexes that we present, this paves the way for utilizing quantum walks to explore higher-order interactions within topological structures. Specifically, our construction requires 𝒪(n^3log(1/ϵ)/λ_k) gates, where n is the number of vertices, λ_k is the smallest non-zero eigenvalue of the combinatorial Laplacian, and ϵ is the error of the projection, for the implementation of projector onto the harmonic cycles. Thus our results achieve superpolynomial quantum speedup with quantum walks without relying on quantum oracles for large datasets.

Crucially, the walk operates on a state space encompassing both positively and negatively oriented simplices, effectively doubling its size compared to unoriented approaches. Through coherent interference of these paired simplices, we are able to successfully encode the combinatorial Laplacian, which would otherwise be impossible. This observation constitutes our major technical contribution. 
We also extend the framework by constructing variant quantum walks. These variants enable us to: (1) estimate the normalized persistent Betti numbers, capturing topological information throughout a deformation process, and (2) verify a specific QMA_1-hard problem, showcasing potential applications in computational complexity theory.







§ INTRODUCTION








Graph-based information processing has seen extensive success over several decades. However, a fundamental limitation of graphs is their inability to model beyond pairwise interactions. Recent evidence has highlighted the importance of higher-order interactions, where links can connect more than two nodes. Consequently, higher-order networks have emerged as a crucial frontier in complex network science <cit.>. A prominent model in this domain is simplicial complexes, which are natural generalizations of graphs to higher-order structures. 

Just as random walks on graphs have been important tools to solve graph problems, random walks on simplicial complexes can play a crucial role in analyzing higher-order networks. Graph Laplacian dynamics and homology are significant concepts in graph-based information processing. Therefore, it is natural to explore the theoretical connection between higher-order random walks and the topological properties of underlying simplicial complexes. Recent breakthroughs have revealed close relationships between the topological properties of simplicial complexes and random walks on them <cit.>.




The concept of orientation becomes crucial when relating random walks on simplicial complexes to their homology. While 0-simplices are merely vertices and lack a natural orientation, for k≥ 1, there exists a clear distinction between positive and negative orientations of simplices. For instance, in the case of 1-simplices (edges), positive and negative orientations (directions) can be discerned. Analogously, similar notions of positive and negative orientation can be extended to higher-dimensional simplices. Random walks described in <cit.> are conducted on such oriented simplicial complexes. In essence, these approaches treat identical simplicial complexes with different orientations as distinct states. By exploring random walks on such oriented simplicial complexes, one can examine the difference between the probabilities of being in a positive simplex and its corresponding negative simplex. This process, defined through the difference of probabilities, is termed the “expectation process" <cit.>. It has been demonstrated in <cit.> that the normalized version of the expectation process exhibits a rigorous connection with the projector onto the harmonic homology group of the underlying simplicial complex. 
It is shown in <cit.>
that performing random walks from some initial simplex and executing the normalized expectation process is equivalent to approximately applying the projector onto  the harmonic homology group to that initial state. 
It is shown as long as the spectral gap of the combinatorial Laplacian operator is inverse-polynomially large, the normalized expectation process can implement the projector with high precision with polynomial time steps. 
However, since the normalized expectation process differs from the conventional random walk itself, it remains open whether the process can be simulated efficiently, especially in (extremely) high-dimensional cases.











Analysis of higher-order networks has recently gained attention in the quantum computing literature. One significant focus has been on efficiently performing topological data analysis (TDA) <cit.> in the high-dimensional regime using quantum computing.
In TDA, input data is transformed into a family of simplicial complexes (referred to as filtration), and the goal is to analyze how topological invariants vary across the filtered simplicial complexes. The primary topological invariants of interest in TDA are known as persistent Betti numbers. While classical TDA has become a popular field of data analysis, classical algorithms face limitations in analyzing high-dimensional persistent Betti numbers. 
This is because the number of simplices can grow superpolynomially in the number of vertices. 



As exact computation is even intractable for quantum computers [Indeed, exactly calculating the Betti numbers is known to be #P-hard for clique complexes <cit.> and more precisely, it is #_1-hard <cit.>.], in quantum TDA (QTDA), a relaxation of the condition of estimating the persistent Betti numbers is usually considered, namely the estimation of the normalized Betti numbers with inverse-polynomial additive precision. 



The first QTDA algorithm was proposed by Lloyd, Garnerone, and Zanardi <cit.>. 








The estimation of the normalized Betti number has been extended to the estimation of the normalized persistent Betti numbers <cit.>. QTDA algorithms exhibit superpolynomial speedup compared to the best-known classical algorithms, because there is no known efficient classical algorithm for solving the NBE problem with inverse polynomial precision in n.








Utilizing Quantum Walks (QW) based algorithms has shown significant speed enhancements compared to classical algorithms across various scenarios, and demonstrated polynomial speedup over classical algorithms <cit.>.
However, there are a few problems that exhibit exponential speedup.
The first QW algorithm exhibiting exponential speedup was proposed in <cit.>, which utilized continuous-time quantum walks to traverse the welded-tree graph with height n by using O(n^6) queries, demonstrating that no classical algorithm can match its efficiency. 
This problem can be solved by a multidimensional QW algorithm with a better complexity<cit.>, and can be extended to a broad class of hierarchical graphs<cit.>.
Although these results show an exponential advantage over the classical algorithms, the advantage holds in the query complexity with oracle access to exponentially large data. 
Therefore, it does not mean that these QW algorithms demonstrate superpolynomial speedup in the realistic computation time. 




















There are a few existing quantum walk results considering higher dimensional space than the graphs. 
The first quantum walk on simplicial complexes is proposed by Matsue, Ogurisu, and Segawa in <cit.>. They extend Szegedy’s QW on simplicial complexes, and these quantum walks possess linear spreading and localization as the Grover walk. 
Later on, they proposed a QW algorithm that can find a marked simplex polynomially faster than the classical counterpart <cit.>. 

However, these results do not show a superpolynomail quantum advantage.
It has been numerically observed that quantum walks on simplicial complexes reflect the topology of simplicial complexes <cit.>. However, the connection between the quantum walks and topology of simplicial complexes has not been rigorously proven.



Even though there is no known efficient way to simulate the normalized expectation process in arbitrary dimensions, 
it indeed paves new applications for signal processing and learning tasks on simplicial complexes in constant dimensions such as the random walks on edges or triangles. 
For example, random walks on oriented edges have been applied to the task of label propagation on edges in <cit.>. 
In <cit.>, similar higher-order random walks are applied to the task of edge flow estimation and Pagerank vector on simplicial complexes. For a review, see <cit.>. 



 §.§ Main results


In this paper, we show a rigorous relationship between quantum walks and homology for the first time. 





Our main result concerns the implementation of projectors onto subspaces that are related to the topology of simplicial complexes with quantum walks. 
Let us focus on the k-th harmonic homology group, denoted by ℋ_k.
For a trivial ℋ_k, the simplicial complex has no “k-dimensional holes”. Conversely, the dimension of ℋ_k reflects the number of such holes, making it highly relevant to the complex's topology.
We can relate ℋ_k to a positive semi-definite hermitian operator called the combinatorial Laplacian Δ_k. 
It is known that 
ℋ_k= (Δ_k).  
Our main result can be stated as follows. 





   
  
  
   
   
Given a simplicial complex over n vertices, let λ_k>1/poly(n), where λ_k is the smallest non-zero eigenvalue of Δ_k. Then, there exists a Markov transition matrix P on oriented k-simplices such that   we can implement a unitary encoding of an operator which is inverse-exponentially close to the projector onto ℋ_k with polynomial use of “harmonic quantum walk unitary” U^h and other elementary quantum gates. Here, U^h is a unitary in which the Markov transition matrix P is encoded using α-ancilla qubits i.e., 

    (Π^±_k⊗⟨0^α|)U^h(Π^±_k⊗|0^α⟩)= Π^±_kPΠ^±_k,

where Π^±_k is a projector onto the space spanned by positively and negatively oriented k-simplices.




In addition to the implementation of the projector onto ℋ_k, we implement quantum encodings of projectors onto other subspaces related to the topology 
based on variants of quantum walks on simplicial complexes (See the formal statement of Theorem <ref>).

These projectors play essential roles in the application of quantum walks to the estimation of the normalized persistent Betti numbers, which is an indispensable topological invariant in TDA. 
In total, we construct three quantum walk algorithms and they are referred to as up, down, and harmonic quantum walks.

Our second contribution is that we provide an explicit construction of quantum walk unitaries in Section <ref>. Especially, we show that we can efficiently construct quantum walks unitaries for clique complexes given access to the graph adjacency matrix, which is (exponentially) succinct compared to the size of the simplicial complex. 




Let X be a vertex-weighted clique complex over n vertices. 
Then, we can construct unitaries U^up, U^down, and U^h 
that are unitary encodings of up, down, and harmonic Markov transition matrices with error ϵ using α=𝒪(n) ancilla qubits
with 𝒪(n^2log(1/ϵ))-number of gates, respectively. 


Our results on the encoding of Laplacians, implementation of projectors, and construction of quantum walk unitaries are summarized in Table <ref>.





The presented Theorems <ref> and <ref>
lead to new applications of quantum walks to higher-order networks because they clarify the conditions for the efficient implementations of the projectors and the efficient implementations of quantum walk unitaries for clique complexes. 
We demonstrate the usefulness of our quantum walks through three applications:




    
  * Normalized Betti number estimation: First, we show that we can efficiently estimate the normalized k-Betti numbers of clique complexes of arbitrary dimensions based on harmonic quantum walks if we can sample from the uniform distribution of k-simplices and the combinatorial Laplacian has an inverse-polynomial spectral gap (Theorem <ref>).
    
  * Normalized persistent Betti number estimation: Second, we show that we can efficiently estimate the normalized k-persistent Betti numbers of clique complexes combining up quantum walks and down quantum walks (Theorem <ref>). 
    
  * Verification of the promise clique homology problem: Third, we show we can efficiently verify the promise clique homology problem of <cit.> i.e., we can efficiently verify if a state sent from the prover is in the harmonic homology group or not (Theorem <ref>). 

The first two applications are motivated by TDA. The third application is motivated by potentially providing new interactive protocols based on quantum walks such as the verification of quantum computing.
These results also open the possibility of demonstrating superpolynomial speedup using quantum walks for practical problems on simplicial complexes. 
We discuss the computational complexity of the problems in our applications in Section <ref> and discuss why these problems might not be tractable for classical algorithms. 
Notably, unlike the previous superpolynomial speedup results of quantum walks for graph problems <cit.>, our superpolynomial speedup result does not rely on the query access to exponentially large matrices. 
This is because clique complexes can be described with graphs and we can efficiently construct quantum walk unitaries clique complexes from the graph adjacency matrices. 
As far as we know, this is the first example of superpolynomial speedup for graph or topological problems in the computational time rather than the query complexity based on quantum walks. 
We expect that our quantum walks on simplicial complexes will find more applications in high-dimensional signal processing and machine learning tasks as is in the case for the random walks on simplicial complexes in constant dimensions.








 §.§ Technical Contributions


No previous works have shown a relation between the homology of simplicial complexes and quantum walks. 
We identified that this obscurity originated from the lack of the proper treatment of orientations of simplicial complexes in quantum walks. 
It is the treatment of orientations of simplicial complexes that enabled us to encode the topological Laplacian operators into quantum walks and moreover, enabled us to implement the projectors onto the topological subspaces. Let us start by first illustrating how we represent the oriented simplicial complexes with quantum states. 





  
Quantum representation of oriented simplices.

As we perform quantum walks on oriented simplicial complexes, how we represent such objects as quantum states comes up as the first technical challenge.
The oriented k-simplices can be represented as [v_0,v_1,...,v_k]. 
The oriented k-simplices obtained by even (odd) permutation of vertices are said to have the same (opposite) orientation.
Throughout the paper, we fix the positively oriented simplices by the ordering [v_0,v_2,...,v_k] with v_0<v_1<...<v_k. 
The unoriented simplices can be described by n-bit strings with Hamming weight k+1 where the positions of 1's correspond to the vertices of simplices. 
We represent each of oriented k-simplices σ with n+1-qubit computational basis states where the first n qubits correspond to the membership of the vertices and the last 1 qubit represents the orientation i.e.,  

    |σ⟩=
    |x_σ⟩⊗|0⟩   if σ is positively oriented,
    |x_σ⟩⊗|1⟩   if σ is negatively oriented,

where x_σ is the n-bit string with Hamming weight k+1.[We actually use n+2-qubit state to represent an additional special state called the absorbing state. Here, we describe without the absorbing state for simplicity.]
In Figure <ref>, we show an example of quantum representation of a positively oriented 2-simplex over 5 vertices. 








  
Encoding of up, down, and full Laplacians into quantum walks.

The next technical challenge is how we can define quantum walks on simplicial complexes in which we can encode the Laplacians. Unlike graphs, there are two different notions for adjacency for simplicial complexes: up-adjacency and down-adjacency. 
Based on the up-adjacency and down-adjacency, we can define three kinds of random walks on simplicial complexes (up, down, and harmonic random walks). Formal definitions can be seen in Definitions <ref>, <ref>, <ref> in Section <ref>.  
Examples of up, down, and harmonic walks on simplicial complexes are shown in Figure <ref>. 

For simplicity, we consider unweighted simplicial complexes here. 


Let us take the relationship among up random walk, up quantum walk, and up Laplacian for example. 
It should be emphasized that although the random walk is defined on the oriented simplicial complexes, the up Laplacian is defined for the simplices with a fixed orientation.  
In the up random walk, a k-simplex σ transit to simplices σ' that share a common upper simplex and the orientation of the k+1 induced by σ and σ' must be the same. 
In Figure <ref>(a), it can be seen that the orientation of the triangle induced by the edges are same. 
This means that for σ≠σ',

    P^up_σ,σ'=Prob(σ→σ') 
    = 1/K^up

if σ and σ' are up-adjacent (including the orientation) where K^up is some normalization factor of probabilities. 
Meanwhile, the matrix element of the up Laplacian satisfies for σ≠σ' s.t. σ and σ' are up-adjacent, 

    (Δ^up_k)_σ_+,σ'_+=
    
        1    if σ_+ and σ'_+ are up adjacent, 
    
        -1    if σ_+ and σ'_- are up adjacent,

where σ_+ and σ'_+ (resp. σ'_-) are positively (resp. negatively) oriented simplices correspond to σ and σ', respectively. 
These relationships show that if a state transits to a state with the same (resp. different) orientation, the corresponding sign of the matrix element of the up Laplacian is + (resp. -). 
Suppose we have a unitary encoding U^up of P^up using α-ancilla qubits i.e., 

    (Π^±_k⊗⟨0^α|)
        U^up(Π^±_k⊗|0^α⟩)= Π^±_kP^upΠ^±_k,

where Π^±_k is the projector onto the space spanned by positively and negatively oriented k-simplices. 
Then, we apply HZ gates to the qubit that represents the orientation to obtain a unitary V^up= ((I_n⊗ HZ)⊗ I_α)U^up.
By this construction, we can add a relative phase factor of -1 if a simplex transit to other simplices with a different orientation. 
The laziness of the random walk (i.e., the probability of staying in the same simplex after a transition) is proportional to the up-degree (the number of k+1-simplices that a k-simplex has as upper simplex). 
The diagonal elements of the up Laplacian are given exactly by the up-degree of simplices. 
Therefore, we can conclude that V^up is a unitary encoding of the up Laplacian. A formal statement and proof can be found in Proposition <ref> in Section <ref>. 
For the down and harmonic quantum walks, we can encode the down and full Laplacians with analogous arguments. 




  
Implementing the unitary encoding of projectors.

The implementation of the projectors is based on the quantum singular value transformations <cit.> of quantum walk unitaries. 
The k-chain space C_k, which is a space spanned by positively oriented k-simplices, can be decomposed as follows:

    C_k= B_k ⊕ℋ_k ⊕ B^k,

where B_k, B^k, ℋ_k are k-boundary, k-coboundary, and k-harmonic homology group. 
For formal definitions, see Section <ref>.
These subspaces can be represented with Laplacian operators as follows:

    
  * B_k=Im(Δ_k^up),  B^k=Im(Δ_k^down).
    
  * B_k⊕ℋ_k = (Δ_k^down),   B^k⊕ℋ_k = (Δ_k^up).

Therefore, projectors onto these subspaces can be realized by the projectors onto the low/high energy subspace of Δ_k, Δ_k^up and Δ_k^down with threshold λ_k, λ_k^up, and λ_k^down where λ_k, λ_k^up, and λ_k^down are the minimal non-zero eigenvalues (spectral gaps) of Δ_k, Δ_k^up, and Δ_k^down, respectively. 
We perform quantum singular value transformations with polynomial approximation of rectangle functions with threshold λ_k, λ_k^up, and λ_k^down with the quantum walk unitaries. 

The number of quantum walk unitaries used in the procedures is bounded by polynomial in n if λ_k, λ_k^up, and λ_k^down are lower bounded by 1/poly(n).




  
Construction of up/down quantum walk unitaries.

We explain how to construct the quantum walk unitaries for clique complexes using the membership function. 
For simplicity, we consider the unweighted case. 
The up quantum walk unitary is constructed with “up-down” construction and the down quantum walk unitary is constructed with “down-up” construction. 
In the “up-down” construction, k-simplices first go up to k+1-simplices and then go back to k-simplices. 
In the “down-up” construction, k-simplices first go down to k-1-simplices and then go back to k-simplices. 

When we go up from k-simplex σ to k+1-simplices, we can change one of the 0's of the n-bit string x_σ to 1.  
As the number of 0's in x_σ is n-k-1, we use the superposition of ∑_i∈ [n-k-1]1/√(n-k-1)|i⟩ in an ancilla register. 
Of course, not all of the Hamming weight k+2 strings are included in the k+1-simplices. Therefore, we can apply the membership function to verify if they are included in the k+1-simplices. 
The induced orientation of the k+1-simplices depends on the position of 0 that is converted to 1. 
If there are odd numbers of 1 before the position of 0, the relative orientation changes from the original simplex σ. 
If the number of the sum of 1 is even, the relative orientation does not change. 
After we transit to k+1-simplices, we similarly go down to k-simplices by changing one of the positions of 1 to 0 while tracking the orientation.
When we go down, we use the superposition of ∑_j∈ [k+2]1/√(k+2)|j⟩ prepared in another ancilla register. 

The “down-up” construction can be similarly done. Note that when we go down from k-simplices, the states must be included in the elements of k-1-simplices by the definition of simplicial complexes. Therefore, we apply the membership function after we go back to k-simplices. 
Note that in the “up-down” and “down-up” constructions, the self-loops (laziness) are automatically encoded. 



  
Construction of the harmonic walk unitary.

For the construction of harmonic walk unitary, we use the following superpositions in an ancilla register:

    ∑_i∈ [n-k-1], j∈ [k+1]|i,j⟩|0⟩ 
    +
    ∑_l ∈ [n-k-1]|l,l⟩|1⟩
    +
    ∑_m ∈ [k+1]|m,m⟩|1⟩,

where we hide a global normalization factor. 
The first term is for the adjacency, the second term is for the upper degree, and the third term is for the lower degree. 
Based on this superposition, we perform the following computation for each of the σ:

    ∑_i∈ [n-k-1], j∈ [k+1]|i,j⟩|0⟩_Flip the  i-th  0 and  j-th  1 of x_σ,
    then, check the membership.
    +
    ∑_l ∈ [n-k-1]|l,l⟩|1⟩_Check the membership of the simplex
    obtained by flipping the l-th 0 of x_σ
    +
    ∑_m ∈ [k+1]|m,m⟩|1⟩._Do nothing.

By Claim <ref> in Section <ref>, it follows that the relative orientation of the simplex obtained by the transition of the first term is equal to the sum of the bit elements of the positions between the indices of i-th 0 and j-th 1 of x_σ.
In the harmonic walk, simplices transit to other simplices that are lower-adjacent but not up-adjacent. This condition can also be computed using the membership function. 
Unlike the “up-down” and “down-up” construction, this construction separates the self-loops and adjacency. 



  
Applications.

The constructed projectors onto topological subspace can be applied to problems of practical interest. 
The first two applications of our quantum walks are the tasks of estimating the normalized Betti numbers and the normalized persistent Betti numbers, that are related to the topological data analysis. 
First, the estimation of the normalized Betti numbers, denote by β_k/n^k, can be done in the following steps:

    
  * Prepare the uniform mixture over k-simplices
    ρ_k = 1/n_k∑_σ∈ X^+_k|σ⟩⟨σ|,
    where n_k is the number of k-simplices of a simplicial complex X.
    
  * Estimate the energy w.r.t the combinatorial Laplacian Δ_k and measure the energy.
    
  * Sample from the above quantum circuit and output: 
    
    The # of outcomes of energy below λ_k /The # of samples

    as the estimate, where λ_k is the minimal non-zero eigenvalue of Δ_k.

We can estimate the β_k/n^k with the above procedures because
ρ_k=1/n^k ∑_i∈ n_k|ψ_i⟩⟨ψ_i| where {|ψ⟩}_i are eigenvectors of Δ_k and β_k is equivalent to the number of zero-energy eigenvectors of Δ_k. 
In the second step, we measure the energy w.r.t. the combinatorial Laplacian.
To be more precise, we actually construct a quantum circuit that can conditionally project onto the low-energy subspace of the combinatorial Laplacian. This means that in the third step, if the measurement outcome is 1, the state is successfully projected onto the low-energy subspace below the energy threshold. 
The complexity of the procedure is governed by the complexity of preparing the initial mixed state, the complexity of energy measurement, and the number of necessary samples. 
We can efficiently estimate the normalized Betti numbers with inverse-polynomial additive precision
under the conditions that
we can efficiently sample from the uniform distribution over k-simplices and λ_k> 1/poly(n). 

Next, we explain how to estimate the normalized persistent Betti numbers. 
We use the following relationship:
β^i,j_k =  ( (Δ_k^i,down))-  ( (Δ_k^i,down) ∩ (Im(Δ_k^j,up)),
where i and j represents the two simplicial complexes X^i ⊆ X^j. 

We can estimate β^i,j_k/n_k by estimating
( (Δ_k^i,down))/n_k  and   ( (Δ_k^i,down) ∩ (Im(Δ_k^j,up))/n_k,
respectively, 
where n_k is the number of k-simplices of X^i. 
The first quantity can be estimated using the down quantum walk on K_i and the second quantity can be estimated by combining the down quantum walk on K_i and the up quantum walk on K_j in a similar way with the case of Betti numbers. 
This application illustrates that down quantum walk and up quantum walks are useful for tasks related to persistence and TDA. 

Finally, in the case of the verification of the promise clique homology problem, the task is to verify if the homology group of the given clique complex is trivial or not. 
If the homology group is not trivial (YES case), we can receive a witness state from the prover which is supposed to be in the kernel of Δ_k. 
In the NO case, there is a promise that Δ_k has some inverse-polynomial spectral gap. 
Therefore, we can show that the verifier can decide which is the case based on the implementation of the projector onto the low-energy subspace of Δ_k with desirable soundness and completeness. 



 §.§ Outlook and Related works





Our work opens avenues for applying quantum walks to higher-order networks. 
In this subsection, we discuss related works and open problems. 
We first compare existing classical results and our results in detail.
Second, we discuss the computational complexity of the problems related to clique complexes to clarify how hard the problems we are solving are and to highlight the evidence for the classical difficulty of the tasks. Next, we compare our results to another classical algorithm based on the path integral Monte Carlo method and existing QTDA algorithms. Finally, we present two open problems: one regarding the potential for further application of our construction to graph problems, and the other concerning the extension of our quantum walks to persistent homology groups. 





  
Comparison with classical results.
We give a comparison between our results and previous results on classical random walks on simplicial complexes.
We give a summary of classical results in Table <ref>. 
Although <cit.> also provides conceptually similar results, we do not include their result because the rate of convergence of the result of <cit.> is not known.  The formal definitions of up and down random walks can be found in Appendix <ref>. 

The number of required time steps t should be comparable to the number of uses of quantum walk unitaries in our results. 
As it can be seen from the table, the rate of the convergence to the target subspaces is similar to our results in the sense that the distance can be made to be inverse polynomially small in polynomial time steps t with proper choice of the laziness if the spectral gaps of the Laplacians are at least inverse-polynomially large. 
However, there are obstacles to simulating the normalized expectation process because in order to perform the process, one needs to characterize the behavior of two different probabilities at the same time to take their differences, which is beyond the applicability of usual random walk techniques. 



  
Complexity of the problems related to the homology of clique complexes.

Complementary to the study of quantum algorithms for simplicial complexes, 
the quantum computational complexity of problems related to the homology of simplicial complexes has also been examined. 
First, the normalized Betti number estimation (NBE) problem for inverse-polynomial precision for general simplicial complexes has been shown to be -hard <cit.>. 
Similarly, the Low-lying Energy Density Problem, a generalization of the NBE problem, is also -hard <cit.>. 
These results can be seen as evidence that there are no efficient classical algorithms for such generalized problems assuming that -hard problem cannot be solved efficiently classically. 
These can also be seen as evidence of the difficulty of classically simulating the normalized expectation process in arbitrary dimensions.
However, note that it is still open whether the estimation problem of normalized Betti numbers in inverse polynomial precision is -hard for Vietoris-Rips complexes or clique complexes for which we have efficient quantum algorithms. 
Second, the computational complexity of the clique homology problem, which is a problem to decide if the homology group of a given clique complex is empty or not, has also been studied in terms of quantum computational complexity. The clique homology problem is shown to be _1-hard <cit.>.
It has also shown that the clique homology problem with weights on vertices and promise for the spectral gap of the combinatorial Laplacian is _1-hard and contained in  <cit.>. 





  
Path integral Monte Carlo algorithm for Betti numbers.
In addition to the random walks on oriented simplicial complexes of <cit.> <cit.>, 
there is another classical random walk for tasks related to homology. 
In <cit.>, the authors propose a path integral Monte Carlo algorithm which is used to estimate the normalized Betti numbers in the constant additive precision. 
The algorithm of <cit.> first samples uniformly from the k-th simplices and then performs some random walk related to the combinatorial Laplacian.
Finally, it computes and outputs the estimate for the normalized Betti numbers. 
Instead of sampling from the space with positive and negative orientations, they perform random walks on unoriented k-simplices and use the information of orientation in the post-processing. 
However, their algorithm still does not provide an efficient way of estimating the normalized Betti numbers in the inverse polynomial precision.




































  
Comparison between the existing QTDA algorithms.
We give a comparison between our algorithm and the prior works on QTDA <cit.>. 
Compared to the prior works, we double the state space due to the distinction of orientations. Note that, however, this doubling only requires an additional single qubit. 
It can be said that it is due to this addition of a single qubit that we have been able to ease the sign problem of combinatorial Laplacians and relate QTDA to Markov chains. 
Therefore, although it is not that our algorithm drastically improves the time complexity for QTDA compared to the prior works on QTDA, we have been able to find a new way to perform topological information processing through the experimental realization of quantum walks <cit.>, and in a broader sense, our work opens a way to unify the study of quantum walks and QTDA. 



  
Lackadaisical quantum walks.

Our random walks on simplicial complexes are lazy random walks i.e., there are self-loops. 
A lazy version of quantum walks is called the lackadaisical quantum walks <cit.> <cit.>. 
Therefore, our quantum walks can be seen as high-dimensional lackadaisical quantum walks. 
If we consider our quantum walks on 0-simplices i.e., vertices, we can straightforwardly obtain the encoding of graph Laplacians into quantum walk unitaries. 
As graph Laplacian is an important tool in graph-based information processing, can the encoding of graph Laplacians into quantum walks find more applications? 



  
Persistent harmonic homology group.

In this paper, we show the implementation of several projectors onto subspaces related to topology. 
Recently, persistent Laplacian operators are introduced <cit.> <cit.> <cit.>. 
It has been known that the dimension of the kernel of the persistent Laplacian is equivalent to the persistent Betti numbers. 
Although we show how to estimate the normalized persistent Betti numbers in Section <ref>, it is based on the combination of several projectors and not based on the persistent Laplacian. 
Is it possible to construct quantum walks with which we can directly implement the projector onto the persistent harmonic homology group (i.e., the kernel of the persistent Laplacian)?




 §.§ Organization of the paper


The remainder of this paper is organized as follows. In Section
 <ref>, we introduce several preliminaries on simplicial complexes, homology, and quantum computing. 
In Section <ref>, we present the implementation of the projectors based on the quantum walks. This section includes the formal definitions of up, down, and harmonic random walks on simplicial complexes.  
In Section <ref>, we show efficient constructions of up, down, and harmonic quantum walk unitaries for clique complexes.
Finally, in Section <ref>, we show three applications of our quantum walks on simplicial complexes: estimation of the normalized Betti numbers, estimation of the normalized persistent Betti numbers, and the verification procedure of the promise clique homology problems. 



§ PRELIMINARY


In this section, we introduce several preliminaries. 
In Section <ref>, we introduce simplicial complexes and their orientations. 
In Section <ref>, we introduce up-adjacency and down-adjacency of simplicial complexes. 
In Section <ref> we introduce boundary operators and homology group. 
In Section <ref>, we introduce the discrete Hodge theory, which relates the homology and the Laplacian operators. 
In Section <ref> and  <ref>, we introduce the matrix representation of Laplacians and the weighting of simplicial complexes. 
In Section <ref>, we introduce some preliminaries on quantum computing. 
Finally, in Sectioin <ref>, we further introduce some notations. 



 §.§ Oriented simplicial complexes
 

An abstract simplicial complex X over a finite set of vertices V is a set of vertices of V that is closed under taking subsets. 
Let n |V|. A simplex is called a k-simplex if it is composed of (k+1)-vertices. 
We denote the set of k-simplices of X as X_k.
We denote the number of k-simplices of X by n_k.
An oriented k-simplex σ is a simplex σ with orientation inherited from the ordering of vertices σ=[v_0,v_1,...,v_k]. Two oriented k-simplices σ=[v_0,v_1,...,v_k] and σ'=[v'_0,v'_1,...,v'_k] are said to have the same orientation if [v_π(0),v_π(1),...,v_π(k)]=[v'_0,v'_1,...,v'_k] for an even permutation π. 
Such σ_k and σ_k' are regarded as the same oriented simplex. 

Throughout the paper, we say σ_k=[v_0,v_1,...,v_k] is positively (negatively) oriented if an ordering [v_π(0),v_π(1),...,v_π(k)] such that v_π(0)<v_π(1)<⋯<v_π(k) is obtained with an even (odd) permutation π. 
We denote the set of positively oriented k-simplices by X^+_k and negatively oriented k-simplices by X^-_k. It follows that |X^+_k|=|X^-_k|=n_k.
For any oriented simplex σ∈ X^±_k, σ represents its counterpart with the opposite orientation.
For any σ∈ X^±_k, we can identify its corresponding unoriented simplex with a Hamming weight k+1 bit string x_σ∈{0,1}^n, where the positions of 1s correspond to the membership of the vertices of the simplex. 
With a slight abuse of notation, 
we denote the set of all Hamming weight k+1 bit strings  associated with elements of X^±_k by X_k⊆{0,1}^n. 



 §.§ Adjacency of simplicial complexes


For an unoriented simplex σ={v_0,v_1,...,v_k}, its faces are the subsets obtained by removing a single vertex: σ\ v_0,σ\ v_1,...,σ\ v_k.  By definition,  any k-simplex has exactly k+1 faces.   
An oriented simplex σ=[v_0,v_1,...,v_k] induces an orientation on its faces as (-1)^j[v_0,...,v_j-1,v_j+1,...,v_k]
where (-1)^j means to take the opposite orientation if (-1)^j=-1. 
(We take the opposite orientation if we remove the j-th vertex and j is odd.)
A (k+1)-simplex σ'_k+1 is called a coface of σ_k if σ_k is a face of σ'_k+1.
For σ, σ' ∈ X^±_k, we use the following notations:

        
  * (Up-adjacency:) We denote σ∼_↑σ' if they share a common k+1-dimensional coface and the orientation of the coface induced by σ and σ' are same. If σ∼_↑σ', σ and σ' are said to be oriented similarly. 
        If σ∼_↑σ', σ and σ' are said to be oriented dissimilarly <cit.>. 
        
  * (Down-adjacency:) We denote σ∼_↓σ' if they share a common k-1-dimensional face and the orientation of the face induced by σ and σ' are same. 
        If σ∼_↓σ', σ and σ' are said to have a similar common lower simplex. 
         If σ∼_↓σ', σ and σ' are said to have a dissimilar common lower simplex <cit.>.
        
  * σ_↑σ': if σ and σ' are not up-adjacent. 
        
  * (σ): number of cofaces of σ. 

The quantity (σ) should also be called as up-degree as it is the number of cofaces. 
We simply refer to it as “degree" because the number of faces of any k-simplex (down-degree) is always k+1.
Note that for any k-simplices σ and σ', the common face or coface is always unique if they exist <cit.>.



 §.§ Chain group and homology


We denote a k-th chain group C_k defined as Span{|σ⟩}_σ∈ X_k^+ with real coefficients. 
We can define a k-th boundary operator ∂_k:C_k→ C_k-1 as an operator that acts for any k-simplex in [v_0,v_1,...,v_k]∈ X^+_k as


    ∂_k [v_0,v_1,...,v_k]
        =
        ∑_j=0^k (-1)^j [v_0,...,v_j-1,v_j+1,...,v_k].

The important property of boundary operators is that ∂_k-1∂_k=0. 
The k-th homology group is defined as 
    H_k(∂_k)/Im(∂_k+1),
 and the k-th Betti number is defined as β_k(H_k). 
B_kIm(∂_k+1) is called the k-boundary and Z_k(∂_k) is called the k-cycle. 

Given two simplicial complexes X^i ⊆ X^j over the same vertices, we can define the persistent homology groups and the persistent Betti numbers. 
The k-th persistent homology group is defined as follows: 

    H^i,j_k (∂_k^i)/((∂_k^i)∩Im(∂_k+1^j)).

The k-th persistent Betti number is defined as β^i,j_k(H^i,j_k).



 §.§ Discrete Hodge theory


We define the inner product such that {|σ⟩}_σ∈ X^+_k forms an orthonormal basis for C_k. This means that ⟨σ'|σ|=⟩δ_σ,σ' for all σ,σ'∈ X^+_k. 
Then, let ∂^*_k be an adjoint of ∂_k. 
With our choice of inner product, ∂^*_k=∂^†_k. 
The k-th combinatorial Laplacian (Hodge Laplacian) Δ_k:C_k→ C_k is defined as

    Δ_k∂_k+1∂_k+1^*
    +∂_k^*∂_k.

We also define

    Δ_k^up∂_k+1∂_k+1^*,


    Δ_k^down∂_k^*∂_k.

It is known that 
    
    (Δ_k)≅ H_k

and 
    
    β_k=Nullity(Δ_k)((Δ_k)).

We denote the smallest non-zero eigenvalues of Δ_k, Δ_k^up and Δ_k^down as λ_k, λ_k^up and λ_k^down, respectively. It holds that λ_k= min{λ_k^up, λ_k^down}. 
Note that the spectrum of the Laplacians does not depend on the choice of the orientation of simplices <cit.>.

We can decompose C_k as 

    C_k = Im(∂_k+1)⊕(Δ_k) ⊕Im(∂_k^*).

This decomposition is known as the Hodge decomposition. 
It holds that Im(∂_k+1)=Im(Δ_k^up) and Im(∂_k^*)=Im(Δ_k^down). 
Therefore,
we can decompose C_k in terms of up, down Laplacians as  
Im(Δ_k^up)⊕(Δ_k)⊕Im(Δ_k^down) 
. 



 §.§ Matrix representation of the unweighted combinatorial Laplacian



The combinatorial Laplacian can be described using the degree and the adjacency relationships <cit.>. 
It is known that 
Δ^up, Δ^down and Δ_k satisfy for all σ,σ' ∈ X^+_k,
    
    (Δ^up_k)_σ,σ'= (σ),     if σ=σ' 
    
            1,     if σ∼_↑σ'
    
            -1,     if σ∼_↑σ'
    
            0,     otherwise.

    
    (Δ^down_k)_σ,σ'=
        
            k+1,     if σ=σ' 
    
            1,     if σ∼_↓σ'
    
            -1,     if σ∼_↓σ'
    
            0,     otherwise.

    
    (Δ_k)_σ,σ'=
        (σ)+k+1,     if σ=σ' 
    
            1,    if σ∼_↓σ' and σ_↑σ'
    
            -1,    if σ∼_↓σ' and σ_↑σ'
    
            0,     otherwise.

Note that σ∼_↑σ' also implies σ∼_↓σ'. 
Therefore, in the full Laplacian, the matrix elements of σ, σ' that are only lower adjacent (regardless of orientations) remain to be non-zero. 





 §.§ Vertex-weighted simplicial complexes



We generalize the simplicial complexes with a vertex-weighted graph G, which is characterized by a function w:ℕ→ (0,∞] assigning each vertex v a weight w(v) following <cit.>.
A vertex-weighted simplicial complex X over the vertices is defined in the same manner as the unweighted case. 
The main difference between them is that we assign 
each simplex σ in X a weight w(σ), defined as the product over weights of all vertices in σ: 

    w(σ)=∏_v∈σw(v).

Furthermore, the inner product on the k^th vertex-weighted simplicial complexes chain space, C_k(X,ℝ), is defined by 

    ⟨σ|τ⟩= w(σ)^2     if σ=τ ,
     0     otherwise,

for σ,τ∈ X_k are k-simplices of X. 
This inner product implies that the set {|σ'⟩:=1/w(σ)|σ⟩: σ∈ C_k} forms an orthonormal basis for C_k.

To define the combinatorial Laplacian Δ^k of the k^th vertex-weighted simplicial complexes chain, it is necessary to define the boundary operator ∂_k: 

    ∂_k|σ^'⟩=∑_v ∈σ w(v)|(σ\{v})^'⟩.








With the boundary operator, the combinatorial Laplacian Δ^k=∂_k+1∂_k+1^*+∂_k^*∂_k can be expressed as follows: Δ^up, Δ^down and Δ_k satisfy for all σ,σ' ∈ X^+_k,
    
    (Δ^up_k)_σ,σ'= ∑_u ∈ up(σ) w(u)^2,     if σ=σ' 
    
            w(v_σ)w(v_σ'),     if σ∼_↑σ'
    
            -w(v_σ)w(v_σ'),     if σ∼_↑σ'
    
            0,     otherwise.

    
    (Δ^down_k)_σ,σ'=
        ∑_v ∈σ w(v)^2,     if σ=σ' 
    
            w(v_σ)w(v_σ'),     if σ∼_↓σ'
    
            -w(v_σ)w(v_σ'),     if σ∼_↓σ'
    
            0,     otherwise.

    
    (Δ_k)_σ,σ'=
        (∑_u ∈ up(σ) w(u)^2)+(∑_v ∈σ w(v)^2) ,     if σ=σ' 
    
            w(v_σ)w(v_σ'),    if σ∼_↓σ' and σ_↑σ'
    
            -w(v_σ)w(v_σ'),    if σ∼_↓σ' and σ_↑σ'
    
            0,     otherwise.


Here, up(σ) ⊂ X_0 is the subset of vertices v such that σ∪{v}∈ X_k+1 is a k+1-simplex, and v_σ and v_σ' are the vertices removed from σ and σ', respectively, to obtain the common lower simplex.




 §.§ Unitary encoding, transformation, and measurement



We introduce some preliminaries on quantum computing.
The block-encoding of an operator is defined as follows:


    Suppose that A is an s-qubit operator, a,ϵ∈ℝ_+, and α∈ℕ. We say that the (s+α)-qubit unitary U is an (a,α,ϵ)-block-encoding of A, if 
    
    A-a(I_s⊗⟨0^α|) U (I_s⊗|0^α⟩ )
        ≤ϵ.

    More generally, we say that U is a Π_s-projected (a,α,ϵ)-unitary encoding of A if 
    
    A-a (Π_s ⊗⟨0^α|) U (Π_s ⊗|0^α⟩ )
        ≤ϵ,

where Π_s is an s-qubit projector.

Using the block encoding or the unitary encoding, we can perform quantum singular value transformation (QSVT) <cit.>. 
For a Hamiltonian H with eigendecomposition H=∑_i λ_i |ψ_i⟩⟨ψ_i|, the singular value transformation of H with polynomial f(x) is 

    f(H)=∑_i f(λ_i) |ψ_i⟩⟨ψ_i|.


We introduce a C_ΠNOT-gate which applies X gate conditioned that a state is in the image of a projector Π as:

    C_ΠNOT X⊗Π + I⊗ (I-Π).




  
Block-measurement.
Suppose we have U_Π that is a block encoding of a projector Π, i.e., 

    Π- (I_s ⊗⟨0^a|) U_Π (I_s ⊗|0^a⟩ )
    ≤ϵ.

Then, we can perform a measurement procedure called “block-measurement” <cit.>. 
The circuit for block-measurement is defined as 

    U_ℳ= 
     (U_Π^†⊗ I_α)·C_Π_aNOT· (U_Π⊗ I_α),

where α denotes the single ancilla qubit and Π_a = I_s ⊗|0^a⟩⟨0^a|.




Let Λ̃_Π be a quantum channel by tracing out the a qubits of U_ℳ. Then, the following lemma is shown:


    Let Λ_Π be a quantum channel that maps as 
    
    |0⟩_α⊗|ψ⟩→|1⟩_α⊗Π|ψ⟩ + |0⟩_α⊗ (I_s-Π)|ψ⟩.

    Then 
    
    Λ_Π - Λ̃_Π_♢ = O(ϵ),

    where ·_♢ is the diamond norm. 

We call the ancilla qubit labeled by α as the output qubit of the block-measurement. 




 §.§ Notation



In this subsection, we introduce some notation. 
We use a special state Θ, which is called an absorbing state in the literature of random walks. 
Let S_k X^±_k∪{Θ}. 
This is the state space of our random walks on simplicial complexes. 
For any |σ⟩ where σ∈ S_k,
we identify an (n+2)-qubit computational basis state as follows: 

    |σ⟩=
    |x_σ⟩⊗|00⟩    if σ∈ X^+_k, 
    |x_σ⟩⊗|10⟩    if σ∈ X^-_k, 
    |0^n⟩⊗|01⟩    if σ=Θ,

where x_σ∈ X_k is the Hamming weight k+1 n-bit string that represents the unoriented simplex that corresponds to σ.
We also use 

    s(σ)= 
    
        0     if σ∈ X^+, 
    
        1     if σ∈ X^-.

Therefore, for σ∈ X^±_k, 

    |σ⟩=
        |x_σ,s(σ),0⟩.

For σ∈ X^±_k, we use σ_+ as
σ_+=σ if σ∈ X^+_k and σ_+=σ̅ if σ∈ X^-_k. 
Then, σ_-σ_+. 
Also, let Π_k be a projector onto the space spanned by {|σ⟩}_σ∈ X^+_k={|x_σ⟩⊗|00⟩}_σ∈ X^+_k
and let Π^±_k be a projector onto the space spanned by {|σ⟩}_σ∈ X^±_k


.

For σ∈ X^±_k, we also introduce the following notation:



  * i(σ)∈ [n]: the position of i-th 0 of x_σ.  (i∈ [n-k-1].)

  * ĩ(σ) ∈ [n]: the position of i-th 1 of x_σ. (i∈ [k+1].)





§ QUANTUM WALKS AND HOMOLOGY OF SIMPLICIAL COMPLEXES



We begin this section by introducing our main results on the implementation of projectors which contains three folds in Section <ref>. 
First, we propose a Markov transition matrix P^up, which could aid in encoding two projectors. One projector has support consisting of the k-cocycle, while the other has support consisting of the k-boundary. 
Second, we employ a similar approach, substituting P^up with another transition matrix P^down, to encode two projectors. One has support consisting of the k-cycle, while the other has support consisting of the k-coboundary.
Third, one projector of the k-th homology group is encoded using another  transition matrix P.

The relationships among the subspaces are depicted in Figure <ref>. 



Then, the proofs for these results are presented in Section <ref>, which consists of three steps. 
First, we formally define the Markov transition matrices P^up, P^down, and P, and utilize them to establish three types of quantum walks, denoted as U^up, U^down, and U^h, respectively.
Secondly, we demonstrate the utility of these quantum walks in encoding Δ^up_k, Δ^down_k, and Δ_k.
Finally, quantum singular value transformations are applied to the above Laplacians, resulting in the projectors in our main result.




 §.§ Formal statements of quantum walk based projectors


We formally present three main results, each of which is derived through the utilization of the three aforementioned quantum walks.


Recall that we say U is a Π_s-projected (a,α,ϵ)-unitary encoding of A if 
    
    A-a (Π_s ⊗⟨0^α|) U (Π_s ⊗|0^α⟩ )
        ≤ϵ.




Given a simplicial complex X over n-vertices, 
there exist Markov transition matrices 
P^up, P^down, P
on S_k=X^±_k ∪{Θ}  
and quantum walk unitaries
U^up, U^down, U^h, that are Π^±_k-projected (1,α,0)-unitary encodings of Π^±_k P^upΠ^±_k, Π^±_k P^downΠ^±_k, Π^±_k P Π^±_k, respectively, 
s.t. 
we can implement U_Z^k, U_B_k, U_Z_k,  U_B^k,  U_ℋ_k using quantum walk unitaries that are
Π_k-projected  (1,α,ϵ)-unitary encodings of 
Proj(Z^k), Proj(B_k), Proj(Z_k), Proj(B^k), Proj(ℋ_k), respectively.
Let Π= Π_k⊗|0^α⟩⟨0^α|. 
The implementation can be done with












  * 𝒪(K^uplog(1/ϵ)/λ_k^up)-number of use of 
U^up, (U^up)^†, C_ΠNOT and single qubit gates for U_Z^k and U_B_k, 

  * 𝒪(K^downlog(1/ϵ)/λ_k^down)-number of use of 
U^down, (U^down)^†, C_ΠNOT and single qubit gates for U_Z_k and U_B^k, 

  * 𝒪(Klog(1/ϵ)/λ_k)-number of use of 
U^h, (U^h)^†, C_ΠNOT and single qubit gates for U_ℋ_k.


Here,
λ_k^up, λ_k^down, λ_k are the smallest non-zero eigenvalues of Δ_k^up, Δ_k^down, Δ_k, respectively.  






























































































































In the above theorem, unitary encoding of Proj(ℋ_k) is implemented using the harmonic quantum walk unitary U^h. 
As a corollary of Theorem <ref>, 
we can alternatively implement a projector onto ℋ_k by combining the up quantum walk U^up and the down quantum walk U^down. 




Given a simplicial complex X over n-vertices, 
we can implement U_ℋ_k  
such that 

    (Π_k⊗⟨0^2α|) U_ℋ_k(Π_k⊗|0^2α⟩)=Π̃_ℋ_k

    where

    Proj(ℋ_k) -Π̃_ℋ_k≤ϵ,

with 
𝒪(K^downlog(1/ϵ)/λ_k^down+K^uplog(1/ϵ)/λ_k^up)-number of use of 
U^down, (U^down)^†, U^up, (U^up)^†, C_ΠNOT and single qubit gates with Π= Π_k⊗|0^α⟩⟨0^α|.




    This result is based on taking the product of projected unitary encoding of projectors onto k-cycle and k-cocycle (Theorem <ref>).  
    Note that ℋ_k=Z_k∩ Z^k. 
    Using the method of taking the product of block-encoded matrices of <cit.>, the theorem follows. 




 §.§ Proof of Theorem <ref>




We complete the proofs of our theorems in the subsequent subsections as follows. 
In Section <ref>,
we define the Markov transition matrix P^up and show an encoding of Δ^up_k into up quantum walk.
In Section <ref>,
we define the Markov transition matrix P^down and show an encoding of Δ^down_k into up quantum walk.
In Section <ref>,
we define the Markov transition matrix P and show an encoding of Δ_k into harmonic quantum walk.
In Section <ref>,
we show how to approximately implement the encoding of projectors and show the complexity of the procedures. 










  §.§.§ Up quantum walk and encoding of up Laplacian



We start by formally defining the up random walk on simplicial complexes. 
Let us introduce the following normalization factor for up random walk:

    K^upmax_σ∈ X^±_k∑_i∈[n-k-1]
    j∈ [k+2] w(i(σ))w(j̃(σ^↑(i))).


Note that K^up∈ poly(n) as long as the w(v)∈ poly(n) for all v∈ V. 
Let us also define

    η^up_σ 1- 1/K^up∑_σ'∈ X^+_k|(Δ_k^up )_σ',σ_+|.



    

    We define a Markov chain transition matrix P^up:S_k→ S_k for up random walk as follows

    (P^up)_σ,σ'   =
        ∑_u ∈ up(σ) w(u)^2 /K^up
            ,     if σ≠Θ and σ=σ'
    
            w(v_σ)w(v_σ')/K^up,    if σ≠Θ,  σ∼_↑σ'
            
    η_σ^up    if σ≠Θ and σ'=Θ
    
            1,     if σ=σ'=Θ 
    
            0,     otherwise.




This is a random walk on oriented k-simplices and an additional absorbing state Θ. A k-simplex moves to up-adjacent simplex σ' with probability w(v_σ)w(v_σ')/K^up. The lazyness for σ is given by ∑_u ∈ up(σ) w(u)^2/K^up . For unweighted simplicial complexes, ∑_u ∈ up(σ) w(u)^2 is equivalent to the up-degree of σ.

Recall that the matrix representation of up Laplacian is
 
    (Δ^up_k)_σ,σ'= ∑_u ∈ up(σ) w(u)^2,     if σ=σ' 
    
            w(v_σ)w(v_σ'),     if σ∼_↑σ'
    
            -w(v_σ)w(v_σ'),     if σ∼_↑σ'
    
            0,     otherwise.

From the matrix representation of the up Laplacian, it can be seen that 

    (P^up)_σ,σ'=
         (Δ_k^up)_σ_+,σ_+/K^up,     if σ≠Θ and σ=σ'
    
            |(Δ_k^up)_σ_+',σ_+|/K^up,    if σ≠Θ,  σ∼_↑σ'
            
    η_σ^up    if σ≠Θ and σ'=Θ
    
            1,     if σ=σ'=Θ 
    
            0,     otherwise.

 


We then consider the quantization of the up random walk. 
Suppose we have a projected unitary encoding of Π^±_k P^upΠ^±_k, then we can construct an encoding of the up Laplacian by taking the coherent interference between the positively oriented simplices and corresponding negatively oriented simplices after the application of a quantum walk step:



Given a simplicial complex X over n-vertices,  
 let U^up be a Π^±_k-projected (1,α,0)-unitary encoding of Π^±_k P^upΠ^±_k i.e.,
   
    (Π^±_k⊗⟨0^α|)
        U^up(Π^±_k⊗|0^α⟩)= Π^±_kP^upΠ^±_k.

    Then, V^up((I_n⊗ HZ⊗ I)⊗ I_α)U^up 
    satisfies
     
    (Π_k⊗⟨0^α|)
        V^up(Π_k⊗|0^α⟩)= Δ_k^up/K^up√(2).
 




For σ^+_x,σ^+_y ∈ X^+_k,  
let us denote the corresponding unoriented simplices by x,y ∈{0,1}^n, respectively.
Then, for all σ^+_x,σ^+_y ∈ X^+_k,
    
    (⟨σ^+_y|⊗⟨0^α|) V^up (|σ^+_x⟩⊗|0^α⟩)   = 
         (⟨y|⟨00|⊗⟨0^n+2|) V^up (|x⟩|00⟩⊗|0^n+2⟩)
        = 
        (⟨y|⟨00|-⟨10|/√(2)⊗⟨0^n+2|) U^up(|x⟩|00⟩⊗|0^n+2⟩)
        =
        (⟨σ_y^+|-⟨σ_y^-|/√(2)⊗⟨0^n+2|) U^up(|σ_x^+⟩⊗|0^n+2⟩)
        = 
        1/√(2)(
        P^up_σ_x^+,σ_y^+
        -P^up_σ_x^+,σ_y^-)
        
       =
        1/√(2)P^up_σ_x^+,σ_y^+,     if σ_x^+=σ_y^+ 
    1/√(2)P^up_σ_x^+,σ_y^+,    if σ_x^+∼_↑σ_y^+
    
           - 1/√(2)P^up_σ_x^+,σ_y^-,    if σ_x^+∼_↑σ_y^-
            
    
            0,     otherwise.

Using the relationship between the Markov transition matrix and the up Laplacian of eq. (<ref>), we can further compute

    (⟨σ^+_y|⊗⟨0^α|) V^up (|σ^+_x⟩⊗|0^α⟩)    =
        1/K^up√(2)(Δ^up_k)_σ_x^+,σ_x^+,     if σ_x^+=σ_y^+ 
    1/K^up√(2)|(Δ^up_k)_σ_x^+,σ_y^+|,    if σ_x^+∼_↑σ_y^+
    
            -1/K^up√(2)|(Δ^up_k)_σ_x^+,σ_y^+|,    if σ_x^+∼_↑σ_y^-
            
    
            0,     otherwise.
        
       =
        1/K^up√(2)(Δ^up_k)_σ_x^+,σ_x^+,     if σ_x^+=σ_y^+ 
    1/K^up√(2)(Δ^up_k)_σ_x^+,σ_y^+,    if σ_x^+∼_↑σ_y^+
    1/K^up√(2)(Δ^up_k)_σ_x^+,σ_y^+,    if σ_x^+∼_↑σ_y^-
            
    
            0,     otherwise.


    
   Therefore, it can be observed that
   
    (Π_k ⊗⟨0^α|)
        V^up(Π_k⊗|0^α⟩)= 1/K^up√(2)Δ^up_k.




    There could be several ways of realizing the unitary encoding of Π^±_k P^upΠ^±_k. 
For example, based on the Szegedy type quantum walk, we can consider the following unitary that acts on two state registers for all σ∈ S_k: 
    
    U: |σ⟩|0^n+2⟩→∑_σ'∈ S√(P^up_σ,σ')|σ⟩|σ'⟩.

Then, we can construct a projected unitary encoding of P^up by U^†·SWAP·  U:


    (Π^±_k⊗⟨0^n+2|)
        U^†·SWAP·  U (Π^±_k⊗|0^n+2⟩)= Π^±_k P^upΠ^±_k.

This is because   for all σ_x,σ_y ∈ S_k,
    
    (⟨σ_y|⊗⟨0^n+2|) U^†·SWAP·  U (|σ_x⟩⊗|0^n+2⟩)
           =(
           ∑_σ_y'∈ S_k√(P^up_σ_y,σ_y')⟨σ_y|⟨σ_y'|) 
          (∑_σ_x'∈ S_k√(P^up_σ_x,σ_x')|σ_x'⟩|σ_x⟩)
       = √(P^up_σ_x,σ_y)√(P^up_σ_y,σ_x),

and for all σ_x,σ_y ∈ X^±_k, 

    (⟨σ_y|⊗⟨0^n+2|) U^†·SWAP·  U(|σ_x⟩⊗|0^n+2⟩)=√(P^up_σ_x,σ_y)√(P^up_σ_y,σ_x)= P^up_σ_x,σ_y

because the Markov transition matrix is symmetric except for the elements related to the absorbing state Θ. 
In Section <ref> we give explicit construction of the unitary encoding of Markov chain for clique complexes. 





  §.§.§ Down quantum walk and encoding of down Laplacian



Let us introduce the following normalization factor for a down random walk:

    K^downmax_σ∈ X^±_k∑_i∈[k+1],j∈ [n-k] w(ĩ(σ))w(j̃(σ^↓(i))).

Note that K^down∈ poly(n) as long as the w(v)∈ poly(n) for all v∈ V. 
Let us also define

    η^down_σ 1- 1/K^down∑_σ'∈ X^+_k|(Δ_k^down )_σ',σ_+|.



    
    We define a Markov chain transition matrix P^down:S_k→ S_k for a down random walk as follows:

    (P)^down_σ,σ'=
        ∑_v ∈σ w(v)^2/K^down,     if σ≠Θ and σ=σ'
    
            w(v_σ)w(v_σ')/K^down,    if σ≠Θ,  σ∼_↓σ'
            
    η_σ^down    if σ≠Θ and σ'=Θ
    
            1,     if σ=σ'=Θ 
    
            0,     otherwise.




Recall that the matrix representation of the down Laplacian for σ, σ' ∈ X^+_k is 

    (Δ^down_k)_σ,σ'=
        ∑_v ∈σ w(v)^2,     if σ=σ' 
    
            w(v_σ)w(v_σ'),     if σ∼_↓σ'
    
            -w(v_σ)w(v_σ'),     if σ∼_↓σ'
    
            0,     otherwise.


Then, it can be seen that 


    (P^down)_σ,σ'=
         (Δ_k^down)_σ_+,σ_+/K^down,     if σ≠Θ and σ=σ'
    
            |(Δ_k^down)_σ_+',σ_+|/K^down,    if σ≠Θ,  σ∼_↓σ'
            
    η_σ^down,     if σ≠Θ and σ'=Θ
    
            1,     if σ=σ'=Θ 
    
            0,     otherwise.









With a projected unitary encoding of P^down, we can construct a unitary in which down Laplacian is encoded:




Given a simplicial complex X over n-vertices, 
let U^down be a Π^±_k-projected (1,α,0)-unitary encoding of Π^±_k P^downΠ^±_k i.e.,
    
    (Π^±_k⊗⟨0^α|)
        U^down(Π^±_k⊗|0^α⟩)=Π^±_k P^downΠ^±_k.

    Then, V^down((I_n⊗ HZ⊗ I)⊗ I_α)U^down satisfies
     
    (Π_k⊗⟨0^α|)
        V^down(Π_k⊗|0^α⟩)= Δ_k^down/K^down√(2).
 


    The proof is almost similar to the proof of Proposition <ref>. With a similar calculation, we can show that 
        
    (⟨σ^+_y|⊗⟨0^α|) V (|σ^+_x⟩⊗|0^α⟩)   = 
        1/√(2)(
        P^down_σ_x^+,σ_y^+
        -P^down_σ_x^+,σ_y^-)
        
       =
        1/√(2)P^down_σ_x^+,σ_y^+,     if σ_x^+=σ_y^+ 
    1/√(2)P^down_σ_x^+,σ_y^+,    if σ_x^+∼_↓σ_y^+
    
           - 1/√(2)P^down_σ_x^+,σ_y^-,    if σ_x^+∼_↓σ_y^-
            
    
            0,     otherwise
        
       =
        1/K^down√(2)(Δ^down_k)_σ_x^+,σ_x^+,     if σ_x^+=σ_y^+ 
    1/K^down√(2)(Δ^down_k)_σ_x^+,σ_y^+,    if σ_x^+∼_↓σ_y^+
    1/K^down√(2)(Δ^down_k)_σ_x^+,σ_y^+,    if σ_x^+∼_↓σ_y^-
            
    
            0,     otherwise.





  §.§.§ Harmonic quantum walk and encoding of full Laplacian


In this subsection, we introduce the random walk on simplicial complexes that we will quantize in the subsequent section. 

Given a directed simplicial complex X^±,
define 


    K max_σ∈ X^±_k(
    ∑_i∈ [n] w(i)^2
    +
    ∑_i∈ [n-k-1],
    j∈ [k+1] w(i(σ))w(j̃(σ))
    ).

Note that K∈ poly(n) as long as the w(v)∈ poly(n) for all v∈ V. 
Then, let us also introduce 

    η_σ 1- 1/K∑_σ'∈ X^+_k|(Δ_k )_σ',σ_+|.




    

We define a Markov chain transition matrix P:S_k→ S_k as follows

    (P)_σ,σ'   =
        (∑_u ∈ up(σ) w(u)^2+∑_v ∈σ w(v)^2)/K,     if σ≠Θ and σ=σ'
    
            w(v_σ)w(v_σ')/K,    if σ≠Θ, σ∼_↓σ'  and σ_↑σ'
    η_σ    if σ≠Θ and σ'=Θ
    
            1,     if σ=σ'=Θ 
    
            0,     otherwise.



It can be seen that this is a stochastic matrix, i.e., ∑_σ'∈ S_k (P)_σ,σ'=1 for all σ∈ S_k.
Recalling the matrix representation of the combinatorial Laplacian 
    
    (Δ_k)_σ,σ'=
        (σ)+k+1,     if σ=σ' 
    
            1,    if σ∼_↓σ' and σ_↑σ'
    
            -1,    if σ∼_↓σ' and σ_↑σ' 
    
            0,     otherwise,

it can be seen that

    (P)_σ,σ'=
        
            (Δ_k)_σ_+,σ_+/K ,     if σ≠Θ and σ=σ'
    
            |(Δ_k)_σ_+',σ_+|/K,    if σ≠Θ, σ∼_↓σ'  and σ_↑σ'
    η_σ    if σ≠Θ and σ'=Θ
    
            1,     if σ=σ'=Θ 
    
            0,     otherwise.












Based on this definition, we show the following proposition:




Given a simplicial complex X over n-vertices, 
suppose that U^h is a Π^±_k-projected (1,α,0)-unitary encoding of Π^±_k P Π^±_k i.e.,
    
    (Π^±_k⊗⟨0^α|)
        U^h(Π^±_k⊗|0^α⟩)=Π^±_k P Π^±_k.

Let V^h= ((I_n⊗ HZ⊗ I)⊗ I_n+2)((U^h)^†·SWAP· U^h) 
Then, V^h satisfies
 
    (Π_k⊗⟨0^n+2|)
        V^h (Π_k⊗|0^n+2⟩)= Δ_k/K√(2).
 



The proof is similar to the proof of Proposition <ref>.
In this case, for all σ^+_x,σ^+_y ∈ X^+_k,
    
    (⟨σ^+_y|⊗⟨0^α|) V^h (|σ^+_x⟩⊗|0^α⟩)
            = 
        1/√(2)(
        P_σ_x^+,σ_y^+
        -P_σ_x^+,σ_y^-)
        
       =
        1/K√(2)(Δ_k)_σ_x^+,σ_x^+,     if σ_x^+=σ_y^+ 
    
            0,    if σ_x^+∼_↓σ_y^+ and σ_x^+∼_↑σ_y^-
    
           0,    if σ_x^+∼_↓σ_y^- and σ_x^+∼_↑σ_y^+
            
    1/√(2)P_σ_x^+,σ_y^+,    if σ_x^+∼_↓σ_y^+ and σ_x^+_↑σ_y^-
    
           - 1/√(2)P_σ_x^+,σ_y^-,    if σ_x^+∼_↓σ_y^- and σ_x^+_↑σ_y^+
            
    
            0,     otherwise.

Then, we can conclude the proof of the proposition.






    We can give a different definition of harmonic random walk on simplicial complexes as follows:


    (P')_σ,σ'   =
        (∑_u ∈ up(σ) w(u)^2+∑_v ∈σ w(v)^2)/K,     if σ≠Θ and σ=σ'
    
            w(v_σ)w(v_σ')/K,    if σ≠Θ, σ∼_↓σ'  or σ∼_↑σ'
            
    η_σ,     if σ≠Θ and σ'=Θ
    
            1,     if σ=σ'=Θ 
    
            0,     otherwise.

Note that σ∼_↓σ' and σ∼_↑σ' do not coincide. 
Although this definition also works for the quantization and quantum encoding of the Laplacian, we mainly consider the definition in Section <ref> in this paper.







  §.§.§ Implementing the unitary encoding of projectors






In this subsection, we finally show how to implement the unitary encoding of the projector onto the k-cocycle Z^k=(∂^*_k+1)=(Δ^up_k) of vertex-weighted simplicial complexes using up quantum walk. 

The projector can be implemented by applying the quantum singular value transformation (QSVT) <cit.> to V^up of Proposition <ref>, which is a unitary encoding of the up Laplacian. 
We use the following polynomial, which is an approximation of the rectangle function, to transform the eigenvalues.



Let δ,ϵ∈(0,1/2) and t∈ [-1,1]. There exists an even polynomial P∈ℝ[x] of degree 𝒪(log(1/ϵ)/δ), such that |P(x)|≤ 1 for all x∈[-1,1], and 

    {[                P(x)∈ [0,ϵ], ∀ x∈[-1,-t-δ]∪ [t+δ,1], and;              P(x)∈ [1-ϵ,1],            ∀ x∈ [-t+δ,t-δ]. ].



Let λ̃_k^upλ^up_k/√(2)K^up where λ^up_k is the smallest non-zero eigenvalue of Δ^up_k.
We perform QSVT with this polynomial by taking t=λ̃_k^up/2 and δ=λ̃_k^up/4.
Then, the degree of P(x) is T= 𝒪(K^uplog(1/ϵ)/λ^up_k). 
By performing QSVT for V^up, 
we can implement V^up_T s.t. 
    
    (Π_k⊗⟨00|⊗⟨0^α|) V^up_T (Π_k⊗|00⟩⊗|0^α⟩)
           =
        P( 
        Δ^up_k/√(2)K)
       =
        ∑_i
        P(λ^up_i/√(2)K) 
        |ψ_i⟩⟨ψ_i|
       =:
        Π̃_Z^k,

    where {λ^up_i,|ψ_i⟩}_i are the eigenvalues and eigenvectors of Δ^up_k.
    Then, Π̃_Z^k satisfies 
    
    Proj(Z^k)-Π̃_Z^k≤ϵ.

The unitary V^up_T can be implemented using T= 𝒪(Klog(1/ϵ)/λ_k) number of 
 V^up,(V^up)^†, C_Π NOT gates and other single qubit gates.

With up quantum walk, we can also implement the unitary encoding of the projector onto the k-boundary B_k= Im(∂_k+1)=Im(Δ^up_k). 
    
 In this case, instead of using the polynomial of Lemma <ref>, 
    we use a polynomial P(x) s.t. 

    {[              P(x)∈ [1-ϵ,1], ∀ x∈[-1,-t-δ]∪ [t+δ,1], and;                P(x)∈ [0,ϵ],            ∀ x∈ [-t+δ,t-δ]. ].

of <cit.>. 
By performing QSVT with this polynomial, we can implement U_B_k with the desired complexity. 


With down quantum walks, we can similarly implement projectors onto k-cycle Z_k=(∂_k)=(Δ^down_k) and k-coboundary B^k=Im(∂_k^*).

Finally, we can implement a projector onto the harmonics with the harmonic quantum walk in a similar way as in the case of the up walk and down walk. 

This concludes the proof of Theorem <ref>.





§ EFFICIENT CONSTRUCTION OF QUANTUM WALK UNITARIES FOR CLIQUE COMPLEXES




In this section, we show efficient constructions of up, down, and harmonic quantum walk unitaries for clique complexes.
When we use 𝒪̃, it hides factors in polylog(n), where n is the number of vertices. 
In the following, we assume that quantum access to graph adjacency matrices and vertex-weighting functions can be done in at most linear time in n. 
We will prove the following theorem.













































Let X be a vertex-weighted clique complex over n vertices and P^up, P^down, P be the Markov transition matrices of Definitions <ref>, <ref>, <ref>. 
Suppose that (P^up)_σ,σ', (P^down)_σ,σ', (P)_σ,σ' can be represented with t-bits with t∈𝒪( log (1/ϵ) + log n ) for every σ,σ' ∈ S_k and we are given the normalization factors K^up, K^down and K. 
Then we can 
construct U^↑↓_k, U^↓↑_k, U^h_k such that 
it holds for all σ,σ' ∈ X^±_k that 

    
  * |(P^up)_σ,σ' - ⟨σ'|⟨0^n+2|⟨0^m,0^m|
(U^↑↓_k)^†·SWAP· U^↑↓_k
|σ⟩|0^n+2⟩|0^m,0^m⟩|
≤ϵ,
    
  * | (P^down)_σ,σ'-⟨σ'|⟨0^n+2|⟨0^m,0^m|
(U^↓↑_k)^†·SWAP· U^↓↑_k
|σ⟩|0^n+2⟩|0^m,0^m⟩|
≤ϵ,

  * | 
P_σ,σ'-⟨σ'|⟨0^n+2|⟨0^m,0^m|
(U^h_k)^†·SWAP· U^h_k
|σ⟩|0^n+2⟩|0^m,0^m⟩| ≤ϵ,

with 𝒪̃(n^2log(1/ϵ)) gates and m=𝒪(log n), 
where the SWAP operator swaps between the first and the second n+2-qubit registers and the two m-qubit registers, respectively. 



In Section <ref>, we introduce notations that we use in the proof. 
In Section <ref>, we give the proof of the first part of the theorem (construction of U^↑↓_k). 
In Section <ref>, we give the proof of the second part of the theorem (construction of U^↓↑_k). 
In Section <ref>, we give the proof of the third part of the theorem (construction of U^h_k). 


























































 §.§ Notations



Before giving the proofs of theorems, we introduce several notations for the proofs. 




We denote f(σ)=0 if σ∈ X^± and f_k(σ)=1 if σ∉ X^±.


We denote the state representing an oriented k-simplex σ∈ X^±_k by |σ⟩=|x_σ,s(σ),0⟩ where x_σ is the Hamming weight k+1 n-bit string that represents the unoriented simplex that corresponds to σ and  

    s(σ)= 
    
        0     if σ∈ X^+_k, 
    
        1     if σ∈ X^-_k.


















For σ∈ X^±_k, we define 


  * i(σ)∈ [n]: the position of i-th 0 of x_σ.  (i∈ [n-k-1].)

  * ĩ(σ) ∈ [n]: the position of i-th 1 of x_σ. (i∈ [k+1].)

Then, we introduce

    
  * x_σ^↑(i) x_σ⊕ 0^i(σ)-110^n-i(σ) for i∈ [n-k-1].
    
  * x_σ^↓(i) x_σ⊕ 0^ĩ(σ)-110^n-ĩ(σ) for i=1,2,...,k+1.

These are the descriptions of the unoriented simplices obtained by adding a vertex i(σ) to σ and removing a vertex ĩ(σ), respectively. 
Note that x_σ^↓(i) ∈ X_k-1 always holds but x_σ^↑(i) ∈ X_k+1 does not always holds. 
Then, we define


  * Parity of i-th 0 of σ: P(i,σ)⊕_j=1^i(σ)x_σ_j.

  * Parity of i: P̃(i)=0 if i is odd and P̃(i)=1 if i is even.

Using these notations, we can define


  * σ^↑(i): k+1-simplex corresponding to x_σ^↑(i) with orientation P(i,σ).


  * σ^↓(i): k-1-simplex corresponding to x^↓_σ(i) with orientation P̃(i).  

These are cofaces and faces of σ with the induced orientations (as long as x_σ^↑(i) ∈ X_k+1). 
Finally, we introduce


  * x_σ^↑↓(i,j) 
x_σ^↑(i)
⊕ 0^j̃(σ^↑(i))-110^n-j̃(σ^↑(i)).

  * x_σ^↓↑(i,j) x_σ^↓(i)
⊕ 0^j(σ^↓ (i))-110^n-j(σ^↓ (i)).

The first n-bit string represents the unoriented simplex obtained by removing a vertex j̃(σ^↑(i)) from σ^↑(i). 
The second n-bit string represents the unoriented simplex obtained by adding a vertex j(σ^↓ (i)) to σ^↓(i).
Corresponding to the removed and added vertices, we define the following functions of the product of weights. 


  * w_σ^↑↓(i,j) w(i(σ))w(j̃(σ^↑(i))) for all i∈ [n-k-1],j∈[k+2] .

  * w_σ^↓↑(i,j) w(ĩ(σ))w(j(σ^↑(i))).








 §.§ Proof of the first part of Theorem <ref>







We first provide the construction of U^↑↓_k. 



The construction is given using a quantum membership unitary M that acts
for all b∈{0,1} and σ∈{0,1}^n+2 as follows: 

    M|σ⟩|b⟩=|σ⟩|b⊕ f(σ)⟩,

where f(σ)=0 if σ∈ X^± and f(σ)=1 if σ∉ X^±.

Let U^↑↓_k be a unitary constructed in the following steps.  

    
  * For |σ⟩, compute the positions of 0's of x_σ in an ancilla register:
    
    ⊗_i∈ [n-k-1] |i(σ)⟩.

    
  * Further compute j̃(σ^↑(i)) for j∈ [k+2] to create the following ancilla state:
    
    ⊗_i∈ [n-k-1] ,j∈[k+2]|i(σ)⟩|j̃(σ^↑(i))⟩.


    
  * Compute the following  weights using the above ancilla state in another ancilla register:
    
    ⊗_i∈ [n-k-1],j∈[k+2] |w_σ^↑↓(i,j)/K^up⟩,

    where w_σ^↑↓(i,j)=w(i(σ))w(j̃(σ^↑(i))).
    In this step, we have used two calls to the vertex-weighting functions.
    
  * Then, following <cit.>, approximately prepare the following state for all initial states |σ⟩|0^n+2⟩= |x_σ,s(σ),0⟩|0^n+2⟩ where σ∈ X^±_k:
    
    |σ⟩|0^n+2⟩∑_i∈ [n-k-1],j∈[k+2]√(w_σ^↑↓(i,j)/K^up)|i,j⟩.

    Although we do not prepare this state exactly, we use this exact expression in the following for simplicity. We give a complexity and error analysis later. 
    
  * Create the following state using  ⊗_i∈ [n-k-1] ,j∈[k+2]|i(σ)⟩|j̃(σ^↑(i))⟩:
    
    |σ⟩|0^n+2⟩∑_i∈ [n-k-1],j∈[k+2]√(w_σ^↑↓(i,j)/K^up)|i(σ),j̃(σ^↑(i))⟩.

    
  * Then, create the following state:
    
    ∑_i∈ [n-k-1],
    j∈[k+2]√(w_σ^↑↓(i,j)/K^up)|σ⟩|x_σ^↑↓(i,j),s(σ)⊕ P(i,σ)⊕P̃(j,σ^↑(i)),f(σ^↑(i))⟩|i(σ),j̃(σ^↑(i))⟩.


This computation is based on the following sub-steps:

    
  * Recall that x_σ^↑↓(i,j)= x_σ⊕ 0^i(σ)-110^n-i(σ)⊕ 0^j̃(σ^↑(i))-110^n-j̃(σ^↑(i)). 
    Therefore, |x_σ^↑↓(i,j)⟩ can be computed by copying x_σ from |σ⟩ and applying X-gates to i(σ)-th qubit and j̃(σ^↑(i))-th qubit conditioned on that the state of the last register is |i(σ),j̃(σ^↑(i))⟩.
    
  * The state |s(σ)⊕ P(i,σ)⊕P̃(j,σ^↑(i))⟩ can be prepared by copying s(σ) from |σ⟩ and computing the “parity” of |i(σ),j̃(σ^↑(i))⟩. 
    
  * The state |f(σ^↑(i))⟩ can be computed by applying the membership unitary M to the state |x_σ⊕ 0^i(σ)-110^n-i(σ)⟩ (which appear in the intermediate of step (a)).


    
  * Conditioned that f(σ^↑(i))=1, uncompute the above step (this is to move to the absorbing state if σ^↑(i)∉ X^±_k+1). 

    
  * Uncompute the following ancilla registers:
 
    ⊗_i∈ [n-k-1] ,j∈[k+2]|i(σ)⟩|j̃(σ^↑(i))⟩.

    
    ⊗_i∈ [n-k-1],j∈[k+2] |w_σ^↑↓(i,j)/K^up⟩.



Note that in the above construction, we only used one query to the membership oracle and 𝒪(n) query to the weight functions. 







For all σ∈ X^±_k, U^↑↓_k approximately acts as follows: 


    U^↑↓_k|σ⟩|0^n+2⟩|0^m,0^m⟩
       ≃∑_i:f(σ^↑(i))=0,j∈[k+2]√(w_σ^↑↓(i,j)/K^up)|σ⟩|x_σ^↑↓(i,j),s(σ)⊕ P(i,σ)⊕P̃(j,σ^↑(i)),0⟩|i(σ),j̃(σ^↑(i))⟩
           +
     ∑_i:f(σ^↑(i))=1,j∈[k+2]√(w_σ^↑↓(i,j)/K^up)|σ⟩|Θ⟩|i(σ),j̃(σ^↑(i))⟩.


The state |x_σ^↑↓(i,j),s(σ)⊕ P(i,σ)⊕P̃(j,σ^↑(i)),0⟩ can be seen as the representation of  simplex with vertices x_σ^↑↓(i,j) and orientation s(σ)⊕ P(i,σ)⊕P̃(j,σ^↑(i)). Let us denote such a simplex as σ^↑↓(i,j). 

For i∈[n-k-1] such that f(σ^↑(i))=0 (i.e., σ^↑(i)∈ X^±_k+1), we can show that  σ∼_↑σ^↑↓(i,j)  
for any j∈ [k+2]. This is because x^↑(i(σ))  is the common upper simplex of them and the orientation induced by them s(σ)⊕ P(i,σ).


Therefore, 


    U^↑↓_k|σ⟩|0^n+2⟩|0^m,0^m⟩
       ≃∑_i:f(σ^↑(i))=0,j∈[k+2]√(w_σ^↑↓(i,j)/K^up)|σ⟩|σ^↑↓(i,j)⟩|i(σ),j̃(σ^↑(i))⟩
           +
        ∑_i:f(σ^↑(i))=1,j∈[k+2]√(w_σ^↑↓(i,j)/K^up)|σ⟩|Θ⟩|i(σ),j̃(σ^↑(i))⟩.


Finally, it can be seen that for all σ,σ'∈ X^±_k,

    ⟨σ'|⟨0^n+2|⟨0^m,0^m|
    (U^↑↓_k)^†·SWAP· U^↑↓_k
    |σ⟩|0^n+2⟩|0^m,0^m⟩
    ≃   (∑_i':f(σ'^↑(i'))=0,
    j'∈[k+2]√(w_σ'^↑↓(i',j')/K^up)⟨σ'|⟨σ'^↑↓(i',j')|⟨i'(σ'),j̃'̃(σ'^↑(i'))|)
        
       ×(∑_i:f(σ^↑(i))=0,
    j∈[k+2]√(w_σ^↑↓(i,j)/K^up)|σ^↑↓(i,j)⟩|σ⟩|j̃(σ^↑(i)),i(σ)⟩)
        
       =
        w(v_σ)w(v_σ')/K^up    if σ∼_↑σ',
    ∑_u∈ up(σ)w(u)^2/K^up    if σ=σ',
    
    0     otherwise,

as desired.



  
Complexity and error analysis.
In the construction of U^↑↓_k, we use 𝒪(n) calls to the vertex-weighting function in step 3, and one call to the membership function in step 6. 
We assumed that the cost of calling the vertex-weighting function is 𝒪(n). 
The cost of implementing the membership function for clique complex is 𝒪(n^2) because it suffices to check the connection of all the pairs of vertices. The number of pair of vertices for k-simplices is k+12 and k≤ n-1.
The error in the construction comes from the creation of the superposition in step 4. As it is shown in <cit.>, the gate complexity for making the error of the amplitude in each of the superposition upper bounded by 𝒪(√(ϵ)) is 𝒪̃(nlog(1/ϵ)). 
Other computations in the construction can be done with 𝒪(n^2) size circuit with classical reversible gates. 
This concludes the proof of the first part of Theorem <ref>.



 §.§ Proof of the second part of Theorem <ref>




We first give a construction of U^↑↓_k. 
Let U^↑↓_k be a unitary that is constructed in the following steps: 


    
  * For |σ⟩, compute the positions of 1's of x_σ in an registers:
    
    ⊗_i∈ [k+1] |ĩ(σ)⟩.

    
  * Compute j(σ^↓(i)) for j∈ [n-k] to create the following ancilla state:
    
    ⊗_i∈ [k+1] , j∈ [n-k]|ĩ(σ)⟩|j(σ^↓(i))⟩.

    
  * Compute the following  weights in another ancilla register:
    
    ⊗_i∈ [k+1],j∈[n-k] |w_σ^↓↑(i,j)/K^down                              ⟩,

    where w_σ^↓↑(i,j) w(ĩ(σ))w(j(σ^↑(i))).
    
  * Then, following <cit.>, approximately prepare the following state for all initial states |σ⟩|0^n+2⟩ where σ∈ X^±_k:
    
    |x_σ,s(σ),0⟩|0^n+2⟩∑_i∈ [k+1],j∈[n-k]√(w_σ^↓↑(i,j)/K^down)|i,j⟩.

    
  * Create the following state using the information in ancilla registers:
    
    |x_σ,s(σ),0⟩|0^n+2⟩∑_i∈ [k+1],j∈[n-k]√(w_σ^↑↓(i,j)/K^up)|ĩ(σ),j(σ^↓(i))⟩.

    
  * Create the following state:
    
    ∑_i∈ [k+1],
    j∈[n-k]√(w_σ^↓↑(i,j)/K^down)|x_σ,s(σ),0⟩|x_σ^↓↑(i,j),s(σ)⊕P̃(i)⊕P(j,σ^↓(i)),f(x_σ^↓↑(i,j))⟩|ĩ(σ),j(σ^↓(i))⟩.

The computation is similar to the step 6 of the previous subsection.
    
  * Conditioned that f(x_σ^↓↑(i,j))=1 (i.e., x_σ^↓↑(i,j)∈ X_k), uncompute the above step. 
    
  * Uncompute the following ancilla registers:
    
    ⊗_i∈ [n-k-1] ,j∈[k+2]|i(σ)⟩|j̃(σ^↑(i))⟩,

   
    ⊗_i∈ [k+1],j∈[n-k] |w_σ^↓↑(i,j)/K^down                              ⟩.




The computation is similar to the first part of the proof of Theorem <ref>.
    In this case, it holds that 
    
    U^↓↑_k|σ⟩|0^n+2⟩|0^m,0^m⟩
       ≃∑_i∈ [k+1],
    j:f(x_σ^↓↑(i,j))=0√(w_σ^↓↑(i,j)/K^up)|σ⟩|σ^↓↑(i,j)⟩|ĩ(σ),j(σ^↓(i))⟩
       +
        ∑_i∈ [k+1],
    j:f(x_σ^↓↑(i,j))=1√(w_σ^↓↑(i,j)/K^up)|σ⟩|Θ⟩|ĩ(σ),j(σ^↓(i))⟩,

    where in the first term, 
    |σ^↓↑(i,j)⟩=
    |x_σ^↓↑(i,j),s(σ)⊕P̃(i)⊕P(j,σ^↓(i)),0⟩
    and σ∼_↓σ^↓↑(i,j). 
    This is because due to the condition that j:f(x_σ^↓↑(i,j))=0, σ and σ^↓↑(i,j) shares a same lower simplex and the orientation of the lower simplex induced by both σ and σ^↓↑(i,j) is s(σ)⊕P̃(i).

    The relation between the error and the complexity is similar to the case of the first part of Theorem <ref>. 
    Then, by a similar calculation as in the first part of the proof of Theorem <ref>, we can conclude the second part of the proof of the theorem. 





 §.§ Proof of the third part of Theorem <ref>



First, we show the following claim:



For σ,σ' ∈ X^±_k s.t. σ∼_↓σ', let v_σ and v_σ' be the vertices to be removed from σ and σ' to obtain the common lower simplex, respectively. It holds that s(σ')=s(σ)+ ∑_i∈ (v_σ, v_σ') (x_σ)_i  (mod 2) . Here, (v_σ, v_σ') are set of integers between v_σ+1 and v_σ'-1 if v_σ<v_σ' and integers between v_σ'+1 and v_σ-1 if v_σ'<v_σ .





Suppose that v_σ<v_σ'. Then, the lower simplex obtained by removing v_σ from σ has an orientation s(σ)+∑_i∈ [1,v_σ] (x_σ)_i+1 . Therefore, the orientation of σ' is 

    (s(σ)+∑_i∈ [1,v_σ] (x_σ)_i+1)+∑_j∈ [1,v_σ')(x_σ)_i+1 
    =
    s(σ)+ ∑_i∈ (v_σ, v_σ') (x_σ)_i  (mod 2).

Here, [1,v_σ')={1,2,...,v_σ'-1} and (x_σ)_i is the i-th bit of x_σ.
Next, suppose that v_σ'<v_σ. Then, the orientation of σ' is 

    (s(σ)+∑_i∈ [1,v_σ] (x_σ)_i+1)+∑_j∈ [1,v_σ'](x_σ)_i=s(σ)+ ∑_i∈ (v_σ', v_σ) (x_σ)_i  (mod 2).

This concludes the proof of the claim.




Then, we show the construction of U^h. Let U^h
be the unitary constructed in the following steps:

    
  * Compute the positions of 0's and 1's of σ:

    ⊗_i∈ [n-k-1] |i(σ)⟩⊗_j∈ [k+1] |j̃(σ)⟩.

    
  * Compute the following  weights in another ancilla register:
    
    ⊗_i∈ [n-k-1],j∈[k+1] w(i(σ))w(j̃(σ))/Kw(i(σ))^2/Kw(j̃(σ))^2/K.



  * Approximately create the following superposition following <cit.>:

    ∑_i∈ [n-k-1],
    j∈ [k+1]√(w(i(σ))w(j̃(σ))/K)|i(σ)⟩|j̃(σ)⟩|0⟩ 
    +
    ∑_i∈ [n-k-1]√(w(i(σ))^2/K)|i(σ)⟩|i(σ)⟩|1⟩
       
    +
    ∑_j∈ [k+1]√(w(j̃(σ))^2/K)|j̃(σ)⟩|j̃(σ)⟩|2⟩
    =: |ϕ(σ)⟩ .

The first term corresponds to the superposition for adjacency, the second term corresponds to the up degree, and the third term corresponds to a lower degree of σ. 


  * Prepare |σ⟩|0^n+2⟩|ϕ(σ)⟩.


  * Define 

    |ψ_ij(σ)⟩
       x_σ^↑(i) ⊕ 0^j̃(σ)-110^n-j̃(σ),s(σ)+⊕_m∈ (i(σ) ,j̃(σ))(x_σ)_m,f(x_σ^↑(i)⊕ 0^j̃(σ)-110^n-j̃(σ))⊕ f(x_σ^↑(i))⊕ 1.

Here, x_σ^↑(i) ⊕ 0^j̃(σ)-110^n-j̃(σ) is the unoriented simplex obtained by exchanging between the j-th vertex of σ and the i-th “empty vertex” of σ. 

  * Create the following state:

    ∑_i∈ [n-k-1],
    j∈ [k+1]√(w(i(σ))w(j̃(σ))/K)|σ⟩|ψ_ij(σ)⟩|i(σ)⟩|j̃(σ)⟩|0⟩
       
    +
    ∑_i∈ [n-k-1]√(w(i(σ))^2/K)|σ⟩|x_σ,s(σ),f(σ^↑(i(σ)))⟩|i(σ)⟩|i(σ)⟩|1⟩
       
    +
    ∑_j∈ [k+1]√(w(j̃(σ))^2/K)|σ⟩|σ⟩|j̃(σ)⟩|j̃(σ)⟩|1⟩.


  * Uncompute the above step conditioned on that the n+2-th qubit of the second register is |1⟩.



Note that in the above construction, we used 𝒪(1) query to the membership oracle and 𝒪(n) query to the weight functions. 


In the first term of eq. (<ref>), 
observe that f(x_σ^↑(i))=0 implies f(x_σ^↑(i)⊕ 0^j̃(σ)-110^n-j̃(σ))=0.  
This is because if f(x_σ^↑(i))=0 i.e., x_σ^↑(i)∈ X_k+1, 
x_σ^↑(i)⊕ 0^j̃(σ)-110^n-j̃(σ), which is a face of x_σ^↑(i), is also in X_k.

Then,

    f(x_σ^↑(i)⊕ 0^j̃(σ)-110^n-j̃(σ))⊕ f(x_σ^↑(i))⊕ 1 =0

means that f(x_σ^↑(i))=1 and f(x_σ^↑(i)⊕ 0^j̃(σ)-110^n-j̃(σ))=0. 
Therefore, 
it can be observed that 
f(x_σ^↑(i)⊕ 0^j̃(σ)-110^n-j̃(σ))⊕ f(x_σ^↑(i))⊕ 1 =0 
means that 
|ψ_ij(σ)⟩ 
are correct representations of “lower adjacent simplices of σ that are not upper adjacent” 
because due to Claim <ref>, 
⊕_m∈ (i(σ) ,j̃(σ))(x_σ)_m 
represents the relative orientation of lower adjacent simplices. 
In the second term of eq. (<ref>), 
the elements of superposition that satisfy f(σ^↑(i(σ)))=0 
corresponds to laziness due to the upper degree. 
These arguments also show that the uncomputation in step 7 leads to the absorbing state with the desired condition. 
The relationship between the error and the complexity is similar in the case of the first part of the proof of Theorem <ref>. 
Therefore, with a similar calculation, we can conclude the proof of the theorem.








§ APPLICATIONS







In this section, we apply the derived quantum walk algorithms to resolve the following three problems: estimation of the normalized Betti numbers, estimation of the normalized persistent Betti numbers, and the verification of the promise clique homology problem. 



 §.§ Estimating the normalized Betti numbers


In this subsection, we show how to estimate the Betti numbers using harmonic quantum walk on simplicial complexes. 



Given G=(V,E) where |V|=n, let X be a clique complex of the (unweighted) graph G and U^h be a  Π^±_k-projected (1,𝒪(n),0)-unitary encoding of Π^±_k P Π^±_k where P is the Markov transition matrix defined in Definition <ref>.  
    Suppose X satisfies the following promises: 
    
        
  * We can (classically or quantumly) approximately sample from the uniform distribution over the k-simplices of X within a total variation distance (TVD) δ for any δ∈Ω(1/poly(n)) in poly(n) time. 
        
  * The smallest non-zero eigenvalue λ of the k-th combinatorial Laplacian Δ_k of X satisfies λ∈Ω(1/poly(n)).
    
    Then, we can output an estimate for β_k/n_k within additive error ϵ in poly(n) time for any ϵ∈Ω(1/poly(n)) using 
    poly(n) number of harmonic quantum walk unitary U^h,  (U^h)^†, and other single-qubit and two-qubit gates, respectively. 




First, based on the assumption, sample from the uniform distribution over k-simplices within TVD error δ.
Then, we use the sample as the input to the quantum circuit and prepare ρ̃_k such that 

    ρ̃_k-ρ_k ≤δ,

where

    ρ_k1/n_k∑_σ∈ X^+_k|σ⟩⟨σ|.

Note that 

    ρ _k = 1/n_k∑_σ∈ X^+_k|σ⟩⟨σ| 
    = 1/n_k∑_i=1^n_k|ψ_i⟩⟨ψ_i|,

where {|ψ_i⟩} are the eigenvectors of the combinatorial Laplacian.

We can easily modify the unitary encoding U of Theorem <ref> (with error ϵ') into block-encoding using C_Π_kNOT with an additional ancilla qubit. 
Then we apply the block-measurement of Lemma <ref>. 
Let us denote the probability of outputting 1 by measuring the first qubit as p_1.
We have

    |p_1-β_k/n_k|
       ≤ρ̃_k-ρ_k  + Λ̃_Π - Λ_Π_♢
       = δ + O(ϵ').





Then, we estimate the probability p_1 by drawing N=ε^-2 samples from this quantum circuit. 
Let us denote the number of measurement outcomes 1 of the N samples as N_1. 
We output N_1/N as the estimate of the normalized Betti numbers. 
By the Chernoff-Hoeffding inequality, N_1/N is a correct estimate of p_1 within additive error ε with high probability. 
Therefore, we can estimate β_k/n_k within arbitrary additive error ϵ∈Ω(1/poly(n)) by taking small enough δ, ϵ',ε while keeping the algorithm efficient. 








 §.§ Estimating the normalized persistent Betti numbers



In this subsection, we show how to estimate the persistent Betti numbers using quantum walks. 
We show the following theorem: 



Given two unweighted graphs G_i=(V,E_i) and G_j=(V,E_j), where |V|=n and E_i ⊆ E_j, let X^i, X^j be clique complexes of the graph G_i and G_j.

Let U^down_i be a Π^±,i_k-projected 
(1,𝒪(n),0)-unitary encoding of Π_k^±,i P^down_i Π_k^±,i, where Π_k^±,i is the projector onto the space spanned by {|σ⟩}_σ∈ X^±,i_k. 

Similarly, let U^up_j be a Π^±,j_k-projected (1,𝒪(n),0)-unitary encoding of Π^±,j_k P^up_j Π^±,j_k where where Π_k^±,j is the projector onto the space spanned by {|σ⟩}_σ∈ X^±,j_k. 

Suppose X^i and X^j satisfy the following promises: 
    
        
  * We can (classically or quantumly) approximately sample from the uniform distribution over the k-simplices of X^i within a total variation distance (TVD) δ for any δ∈Ω(1/poly(n)) in poly(n) time. 
        
  * The smallest non-zero eigenvalue λ^i,down of the k-th down Laplacian Δ_k^i,down of X^i satisfies λ^i,down∈Ω(1/poly(n)).
        
  * The smallest non-zero eigenvalue λ^j,up of the k-th down Laplacian Δ_k^j,up of X^j satisfies λ^j,up∈Ω(1/poly(n)).
    
    Then, we can output an estimate for β^i,j_k/n_k within additive error ϵ in poly(n) time for any ϵ∈Ω(1/poly(n)) using 
    poly(n) number of U^i,down , (U^i,down)^†, U^j,up , (U^j,up)^† and other single-qubit and two-qubit gates, respectively. 



This result is inspired by the quantum algorithm of <cit.>. 
The quantum algorithm of <cit.> is based on the following fact: 

    β^i,j_k =  ( (∂_k^i))-  ( (∂_k^i) ∩Im(∂_k+1^j)).

It can be seen that 

    (∂_k^i)=((∂^i_k)^*∂_k^i)=(Δ_k^i,down)
    = Z_k^i,

and

    Im(∂_k+1^j)
    =
    Im(∂_k+1^j(∂_k+1^j)^*)
    =
    Im(Δ_k^j,up)
    =
    B_k^j
    .

Therefore, 

    β^i,j_k =  ( (Δ_k^i,down))-  ( (Δ_k^i,down) ∩ (Im(Δ_k^j,up)).

We can therefore estimate β^i,j_k/n_k with estimating 

    ( (Δ_k^i,down))/n_k  and   ( (Δ_k^i,down) ∩ (Im(Δ_k^j,up))/n_k

separately. 
The estimation of the first quantity can be achieved with the unitary encoding of 

    Proj( (Δ_k^i,down)),

and the estimation of the second quantity can be achieved with the unitary encoding of 

    Proj( (Δ_k^i,down) ∩ (Im(Δ_k^j,up)).
  

Estimation of ( (Δ_k^i,down))/n_k± 1/poly(n) can be done using the block-measurement of 

    Proj( (Δ_k^i,down))

using U^i,down as in the proof of Theorem <ref>. The estimation is efficient if 1/λ^i,down∈ poly(n).

Next, consider the Estimation of ( (Δ_k^i,down) ∩ ((Δ_k^j,up)^⊥)/n_k. 
The unitary encoding of 

    Proj( (Δ_k^i,down) ∩ ((Δ_k^j,up)^⊥)
  
can be implemented in the following steps. 
First, implement the unitary encoding of 

    Proj( (Δ_k^i,down))·Proj( (Δ_k^j,up)^⊥)

with taking the product of unitary encodings <cit.> of Proj( (Δ_k^i,down)) 
and Proj( Im(Δ_k^j,up)).
Then, following <cit.>, perform QSVT with the product unitary. 
Using the unitary encoding of

    Proj( (Δ_k^i,down) ∩ ((Δ_k^j,up)^⊥)

we can estimate ( (Δ_k^i,down) ∩ ((Δ_k^j,up)^⊥)/n_k in a similar way as in the proof of Theorem <ref>.
The estimation can be done efficiently if 1/λ^i,down∈ poly(n) and 1/λ^j,up∈ poly(n).






 §.§ Verification of the promise clique homology problem



In this section, we provide a verification algorithm for the following problem using quantum walks on simplicial complexes.

Fix functions k: ℕ→ℕ and g: ℕ→[0, ∞), with g(n) ≥ 1 / poly(n), k(n) ≤ n. The input to the problem is a vertex-weighted graph G on n vertices
where the weights of vertices are between 1/poly(n) to 1. 
We denote the clique complex of G by X. 




The task is to decide whether:

    
  * YES: the k(n)-th homology group of X is non-trivial. 
    
  * NO: the k(n)-th homology group of X is trivial.

given a promise that in NO cases, the combinatorial Laplacian Δ^k has minimum eigenvalue λ_min(Δ^k) ≥ g(n).




Verification of QMA problems has been important in quantum computational complexity. 
For example, a protocol for a certain QMA-type problem has led to a novel interactive protocol for the verification of quantum computing which is done by untrusted quantum computing devices <cit.>. 
Motivated by potentially providing a new protocol for the verification of quantum computing based on quantum walks, we consider the task of the homology problem in a prover and verifier setting. 

We provide a QMA-verification algorithm based on the harmonic quantum walk on simplicial complexes.
We provide a verification algorithm for the promise clique problem as follows: 


    
  * The prover sends an n-qubit state |w⟩ to the verifier (which is supposed to in (Δ_k) in the YES case). 
    
  * The verifier performs the block-measurement of Lemma <ref> with respect to the projected unitary encoding of the projector onto (Δ_k) of Theorem <ref> based on the harmonic quantum walk. 
    
  * Finally, if the measurement outcome is 1,  the verifier outputs YES; otherwise, outputs NO.


In order to perform the block-measurement, we need to know the spectral gap of the combinatorial Laplacian. However, we do not know the spectral gap in the YES case. Instead, we perform the block-measurement that corresponds to the spectral gap of  g(n)/2. 




    The above algorithm can efficiently verify the promise clique homology problem with completeness and soundness. 






From 

Theorem <ref>, 
the approximated kernel projector Π̃_ker satisfies 

    |Π̃_ℋ_k-Proj(ℋ_k)| ≤ϵ.

According to Lemma <ref>, we can construct a quantum channel Λ̃_Π which is approximated equal to a channel Λ_Π that maps as 
    
    |0⟩⊗|ψ⟩→|1⟩⊗Π_ℋ_k|ψ⟩ + |0⟩⊗ (I-Π_ℋ_k) |ψ⟩,

such that Λ_Π - Λ̃_Π_♢∈𝒪(ϵ).
What we can actually implement is a projector that is close to the projector to the space spanned by eigenstates of Δ_k with energy below g(n)/2.

Therefore, in the NO case, the probability of outputting 0 with block-measurement is smaller than 𝒪(ϵ) for arbitrary states provided by the prover because there are no eigenstates of Δ_k with energy less than g(n) and the gap between  g(n)/2 and g(n) is inverse-polynomially large. 
Similarly, in the YES case, the probability of outputting 1 with block-measurement for the provided state |w⟩∈(Δ_k) by an honest prover is larger than 1-𝒪(ϵ). 

We can take small enough ϵ∈𝒪(1/exp(n)) while keeping the procedure efficient. This concludes the proof of the theorem. 





























































































§ ACKNOWLEDGEMENT

RH was supported by JSPS KAKENHI Grant Number JP22J11727 and PRESTO Grant Number JPMJPR23F9, Japan.

alpha







§ OVERVIEW OF THE CLASSICAL RANDOM WALKS ON SIMPLICIAL COMPLEXES



In this section, we give an overview for the definitions of up and down random walks of <cit.> <cit.>. 
The results related to these walks are summarized in Table <ref>. 
Note that we use the notations we introduce in Section <ref>, that are sometimes slightly different from the notations of <cit.> <cit.>.

The Markov transition matrix of the up random walk of <cit.> is defined as 

    P_σ,σ'=
    
        p    σ'=σ
    1-p/(k+1) deg(σ)   σ'∼_↑σ
    
        0     otherwise.

Here, p is the parameter of laziness. 
Note that σ transits to σ' s.t. σ∼_↑ in this definition while we transit to σ' s.t. σ∼_↑ in our definition (Definition <ref>).

















The Markov transition matrix of the down walk of <cit.> is defined using an absorbing state Θ as

    P_σ,σ'=
    
        p    σ≠Θ and σ'=σ
    1-p/(M-1)(k+1)   σ≠Θ and σ'∼_↓σ
    1-p/(M-1)(k+1)   σ≠Θ and σ'∼_↓σ
    β   σ≠Θ and σ'=Θ
    
        1    σ=σ'=Θ
    
        0     otherwise,

where Mmax_σ X^k-1deg(σ) is the maximal (k-1)-degree. 
This definition is also different from our definition (Definition <ref>).

Let p^σ_0_t(σ) be a probability of being in σ after t-steps of random walks starting from σ_0. 
Then, the expectation process is defined as 

    ℰ^σ_0_t 
    p^σ_0_t(σ) - p^σ_0_t(σ)

and the normalized expectation process is defines through normalization to this process. 


















