We investigate generalizations of the graph theoretic notions of effective resistance and capacitance to simplicial complexes and prove analogs of formulas known in the case of graphs. In graphs the effective resistance between two vertices is O(n); however, we show that in a simplicial complex the effective resistance of a null-homologous cycle may be exponential. This is caused by relative torsion in the simplicial complex. We provide upper bounds on both effective resistance and capacitance that are polynomial in the number of simplices as well as the maximum cardinality of the torsion subgroup of a relative homology group denoted 𝒯_{max}(𝒦). We generalize the quantum algorithm deciding st-connectivity in a graph and obtain an algorithm deciding whether or not a (d-1)-dimensional cycle γ is null-homologous in a d-dimensional simplicial complex 𝒦. The quantum algorithm has query complexity parameterized by the effective resistance and capacitance of γ. Using our upper bounds we find that the query complexity is O (n^{5/2}⋅ d^{1/2} ⋅ 𝒯_{max}(𝒦)²). Under the assumptions that γ is the boundary of a d-simplex (which may or may not be included in the complex) and that 𝒦 is relative torsion-free, we match the O(n^{3/2}) query complexity obtained for st-connectivity. These assumptions always hold in the case of st-connectivity. We provide an implementation of the algorithm whose running time is polynomial in the size of the complex and the relative torsion. Finally, we prove a duality theorem relating effective resistance and capacitance when 𝒦 is d-dimensional and admits an embedding into ℝ^{d+1}.
We investigate generalizations of the graph theoretic notions of effective resistance and capacitance to simplicial complexes and prove analogs of formulas known in the case of graphs. In graphs the effective resistance between two vertices is O(n); however, we show that in a simplicial complex the effective resistance of a null-homologous cycle may be exponential. This is caused by relative torsion in the simplicial complex. We provide upper bounds on both effective resistance and capacitance that are polynomial in the number of simplices as well as the maximum cardinality of the torsion subgroup of a relative homology group denoted 𝒯_{max}(𝒦). We generalize the quantum algorithm deciding st-connectivity in a graph and obtain an algorithm deciding whether or not a (d-1)-dimensional cycle γ is null-homologous in a d-dimensional simplicial complex 𝒦. The quantum algorithm has query complexity parameterized by the effective resistance and capacitance of γ. Using our upper bounds we find that the query complexity is O (n^{5/2}⋅ d^{1/2} ⋅ 𝒯_{max}(𝒦)²). Under the assumptions that γ is the boundary of a d-simplex (which may or may not be included in the complex) and that 𝒦 is relative torsion-free, we match the O(n^{3/2}) query complexity obtained for st-connectivity. These assumptions always hold in the case of st-connectivity. We provide an implementation of the algorithm whose running time is polynomial in the size of the complex and the relative torsion. Finally, we prove a duality theorem relating effective resistance and capacitance when 𝒦 is d-dimensional and admits an embedding into ℝ^{d+1}.
We introduce a new quantum algorithm for computing the Betti numbers of a simplicial complex. In contrast to previous quantum algorithms that work by estimating the eigenvalues of the combinatorial Laplacian, our algorithm is an instance of the generic Incremental Algorithm for computing Betti numbers that incrementally adds simplices to the simplicial complex and tests whether or not they create a cycle. In contrast to existing quantum algorithms for computing Betti numbers that work best when the complex has close to the maximal number of simplices, our algorithm works best for sparse complexes. To test whether a simplex creates a cycle, we introduce a quantum span-program algorithm. We show that the query complexity of our span program is parameterized by quantities called the effective resistance and effective capacitance of the boundary of the simplex. Unfortunately, we also prove upper and lower bounds on the effective resistance and capacitance, showing both quantities can be exponentially large with respect to the size of the complex, implying that our algorithm would have to run for exponential time to exactly compute Betti numbers. However, as a corollary to these bounds, we show that the spectral gap of the combinatorial Laplacian can be exponentially small. As the runtime of all previous quantum algorithms for computing Betti numbers are parameterized by the inverse of the spectral gap, our bounds show that all quantum algorithms for computing Betti numbers must run for exponentially long to exactly compute Betti numbers. Finally, we prove some novel formulas for effective resistance and effective capacitance to give intuition for these quantities.
An important family of span programs, st-connectivity span programs, have been used to design quantum algorithms in various contexts, including a number of graph problems and formula evaluation problems. The complexity of the resulting algorithms depends on the largest positive witness size of any 1-input, and the largest negative witness size of any 0-input. Belovs and Reichardt first showed that the positive witness size is exactly characterized by the effective resistance of the input graph, but only rough upper bounds were known previously on the negative witness size. We show that the negative witness size in an st-connectivity span program is exactly characterized by the capacitance of the input graph. This gives a tight analysis for algorithms based on st-connectivity span programs on any set of inputs. We use this analysis to give a new quantum algorithm for estimating the capacitance of a graph. We also describe a new quantum algorithm for deciding if a graph is connected, which improves the previous best quantum algorithm for this problem if we're promised that either the graph has at least kappa>1 components, or the graph is connected and has small average resistance, which is upper bounded by the diameter. We also give an alternative algorithm for deciding if a graph is connected that can be better than our first algorithm when the maximum degree is small. Finally, using ideas from our second connectivity algorithm, we give an algorithm for estimating the algebraic connectivity of a graph, the second largest eigenvalue of the Laplacian.
Gapped Clique Homology on Weighted Graphs Is QMA1-Hard and Contained in QMA
Abstract. We study the complexity of a classic problem in computational topology, the homology problem: given a description of some space [Formula: see text] and an integer [Formula: see text], decide if [Formula: see text] contains a [Formula: see text]-dimensional hole. The setting and statement of the homology problem are completely classical, yet we find that the complexity is characterized by quantum complexity classes. Our result can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics established by Witten (1982). We consider clique complexes, motivated by the practical application of topological data analysis (TDA). The clique complex of a graph is the simplicial complex formed by declaring every [Formula: see text]-clique in the graph to be a [Formula: see text]-simplex. Our main result is that deciding whether the clique complex of a weighted graph has a hole or not, given a suitable promise on the gap, is [Formula: see text]-hard and contained in QMA. Our main innovation is a technique to lower bound the eigenvalues of the combinatorial Laplacian operator. For this, we invoke a tool from algebraic topology known as spectral sequences. In particular, we exploit a connection between spectral sequences and Hodge theory outlined by Forman (1994). Spectral sequences will play a role analogous to perturbation theory for combinatorial Laplacians. In addition, we develop the simplicial surgery technique used in prior work by Crichigno and Kohler (2022). Our result provides some suggestion that the quantum TDA algorithm due to Lloyd, Garnerone, and Zanardi (2016) cannot be dequantized, although proving this would require studying the complexity of a different problem related to the combinatorial Laplacian of clique complexes.
The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph H is present in an input graph G, has been the subject of considerable study. However, even for relatively simple subgraphs, such as paths and cycles, a complete understanding of their query complexities remains elusive. In this work, we consider several variants of path- and cycle-containment problems in the adjacency matrix model, where we search for paths or cycles of constant length k. We compare the settings where the graphs are directed or undirected, where the goal is to detect or find the existence of a path/cycle, and where the path/cycle we are looking for has length exactly k, or at most k. We also consider several promise versions of these problems, where we suppose that the input graph has a certain structure. We characterize the relative difficulty of these variants of the path/cycle-containment problems, by relating them to one another using randomized reductions, and grouping them into equivalence classes.
When we restrict our attention to path-containment problems, we get a dichotomy result. Some of the path-containment problems can be solved using a linear number of queries, and all the others are equivalent to one another (and additionally to several cycle-containment problems) under randomized reductions, up to constant overhead. For the latter equivalence class, we prove a novel quantum-walk-based algorithm that achieves query complexity O(n3/2−αk), where αk∈Θ(c−k) and c=3+17/2≈1.33, beating the previous best upper bound O(n3/2) on its query complexity. We also provide a conditional lower bound based on the graph-collision problem, which implies that this equivalence class does not admit linear-query quantum algorithms unless graph collision admits an O(n) query algorithm.
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 object reflecting the topology of the simplicial complex. We construct a unitary encoding projecting onto the kernel of the Laplacian, representing the harmonic cycles in the complex's homology. Our efficient construction of quantum walk unitaries for clique complexes paves the way for exploring higher-order interactions within topological structures. Our construction requires O ( n 3 log ( 1 / ϵ ) / λ k ) gates, where n is the number of vertices, λ k is the smallest non-zero eigenvalue of the Laplacian, and ϵ is the projection error. Our results indicate apparent superpolynomial quantum speedup with quantum walks, without quantum oracles, provided the spectral gap of the Laplacian is inverse-polynomially bounded and efficient simplex sampling is available.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 is our major technical contribution. We also extend the framework by constructing variant quantum walks that enable us to: (1) estimate normalized persistent Betti numbers throughout a deformation process, (2) verify a specific QMA 1 -hard problem related to clique complex homology, showcasing potential applications in computational complexity theory, and (3) solve the high-dimensional discrete Dirichlet problem (HDDP), generalizing the classical discrete Dirichlet problem on graphs to simplicial complexes, with an apparent superpolynomial speedup over the best known classical algorithm.
We give a new upper bound on the quantum query complexity of deciding s t -connectivity on certain classes of planar graphs, and show the bound is sometimes exponentially better than previous results. We then show Boolean formula evaluation reduces to deciding connectivity on just such a class of graphs. Applying the algorithm for s t -connectivity to Boolean formula evaluation problems, we match the O ( N ) bound on the quantum query complexity of evaluating formulas on N variables, give a quadratic speed-up over the classical query complexity of a certain class of promise Boolean formulas, and show this approach can yield superpolynomial quantum/classical separations. These results indicate that this s t -connectivity-based approach may be the "right" way of looking at quantum algorithms for formula evaluation.