# An Incremental Span-Program-Based Algorithm and the Fine Print of Quantum
Topological Data Analysis111A preliminary version of this paper appeared at
ISAAC 2021 under the title “Effective Resistance and Capacitance in Simplicial
Complexes and a Quantum Algorithm.”

Mitchell Black Oregon State University<EMAIL_ADDRESS>William
Maxwell Oregon State University Amir Nayyeri Oregon State University:
<EMAIL_ADDRESS>
###### Abstract

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.

##  1 Introduction.

The past few years has seen the development of quantum algorithms with the
potential to speed up computation of topological features of simplicial
complexes called Betti numbers. Betti numbers are important topological
invariants of a space; indeed, there is an entire, rapidly-growing field
called Topological Data Analysis (TDA) that studies the application of
topological invariants like Betti numbers (among other)
[carlsson2021topological, dey2022computational, EdelsbrunnerHarer].
Accordingly, the study of quantum algorithms for computing Betti numbers has
been deemed Quantum Topological Data Analysis (QTDA).

Betti numbers can be both time and space inefficient for classical computers
to compute. For example, a simplicial complex on vertices can be exponentially
large and it can take exponential time to compute Betti numbers in arbitrary
dimensions. Quantum computers offer a potential solution to the shortcomings
of the classical algorithm. For example, quantum computers can efficiently
store a simplicial complex with $n$ vertices using only
$O(\operatorname{poly}(n))$ qubits.

However, while these quantum algorithms have certain advantages over their
classical counterparts like improved space complexity, QTDA algorithms only
achieve significant advantage over classical TDA algorithms under certain
circumstances. QTDA algorithms only achieve significant speed up over
classical algorithms when the input complex is clique-dense—it has close to
the maximal number of simplices—and when the spectral gap of the combinatorial
Laplacian of the complex is polynomially small. This second point is a
particular problem as, before now, it was unknown how small the spectral gap
of the combinatorial Laplacian could be. This makes the spectral gap of the
combinatorial Laplacian an example of “fine print” [Aaronson2015fineprint]: an
unbounded parameter in the runtime of a celebrated quantum algorithm.

###  1.1 Our Contributions.

  * •

In Sections 3 and 4, we provide a novel quantum algorithm for computing Betti
numbers using the framework of span programs [Karchmer, Reichardt2012]. As
opposed to existing QTDA algorithms that work by estimating the eigenvalues of
the combinatorial Laplacian or singular values of the boundary matrices, our
algorithm is more similar to classical matrix-reduction algorithms for
computing Betti numbers as it works by incrementally adding simplices to the
simplicial complex and testing if these simplices create or destroy a cycle.
One advantage of our algorithm is that it avoids the step of creating a
superpostion over the $k$-simplices, which is a bottleneck of existing QTDA
algorithms that restricts their utility to the clique-dense regime. In Section
4.3 and Section 4.4, we show that the query and time complexity of our span
program algorithm for QTDA is parameterized by the maximum effective
resistance and capacitance of cycles in $\mathcal{K}$. In Section 4.6, we
compare our algorithm with existing QTDA algorithms. The culmination of this
section is the following theorem.

######  Theorem 1.1.

Let $\mathcal{K}$ be a simplicial complex. There is a quantum algorithm for
computing the $d$th Betti number $\beta_{d}$ of $\mathcal{K}$ in time

$\tilde{O}\left(\left(\sqrt{\frac{\mathcal{R}_{\max}\mathcal{C}_{\max}}{\tilde{\lambda}_{\min}}}n_{0}+\sqrt{\mathcal{R}_{\max}n_{0}}\right)(n_{d}+n_{d+1})\right),$

where

    * $\bullet$

$n_{i}$ is the number of $i$-simplices of $\mathcal{K}$.

    * $\bullet$

$\mathcal{R}_{\max}$ is the maximum finite effective resistance
$\mathcal{R}_{\partial\sigma}(\mathcal{L})$ of the boundary of any $d$\- or
$(d+1)$-simplex $\sigma\in\mathcal{K}$ in any subcomplex
$\mathcal{L}\subset\mathcal{K}$.

    * $\bullet$

$\mathcal{C}_{\max}$ are the maximum finite effective capacitance
$\mathcal{C}_{\partial\sigma}(\mathcal{L},\mathcal{K})$ of the boundary of any
$d$\- or $(d+1)$-simplex $\sigma\in\mathcal{K}$ in any subcomplex
$\mathcal{L}\subset\mathcal{K}$.

    * $\bullet$

$\tilde{\lambda}_{\min}$ is the minimum spectral gap of the normalized up
Laplacians $\tilde{L}_{d-1}^{up}[\mathcal{K}]$ and
$\tilde{L}_{d}^{up}[\mathcal{K}]$.

  * •

In Section 5, we provide upper bounds on the maximum effective resistance by
the size of the simplicial complex and the maximal rank of the torsion
subgroup of the simplicial complex, as well as looser upper bounds purely in
terms of the size of the complex. These upper bounds show that the effective
resistance can be at most exponentially-large with respect to the size of the
complex. We also provide similar upper bounds on effective capacitance for
special cases. Finally, we provide families of simplicial complexes with
cycles whose effective resistance or effective capacitance is exponentially
large, thus matching the upper bound up to the base of the exponent. This
implies that our algorithm for QTDA can take exponentially long in the worst
case. However, in the next paragraph, we will see that our results imply all
other QTDA algorithms must run for exponential time as well.

  * •

In Section 6, we show how the upper and lowers bounds for effective resistance
provide lower and upper bounds for the spectral gap of the combinatorial
Laplacian respectively; thus, the spectral gap is exponentially small in the
worst case. Moreover, we show there are clique-dense complexes that achieve
worst-case spectral gap.

######  Theorem 1.2.

Let $K$ be a simplicial complex. Let $n_{i}$ be the number of $i$-simplices of
$K$. Let $n=\max\\{\min\\{n_{d-1},n_{d}\\},\min\\{n_{d},n_{d+1}\\}\\}$. Then
the spectral gap
$\lambda_{\min}(L_{d}[K])\in\Omega\left(\frac{1}{n^{2}d^{n}}\right)$.

######  Theorem 1.3.

Let $d,n\geq 1$. There are constants $c_{d},\kappa_{d}$ that depends only on
$d$ and a $d$-dimensional simplicial complex $\mathcal{C}_{d}^{n}$ with
$n_{d}=\Omega(\kappa_{d}\binom{n_{0}}{d})$ $d$-simplices such that the
spectral gaps $\lambda_{\min}(L_{d-1}[\mathcal{C}_{d}^{n}])$,
$\lambda_{\min}(L_{d}[\mathcal{C}_{d}^{n}])\in O(\frac{1}{c_{d}^{n_{d}}})$.

This answers one of the most important question in QTDA: how small can the
spectral gap be? As all existing QTDA algorithms are parameterized by the
inverse of the spectral gap of the combinatorial Laplacian
$\frac{1}{\lambda_{\min}}$, this implies that all existing QTDA algorithms
need exponential time to exactly estimate Betti numbers.222This exponential
time complexity is not a result of the quantum nature of these algorithms.
Some classical algorithms for computing Betti numbers are also parameterized
by the inverse of the spectral gap, so these algorithms would need to run for
exponential time as well [apers2022simple,
Friedman1998BettiNumbers].Additionally, the space complexity of some QTDA
algorithms is parameterized by $\log(\frac{1}{\lambda_{\min}})$, so these
algorithms will need space proportional to the number of $(d-1)-$, $d-$, or
$(d+1)$-simplices, rather than space proportional to the number of vertices.

  * •

We also prove some interesting formulas for effective resistance and
capacitance that give intuition for these quantities. In Appendix B, we
provide series and parallel formulas for effective resistance akin to the
formulas for effective resistance in graphs. We also show that effective
resistance satisfies a Rayeligh monotonicity property akin to effective
resistance in graphs. Finally, in Appendix C, we show that effective
resistance is dual to effective capacitance for embedded simplicial complexes.

###  1.2 Related Work

.

##### History of QTDA.

Lloyd, Garnerone, and Zanardi (LGZ) introduced the first quantum algorithm for
computing Betti numbers up to a multiplicative error [Lloyd2016lgz]. Their
algorithm works by estimating the eigenvalues of the combinatorial Laplacian,
which is inspired by Friedman’s classical algorithm for computing Betti
numbers [Friedman1998BettiNumbers]. The LGZ algorithm has the advantage that
its runtime is only polynomial with respect to the number of vertices, as
opposed to the number of simplices like the matrix reduction algorithm. The
trade-off is that this algorithm gains a dependence on the inverse of the
spectral gap and the ratio of the number of simplices to the number of
possible simplices. The LGZ algorithm performs best in the regime where the
spectral gap of the combinatorial Laplacian is polynomially lower-bounded and
the simplicial complex is clique-dense, meaning it has close to the maximal
number of simplices. Subsequent works have improved the LGZ algorithm in
different ways but maintain a runtime dependence on the inverse of the
spectral gap and the clique density [gunn2019, mccardle2023streamlined,
ubaru2021].

Another line of QTDA research has been developing algorithms for persistent
Betti numbers. While the LGZ algorithm was initially claimed to be able to
compute persistent Betti numbers, this was later disproved by Meijer
[Meijer2019] and Neumann and den Breeijen [Neumann2019]. Hayakawa was the
first to develop a quantum algorithm for computing persistent Betti numbers
[Hayakawa2022quantumalgorithm]. McArdle, Gilyén, and Berta have also developed
algorithms for computing persistent Betti numbers [mccardle2023streamlined].

##### Hardness of Computing Betti Numbers.

In addition to new algorithms for computing Betti numbers, there have also
been a number of works arguing computing Betti numbers is hard in general.
Adamaszek and Stacho [adamaszek2016complexity] show that determining if a
simplicial complex has non-zero Betti number is NP-Hard when parameterized
either by the number of vertices and the number of maximal simplices, or the
number of vertices and number of minimal non-faces. Additionally, they show
the problem is NP-Hard for clique complexes when parameterized by the number
of vertices. Schmidhuber and Lloyd [alex2022complexitytheoretic] show that
computing Betti numbers of a clique complex is #P-Hard and estimating the
Betti number up to a multiplicative constant is NP-Hard when parameterized by
the number of vertices. Moreover, the hardness results of Schmidhuber and
Lloyd hold for clique-dense clique complexes. This is an important restriction
as the runtime of LGZ and and other QTDA algorithms are lowest for clique-
dense complexes. Here, the assumptions on the input are vital. Computing Betti
numbers is in $P$ when parameterized by the number of all simplices in the
complex. This does not contradict $P\neq NP$ though, as the number of
simplices can be exponentially large with respect to the number of vertices.

There have also been a number of works showing that problems related to
computing Betti numbers are hard for the quantum computing complexity class
DCQ-1. Crichigno and Kohler [crichigno2022clique] showed that determining if
the Betti number of a clique complex is nonzero is QMA1-Hard when
parameterized by the number of vertices, and computing the Betti number of a
clique complex is #BQP-Hard. Gyurik, Cade, and Dunjko [gyurik2022advantage]
show that a generalization of Betti number estimation called low-lying
spectral density estimation (LLSD) is DCQ1-Complete, suggesting that LLSD may
be classically intractable. Cade and Crichigno [cade2021complexity] showed
that estimating Betti numbers for general chain complexes (not just those
arising from simplicial complexes) is also DCQ1-complete.

##### Lower Bounds on the Spectral Gap of the Combinatorial Laplacian.

All existing QTDA algorithms are parameterized by the inverse of the spectral
gap of the combinatorial Laplacian. While we show the spectral gap can be
exponentially small, there have also been a number of exact or expected lower
bounds on the spectral gap of the combinatorial Laplacian for certain families
of simplicial complexes [beit2020spectral, Friedman1998BettiNumbers,
gundert2016eigenvalues, lew2020spectralb, lew2020spectral, lew2023garland,
STEENBERGEN201456, yamada2019spectrum]. However, these bounds place non-
trivial assumptions on the simplicial complex so should not be taken to
represent general simplicial complexes.

##  2 Preliminaries.

##### Algebraic Topology.

A simplicial complex $\mathcal{K}$ on a set of vertices $V$ is a subset of the
power set $\mathcal{K}\subseteq P(V)$ with the property that if
$\sigma\in\mathcal{K}$ and $\tau\subset\sigma$ then $\tau\in\mathcal{K}$. An
element of $\mathcal{K}$ is a simplex. A simplex $\sigma\in\mathcal{K}$ of
size $|\sigma|=d+1$ is a d-simplex. The set of all $d$-simplices of
$\mathcal{K}$ is denoted $\mathcal{K}_{d}$, and the number of $d$-simplices is
denoted $n_{d}=|\mathcal{K}_{d}|$. The d-skeleton of $\mathcal{K}$, denoted
$\mathcal{K}^{d}$, is the simplicial complex of all simplices of $\mathcal{K}$
of dimension at most $d$, i.e.
$\mathcal{K}^{d}=\cup_{i=0}^{d}\mathcal{K}_{i}$. The dimension of
$\mathcal{K}$ is the largest $d$ such that $\mathcal{K}$ contains a
$d$-simplex; a 1-dimensional simplicial complex is a graph.

The dth chain group $C_{d}(\mathcal{K})$ is the vector space over $\mathbb{R}$
with orthonormal basis $\mathcal{K}_{d}$. An element of $C_{d}(\mathcal{K})$
is a d-chain. Unless otherwise stated, all vectors and matrices will be in the
basis $\mathcal{K}_{d}$. For a chain $f\in C_{d}(\mathcal{K})$, we denote its
$\sigma$ coordinate $f(\sigma)$. Finally, the support of a chain $f$ is the
set of simplices given a non-zero value by $f$ and is denoted
$\operatorname{supp}(f)=\\{\sigma_{i}\in\mathcal{K}_{d}\colon
f(\sigma_{i})\neq 0\\}$.

We assume there is a fixed but arbitrary order on the vertices
$V=(v_{1},\dots,v_{n})$. Let $\sigma=\\{v_{i_{0}},\ldots,v_{i_{d}}\\}$ be a
$d$-simplex in $\mathcal{K}$ with $v_{i_{j}}\leq v_{i_{k}}$ whenever $j\leq
k$. The boundary of $\sigma$ is the $(d-1)$-chain
$\partial\sigma=\sum_{j=0}^{d}(-1)^{j}\cdot(\sigma\setminus\\{v_{i_{j}}\\})$.
The dth boundary map is the linear map $\partial_{d}:C_{d}(\mathcal{K})\to
C_{d-1}(\mathcal{K})$ defined
$\partial_{d}f=\sum_{\sigma\in\mathcal{K}_{d}}f(\sigma)\partial\sigma$ where
$f(\sigma)$ denotes the component of $f$ indexed by the simplex $\sigma$. An
element in $\ker\partial_{d}$ is a cycle, and an element in
$\operatorname{im}\partial_{d}$ is a boundary or a null-homologous cycle. See
Figure 1. The boundary maps have the property that
$\partial_{d}\circ\partial_{d+1}=0$, so
$\operatorname{im}\partial_{d+1}\subset\ker\partial_{d}$. The dth homology
group is the quotient group
$H_{d}(\mathcal{K})=\ker(\partial_{d})/\operatorname{im}(\partial_{d+1})$. The
dth Betti number $\beta_{d}$ is the dimension of $H_{d}(\mathcal{K})$. The dth
coboundary map is the map
$\delta_{d}:=\partial_{d+1}^{T}:C_{d}(\mathcal{K})\to C_{d+1}(\mathcal{K})$.
An element of $\ker\delta_{d}$ is a cocycle, and an element in
$\operatorname{im}\delta_{d-1}$ is a coboundary. We will use the notation
$\partial[\mathcal{K}]$ and $\delta[\mathcal{K}]$ when we want to specify the
complex associated with the (co)boundary operator.

While our algorithms calculate homology with real coefficients, for some of
our topological results, we will need to consider homology with integer
coefficients. The integral chain group $C_{d}(\mathcal{K},\mathbb{Z})$ is the
free abelian group generated by the set of $d$-simplices $\mathcal{K}_{d}$
whose elements are formal sums
$\sum_{\sigma_{i}\in\mathcal{K}_{d}}\alpha_{i}\sigma_{i}$ with coefficients
$\alpha_{i}\in\mathbb{Z}$. The integer homology groups are constructed in the
same way as the real homology groups. We define boundary maps
$\partial_{d}:C_{d}(\mathcal{K};\mathbb{Z})\to
C_{d-1}(\mathcal{K};\mathbb{Z})$ the same way as for the real chain groups,
except now the boundary maps are group homomorphisms rather than linear maps.
The integral homology groups are the quotient groups
$H_{d}(\mathcal{K};\mathbb{Z})=\ker\partial_{d}/\operatorname{im}\partial_{d+1}$.

##### Laplacians.

The dth up Laplacian is $L^{up}_{d}=\partial_{d+1}\delta_{d}$, the dth down
Laplacian is $L^{down}_{d}=\delta_{d-1}\partial_{d}$, and the dth
(combinatorial) Laplacian is $L_{d}=L_{d}^{up}+L_{d}^{down}$. The Laplacians
define the following orthogonal decomposition of the $d$th chain group
$C_{d}(\mathcal{K})$ called the Hodge Decomposition.

$\displaystyle C_{d}(\mathcal{K})$
$\displaystyle=\operatorname{im}L_{d}^{up}\oplus\operatorname{im}L_{d}^{down}\oplus\ker
L_{d}$
$\displaystyle=\operatorname{im}\partial_{d}\oplus\operatorname{im}\delta_{d-1}\oplus\ker
L_{d}$

where the second equality follows from the fact that
$\operatorname{im}AA^{T}=\operatorname{im}A$ for any matrix $A$. We call the
subspaces $\operatorname{im}\partial_{d}$, $\operatorname{im}\delta_{d-1}$,
and $\ker L_{d}$ the boundary, coboundary, and harmonic spaces. Arguably the
fundamental theorem of the combinatorial Laplacian is the Hodge Theorem.

######  Theorem 2.1 (Hodge Theorem, Eckmann [Eckmann1944]).

The $d$th harmonic space is isomorphic to the $d$th homology group, i.e. $\ker
L_{d}\cong H_{d}(\mathcal{K})$.

Therefore, the $d$th Betti number can equivalently be computed by computing
the rank of $L_{d}$, a fact used by many existing QTDA algorithms.

The following lemma gives several properties of the spectrum of the
combinatorial Laplacian.

######  Lemma 2.2.

Let $\operatorname{spec}_{NZ}(A)$ denote the multiset of the non-zero
eigenvalues of a linear operator $A$. Let $\mathcal{K}$ be a simplicial
complex. Let $d>0$ be a positive integer. Then

  1. 1.

(Goldberg [Goldberg2002, Lemma 4.1.8])
$\operatorname{spec}_{NZ}(L^{up}_{d})=\operatorname{spec}_{NZ}(L^{down}_{d+1})$

  2. 2.

(Goldberg [Goldberg2002, Lemma 4.1.7])
$\operatorname{spec}_{NZ}(L_{d})=\operatorname{spec}_{NZ}(L^{up}_{d})\cup\operatorname{spec}_{NZ}(L^{down}_{d})$

  3. 3.

(Goldberg [Goldberg2002, Lemma 4.2.3]) If $\mathcal{K}$ has connected
components $\mathcal{K}_{1},\ldots,\mathcal{K}_{m}$, then

$\operatorname{spec}_{NZ}(L_{d}[\mathcal{K}])=\operatorname{spec}_{NZ}(L_{d}[\mathcal{K}_{1}])\cup\cdots\cup\operatorname{spec}_{NZ}(L_{d}[\mathcal{K}_{m}])$

where all unions are multiset unions.

The up, down, and combinatorial Laplacian are all positive-semidefinite,
meaning their eigenvalues are all non-negative [Goldberg2002]. The spectral
gap $\lambda_{\min}(L_{d})$ is the smallest non-zero eigenvalue of the
combinatorial Laplacian. Lemma 2.2 Part 2 implies the following theorem about
the spectral gap of the combinatorial Laplacian.

######  Corollary 2.3.

Let $\mathcal{K}$ be a simplicial complex. Let $d$ be a positive integer. Then

$\lambda_{\min}(L_{d}[\mathcal{K}])=\min\\{\lambda_{\min}(L^{down}_{d}[\mathcal{K}]),\,\lambda_{\min}(L^{up}_{d}[\mathcal{K}])\\}$

In Section 6, we discuss upper and lower bounds on the spectral gap. There are
also known upper and lower bounds on the largest eigenvalue of the
combinatorial Laplacian.

######  Theorem 2.4.

Let $\mathcal{K}$ be a simplicial complex with $n_{0}$ vertices. Let $d$ be a
natural number. Then the maximal eigenvalue of the combinatorial Laplacian
$\lambda_{\max}(L_{d})\leq n_{0}$.

###### Proof.

Let $\Delta_{n_{0}}$ be the complete complex on $n_{0}$ vertices. The maximum
eigenvalue of the $d$th up Laplacian is
$\lambda_{\max}(L_{d}^{up}[\Delta_{n_{0}}])=n_{0}$ for any dimension $d$
[GundertThesis2013, Lemma 2.6]. Moreover, by the interlacing theorem of
eigenvalues of the up Laplacian,
$\lambda_{\max}(L_{d}^{up}[\mathcal{K}])\leq\lambda_{\max}(L_{d}^{up}[\Delta_{n_{0}}])$
for any subcomplex $\mathcal{K}\subset\Delta_{n_{0}}$ [horak2013interlacing,
Theorem 1.1]. The theorem follows as
$\lambda_{\max}(L_{d}[\mathcal{K}])=\max\\{\lambda_{\max}(L_{d}^{up}[\mathcal{K}]),$
$\lambda_{\max}(L_{d-1}^{up}[\mathcal{K}])\\}\leq n_{0}$ ∎

We also consider two variants of the Laplacian variants of the up-Laplacian:
the weighted up Laplacian and the normalized up Laplacian. Let
$w:\mathcal{K}_{d+1}\to\mathbb{R}^{+}$ be a weight function on the
$(d{+}1)$-simplices. Let $W:C_{d+1}(\mathcal{K})\to C_{d+1}(\mathcal{K})$ be
the diagonal matrix with $W_{\tau,\tau}=w(\tau)$. The dth weighted up
Laplacian is $L^{up,\,W}_{d}=\partial_{d+1}W\delta_{d}$. The degree of a
$d$-simplex $\sigma$ is
$\deg(\sigma)=\sum_{\tau\in\mathcal{K}_{d+1}\colon\sigma\subset\tau}w(\tau)$.
Let $D:C_{d}(\mathcal{K})\to C_{d}(\mathcal{K})$ be the diagonal matrix with
$D_{\sigma,\sigma}=\deg(\sigma)$. The dth normalized up Laplacian is
$\tilde{L}^{up}_{d}=D^{-1/2}\partial_{d+1}W\delta_{d}D^{-1/2}$. The following
theorem relates the spectral gap of the normalized and unnormalized
Laplacians. A proof can be found in Appendix A

######  Lemma 2.5.

Let $\mathcal{K}$ be a simplicial complex. Let $d_{\min}$ and $d_{\max}$ be
the minimum and maximum degrees of any $d$-simplex in $\mathcal{K}$. Suppose
that $d_{\min}>0$. The normalized and unnormalized spectral gap are related as
follows:

$\frac{1}{d_{\max}}\lambda_{\min}(L_{d}^{up})\leq\lambda_{\min}(\tilde{L}_{d}^{up})\leq\frac{1}{d_{\min}}\lambda_{\min}(L_{d}^{up})$

##### Pseudoinverse of a Linear Map.

Let $A:\mathbb{R}^{n}\to\mathbb{R}^{m}$ be a rank $k$ linear operator with
singular value decomposition $A=\sum_{i=1}^{k}\sigma_{i}u_{i}v_{i}^{T}$. The
pseudoinverse of $A$ is the linear operator
$A^{+}:\mathbb{R}^{m}\to\mathbb{R}^{n}$ defined
$A^{+}=\sum_{i=1}^{k}\sigma^{-1}_{i}u_{i}v_{i}^{T}$. While this is in the most
compact definition of the pseudoinverse, it is not the most informative.
Equivalently, the pseudoinverse of $A:\mathbb{R}^{m}\to\mathbb{R}^{n}$ is the
unique linear operator with the following properties: (1) $A^{+}$ maps each
vector $x\in\operatorname{im}A$ to the unique vector
$y\in\operatorname{im}A^{T}$ such that $Ay=x$ and (2) $A^{+}$ maps each vector
in $(\operatorname{im}A)^{\perp}$ to 0. The following are well-known
properties of the pseudoinverse that follow from these definitions

######  Lemma 2.6.

Let $A:\mathbb{R}^{m}\to\mathbb{R}^{n}$ be a linear map.

  1. 1.

$(AA^{T})^{+}=(A^{T})^{+}A^{+}$.

  2. 2.

For $x\in\operatorname{im}A$, $A^{+}x=\arg\min\\{\|y\|:Ay=x\\}$

##### Bra-Ket Notation.

When discussing quantum algorithms, we will use bra-ket notation for vectors.
As this paper may also be of interest to topologists who may be unfamiliar
with this notation, we introduce bra-ket notation now. Assuming a fixed basis
for a finite vector space, a bra is a row vector represented by the notation
$\langle v\rvert$. A ket is a column vector represented by the notation
$\lvert v\rangle$. Using bras and kets, we can represent an inner product as
$\langle u|v\rangle$, an outer product as $\lvert u\rangle\langle v\rvert$, or
a tensor product as $\lvert u\rangle\lvert v\rangle$.

##  3 The Incremental Algorithm for Computing Betti Numbers.

Figure 1: Left: The 1-cycle is null-homologous as it is the boundary of the
pictured 2-chain. Right: The 1-cycle is not null-homologous as it is not the
boundary of any 2-chain. Coefficients on colored simplices are $\pm 1$.
Orientations on the simplices have been omitted for simplicity.

In this section, we review the incremental algorithm for computing Betti
numbers introduced by Delfinado and Edelsbrunner [Delfinado1993]. The
incremental algorithm is a generic framework for computing Betti numbers based
around the primitive of null-homology testing. See Figure 1

######  Problem (Null-Homology Testing).

Given a simplicial complex $\mathcal{K}$ and a cycle $\gamma$ in
$\mathcal{K}$, determine if $\gamma$ is null-homologous.

The Incremental Algorithm for Computing Betti Numbers computes $\beta_{d}$ by
testing if the boundary of simplices are null-homologous. Specifically, the
incremental algorithm incrementally adds $d$-simplices to the simplicial
complex and and then performs a null-homology test on their boundaries to see
how the dimension of the spaces $\ker\partial_{d}$ and
$\operatorname{im}\partial_{d+1}$ change.

To see how this works, fix an order on the $d$-simplices
$\mathcal{K}_{d}=\\{\sigma_{1},\ldots,\sigma_{d}\\}$, and then iteratively add
each simplex $\sigma_{i}$ in increasing order of $i$. Adding the simplex
$\sigma_{i}$ will either increase the dimension of $\ker\partial_{d}$ or
$\operatorname{im}\partial_{d-1}$ by 1. If $\partial\sigma_{i}$ is null-
homologous in $\mathcal{K}^{d-1}\cup\\{\sigma_{1},\ldots,\sigma_{i-1}\\}$,
then adding $\sigma_{i}$ will increase the dimension of $\ker\partial_{d}$ by
1, which also increases $\beta_{d}$ by 1. If not, then adding $\sigma_{i}$
will decrease $\operatorname{im}\partial_{d-1}$ by 1, which also decreases
$\beta_{d-1}$ by 1.333In their original paper on the incremental algorithm
[Delfinado1993], Delfinado and Edelsbrunner phrase this slightly differently
as testing “whether $\sigma_{i}$ is in [the support of] a cycle.” It is
straightforward to verify that $\sigma_{i}$ is in the support of a cycle if
and only if $\partial\sigma_{i}$ is null-homologous. The incremental algorithm
is summarized in Algorithm 1.

Algorithm 1 The incremental algorithm for computing the $d$th Betti Number
$\beta_{d}$ [Delfinado1993]

$\beta_{d}\leftarrow 0$

for $\sigma_{i}\in\mathcal{K}_{d}=\\{\sigma_{1},\ldots,\sigma_{n_{d}}\\}$ do

if $\partial\sigma_{i}$ is null-homologous in
$\mathcal{K}^{d-1}\cup\\{\sigma_{1},\ldots,\sigma_{i-1}\\}$ then

$\beta_{d}\leftarrow\beta_{d}+1$

end if

end for

for $\tau_{j}\in\mathcal{K}_{d+1}=\\{\tau_{1},\ldots,\tau_{n_{d+1}}\\}$ do

if $\partial\tau_{j}$ is not null-homologous in
$\mathcal{K}^{d}\cup\\{\tau_{1},\ldots,\tau_{j-1}\\}$ then

$\beta_{d}\leftarrow\beta_{d}-1$

end if

end for

Return $\beta_{d}$

In the classical matrix reduction algorithm for computing Betti numbers,
testing whether $\partial\sigma_{i}$ is null-homologous is done by reducing
the column corresponding to $\sigma_{i}$ in the boundary matrix, which takes
$O(n_{d-1}n_{d})$ time in the worst case. However, there are special cases
where null-homology testing can be performed much more quickly. For example,
when a simplicial complex is embedded in $\mathbb{R}^{3}$ or the 3-sphere,
null-homology testing can be performed in nearly-linear time using the union-
find algorithm [Delfinado1993]. In the next section, we give a quantum
algorithm for null-homology testing.

##  4 A Quantum Algorithm for Null-Homology Testing.

In this section, we provide a quantum algorithm based on the span program
model to decide whether or not a cycle $\gamma$ is null-homologous in a
simplicial complex $\mathcal{K}$.

Our algorithm is a generalization of the quantum algorithm developed by Belovs
and Reichardt to decide $st$-connectivity in a graph [Belovs2012]. Their
algorithm is parameterized by the effective resistance and capacitance between
the vertices $s$ and $t$. The query complexity of our algorithm is
parameterized by higher-dimensional analogues of effective resistance and
capacitance of $\gamma$ that we introduce in Section 4.3.1.

Upper bounds on the effective resistance and capacitance in graphs imply a
query complexity of $O(n^{3/2})$ for $st$-connectivity, where $n$ is the
number of vertices [jarret_et_al:LIPIcs:2018:9512]. In Section 5, we provide
upper bounds on the effective resistance and capacitance. Our upper bounds on
effective resistance and capacitance imply that the query complexity is
polynomial in both the number of $d$-simplices as well as the cardinality of
the largest torsion subgroup of a relative homology group of $\mathcal{K}$. In
the case that $\mathcal{K}$ is a graph, our analysis of the witness sizes
matches the $O(n^{3/2})$ upper bounds of previous analyses. Specifically,
under the assumptions that $\mathcal{K}$ is relative torsion free and that
$\gamma$ is the boundary of a $d$-simplex (which may or may not be included in
the complex), we match the $O(n^{3/2})$ upper bound. These assumptions are
always true for $st$-connectivity in graphs, which is why we match the query
complexity for this problem. However, in Section 5.2, we provide examples of
simplicial complexes where the effective resistance or capacitance of $\gamma$
is exponentially large.

###  4.1 A Brief Introduction to Span Programs.

Span programs were first defined by Karchmer and Wigderson [Karchmer] and were
first used for quantum algorithms by Reichardt and Špalek [Reichardt2012].
Intuitively, a span program is a model of computation which encodes a boolean
function $f\colon\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ into the geometry of two
vector spaces and a linear operator between them. Encoding $f$ into a span
program implies the existence of a quantum query algorithm evaluating $f$
(Theorem 4.1.)

######  Definition 1.

A span program $\mathcal{P}=(\mathcal{H},\mathcal{U},\lvert\tau\rangle,A)$
over the set of strings $\\{0,1\\}^{n}$ is a 4-tuple consisting of:

  1. 1.

A finite dimensional Hilbert space
$\mathcal{H}=\mathcal{H}_{1}\oplus\dots\oplus\mathcal{H}_{n}$ where
$\mathcal{H}_{i}=\mathcal{H}_{i,0}\oplus\mathcal{H}_{i,1}$,

  2. 2.

a vector space $\mathcal{U}$,

  3. 3.

a non-zero vector $\lvert\tau\rangle\in\mathcal{U}$, called the target vector

  4. 4.

a linear operator $A\colon\mathcal{H}\rightarrow\mathcal{U}$.

For every string $x=(x_{1},\dots,x_{n})\in\\{0,1\\}^{n}$ we associate the
Hilbert space
$\mathcal{H}(x)=\mathcal{H}_{1,x_{1}}\oplus\dots\oplus\mathcal{H}_{N,x_{n}}$
and the linear operator
$A(x)=A\Pi_{\mathcal{H}(x)}\colon\mathcal{H}\rightarrow\mathcal{U}$ where
$\Pi_{\mathcal{H}(x)}$ is the projection of $\mathcal{H}$ onto
$\mathcal{H}(x)$. A string $x\in\\{0,1\\}^{n}$ is a positive instance if
$\lvert\tau\rangle\in\operatorname{im}A(x)$ and is a negative witness
otherwise.

A span program $\mathcal{P}$ decides the function
$f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ if $f(x)=1$ when $x$ is a positive instance
and $f(x)=0$ when $x$ is a negative instance. A span program can also evaluate
a partial boolean function $g\colon D\to\\{0,1\\}$ where
$D\subset\\{0,1\\}^{n}$ by the same criteria.

Span programs are a popular method in quantum computing because there are
upper bounds on the complexity of evaluating span programs in the query model.
The query model evaluates the complexity of a quantum algorithm by its query
complexity, the number of times it queries an input oracle. In our case, the
input oracle returns the bits of the binary string $x$. The input oracle
$\mathcal{O}_{x}$ takes $\mathcal{O}_{x}:\lvert i\rangle\lvert
b\rangle\to\lvert i\rangle\lvert b\oplus x_{i}\rangle$ where $i\in[n]$.
Observe that the states $\lvert i\rangle$ can be stored on $\lceil\log
n\rceil$ qubits. Reichardt [Reichardt2009] showed that the query complexity of
a span program is a function of the positive and negative witness sizes of the
program, which we now define.

######  Definition 2.

Let $\mathcal{P}$ be a span program and let $x\in\\{0,1\\}^{n}$. A positive
witness for $x$ is a vector $\lvert w\rangle\in\mathcal{H}(x)$ such that
$A\lvert w\rangle=\lvert\tau\rangle$. The positive witness size of $x$ is

$w_{+}(x,\mathcal{P})=\min\\{\|\lvert w\rangle\|^{2}:\lvert
w\rangle\in\mathcal{H}(x),\,A\lvert w\rangle=\lvert\tau\rangle\\}.$

If no positive witness exists for $x$, then $w_{+}(x,\mathcal{P})=\infty$.

A negative witness for $x$ is a linear map $\langle
w\rvert:\mathcal{U}\to\mathbb{R}$ such that $\langle w\rvert
A\Pi_{\mathcal{H}(x)}=0$ and $\langle w|\tau\rangle=1$. The negative witness
size of $x$ is

$w_{-}(x,\mathcal{P})=\min\\{\|\langle w\rvert A\|^{2}:\langle
w\rvert:\mathcal{U}\to\mathbb{R},\,\langle w\rvert
A\Pi_{\mathcal{H}(x)}=0,\,\langle w|\tau\rangle=1\\}.$

If no negative witness exists for $x$, then $w_{-}(x,\mathcal{P})=\infty$.

######  Theorem 4.1 (Reichardt [Reichardt2009]).

Let $D\subset\\{0,1\\}^{n}$ and $f:D\to\\{0,1\\}$. Let $\mathcal{P}$ be a span
program that decides $f$. Let $W_{+}(f,\mathcal{P})=\max_{x\in
f^{-1}(1)}w_{+}(x,\mathcal{P})$ and $W(f,\mathcal{P})_{-}=\max_{x\in
f^{-1}(0)}w_{-}(x,\mathcal{P})$. There is a bounded error quantum algorithm
that decides $f$ with query complexity
$O\left(\sqrt{W_{+}(f,\mathcal{P})W_{-}(f,\mathcal{P})}\right)$.

A caveat to the query complexity model is that in general the time complexity
of an algorithm can be much larger than its query complexity.

###  4.2 A Span Program for Null-Homology Testing.

In this section, we present a span program for testing if a cycle is null-
homologous in a simplicial complex. This span program is a generalization of
the span program for $st$-connectivity defined in [Karchmer] and used to
develop quantum algorithms in [Belovs2012, cade,
jarret_et_al:LIPIcs:2018:9512, Jeffery2017].

Let $\mathcal{K}$ be a $d$-dimensional simplicial complex. Let $\gamma\in
C_{d-1}(\mathcal{K})$ be a $(d-1)$-cycle. Let $n_{d}$ be the number of
$d$-simplices in $\mathcal{K}$. Order the $d$-simplices
$\\{\sigma_{1},\ldots,\sigma_{n_{d}}\\}$. Let
$w\colon\mathcal{K}_{d}\rightarrow\mathbb{R}$ be a weight function on the
$d$-simplices, and let $W:C_{d}(\mathcal{K})\to C_{d}(\mathcal{K})$ be the
diagonal weight matrix. We define a span program over the strings
$\\{0,1\\}^{n_{d}}$ as follows.

  1. 1.

$\mathcal{H}=C_{d}(\mathcal{K})$, with
$\mathcal{H}_{i,1}=\operatorname{span}\\{\lvert\sigma_{i}\rangle\\}$ and
$\mathcal{H}_{i,0}=\\{0\\}$.

  2. 2.

$\mathcal{U}=C_{d-1}(\mathcal{K})$

  3. 3.

$A=\partial_{d}\sqrt{W}\colon C_{d}(\mathcal{K})\rightarrow
C_{d-1}(\mathcal{K})$

  4. 4.

$\lvert\tau\rangle=\gamma$

We denote the above span program by $\mathcal{P}_{\mathcal{K}}$. Let
$x\in\\{0,1\\}^{n_{d}}$ be a binary string. We define the subcomplex
$\mathcal{K}(x)\coloneqq\mathcal{K}^{d-1}\cup\\{\sigma_{i}:x_{i}=1\\}$; that
is, $\mathcal{K}(x)$ contains the $d$-simplices $\sigma_{i}$ such that
$x_{i}=1$. There exists a solution $v$ to the linear system
$\partial_{d}\sqrt{W}\Pi_{\mathcal{K}(x)}v=\gamma$ if and only if the cycle
$\gamma$ is null-homologous in $\mathcal{K}(x)$ if and only if $x$ is a
positive instance of $\mathcal{P}_{\mathcal{K}}$. The span program
$\mathcal{P}_{\mathcal{K}}$ decides the boolean function
$f:\\{0,1\\}^{n_{d}}\to\\{0,1\\}$ where $f(x)=1$ if and only if $\gamma$ is a
null-homologous cycle in the subcomplex $\mathcal{K}(x)$.

Theorem 4.1 allows us to bound the query complexity of our span program by the
size of positive and negative witness. In the next section, we provide bounds
on the positive and negative witness size of our span program.

###  4.3 Witness Sizes of the Null-Homology Testing Span Program.

In this section, we bound the positive and negative witness sizes of our span
program for null-homology testing. We will show that they are equal to the
quantities called the effective resistance and effective capacitance of the
cycle. We first introduce these quantities and show some of their properties.
Then, in Section 4.3.4, we show that these quantities are the witness sizes of
our span program.

####  4.3.1 Background: Effective Resistance and Effective Capacitance.

Let $\gamma\in C_{d-1}(\mathcal{K})$ be a cycle in a simplicial complex. We
associate two quantities with $\gamma$: its effective resistance and effective
capacitance. The effective resistance is finite if and only if $\gamma$ is
null-homologous, and the effective capacitance is finite if and only if
$\gamma$ is not null-homologous. We begin with the definition of effective
resistance.

######  Definition 3.

Let $\mathcal{K}$ be a simplicial complex with weight function
$w:\mathcal{K}\to\mathbb{R}^{+}$. Let $\gamma$ be a $(d{-}1)$-cycle in
$\mathcal{K}$. The effective resistance of $\gamma$ is

$\mathcal{R}_{\gamma}(\mathcal{K},W)=\begin{cases}\gamma^{T}\left(L^{up,\,W}_{d-1}\right)^{+}\gamma&\text{if
$\gamma$ is null-homologous}\\\ \infty&\text{otherwise}\\\ \end{cases}$

When obvious or when $\mathcal{K}$ is unweighted, we drop the weights from the
notation and write $\mathcal{R}_{\gamma}(\mathcal{K})$.

This definition of effective resistance is consistent with effective
resistance in graphs (see [Spielman2019]) and other definitions of effective
resistance in simplicial complexes [Kook2018, osting2020sparsification,
Hansen2019].444Effective resistance can be defined even more generally using
the combinatorial Laplacian. For simplicity, consider the unweighted case. For
a null-homologous $(d-1)$-cycle $\gamma$, the effective resistance can be
defined $\mathcal{R}_{\gamma}(\mathcal{K})=\gamma^{T}L_{d-1}^{+}\gamma$. This
equals the formula in Definition 3 because (1)
$L_{d-1}^{+}=(L_{d-1}^{up})^{+}+(L_{d-1}^{down})^{+}$ and (2)
$\gamma^{T}(L_{d-1}^{down})^{+}\gamma=0$ as $\gamma\in\ker
L_{d-1}^{down}=\ker(L_{d-1}^{down})^{+}$.However, this definition gives little
intuition about effective resistance. We now prove there is an alternative
definition of effective resistance in terms of chains with boundary $\gamma$.
We begin with two definitions.

######  Definition 4.

Given a $d$-dimensional simplicial complex $\mathcal{K}$ and a
$(d-1)$-dimensional null-homologous cycle $\gamma$, a unit $\gamma$-flow is a
$d$-chain $f\in C_{d}(\mathcal{K})$ such that $\partial f=\gamma$.

In the case of graphs, a unit $st$-flow is a flow sending 1 unit of flow from
$s$ to $t$.

######  Definition 5.

Given a $d$-dimensional simplicial complex $\mathcal{K}$ with weight function
$w:C_{d}(\mathcal{K})\to\mathbb{R}^{+}$ and a unit $\gamma$-flow $f$, the flow
energy of $f$ on $\mathcal{K}$ is

$\mathsf{J}(f)=\sum_{\sigma\in\mathcal{K}^{(d)}}\frac{f(\sigma)^{2}}{w(\sigma)}=f^{T}W^{-1}f$

where $W$ is the $n_{d}\times n_{d}$ diagonal matrix whose entries are the
weights of the $d$-simplices.

We will now relate unit $\gamma$-flows and their energy to effective
resistance. This generalizes a formula for effective resistance in graphs
[bollobas1998modern, Chapter IX Corollary 6].

######  Lemma 4.2.

Let $\mathcal{K}$ be a simplicial complex and let $\gamma$ be a null-
homologous $d$-cycle. The effective resistance of $\gamma$ is the minimum flow
energy over all unit $\gamma$-flows, i.e.

$\mathcal{R}_{\gamma}(\mathcal{K})=\min\\{\mathsf{J}(f)\mid\partial
f=\gamma\\}$

###### Proof.

Our first observation is that we can factor the weighted Laplacian as

$\displaystyle L_{d}^{up,\,W}$ $\displaystyle=\partial_{d+1}W\delta_{d}$
$\displaystyle=\partial_{d+1}W^{1/2}W^{1/2}\delta_{d}$
$\displaystyle=(\partial_{d+1}W^{1/2})(\partial_{d+1}W^{1/2})^{T}$

By Lemma 2.6 Part 1,
$(L_{d}^{up,\,W})^{+}=((\partial_{d+1}W^{1/2})^{T})^{+}(\partial_{d+1}W^{1/2})^{+}$.
Therefore,

$\mathcal{R}_{\gamma}(\mathcal{K})=\gamma^{T}((\partial_{d+1}W^{1/2})^{T})^{+}(\partial_{d+1}W^{1/2})^{+}\gamma=\|(\partial
W^{1/2})^{+}\gamma\|^{2}.$

By Lemma 2.6 Part 2, $\mathcal{R}_{\gamma}(\mathcal{K})$ is the minimum
squared-norm of a vector that $\partial_{d+1}W^{1/2}$ maps to $\gamma$. Let
$f=(\partial W^{1/2})^{+}\gamma$; the vector $f$ is the unit $\gamma$-flow of
minimum flow energy, which we now prove.

A vector $v$ is mapped to $\gamma$ by $\partial W^{1/2}$ iff $W^{1/2}v$ is
mapped to $\gamma$ by $\partial$ as $W^{1/2}$ is a bijection; that is all to
say, $W^{1/2}v$ is a unit $\gamma$-flow. Moreover, the flow energy of
$W^{1/2}v$ is

$\displaystyle\mathsf{J}(W^{1/2}v)$
$\displaystyle=(W^{1/2}v)^{T}W^{-1}W^{1/2}v$
$\displaystyle=v^{T}W^{1/2}W^{-1}W^{1/2}v$ $\displaystyle=v^{T}v$
$\displaystyle=\|v\|^{2}$

Therefore, the minimum flow energy of a unit $\gamma$-flow is the minimum
squared-norm of a vector that $\partial W^{1/2}$ maps to $\gamma$, which we
previously saw was $\mathcal{R}_{\gamma}(\mathcal{K})$. ∎

We call $(\partial W^{1/2})^{+}\gamma$ the minimum-energy unit
$\gamma$-flow555The minimum-energy unit $\gamma$-flow is unlike the optimal
bounded chain [Dunfield2011], another minimum spanning object of a null-
homologous cycle. The optimal bounded chain of $\gamma$ is (often) defined
with $\mathbb{Z}_{2}$ coefficients and is the smallest set of simplices with
boundary $\gamma$; it is analogous to an $s,t$-path in a graph. The minimum-
energy $\gamma$-flow is defined with real coefficients and can have fractional
values on simplices; it is analogous to an $s,t$-flow in a graph. While the
weight of the optimal bounded chain is always minimized when fewer simplices
are used, the minimum minimum-energy $\gamma$-flow will push a fraction of the
flow on many chains spanning $\gamma$. Indeed, in Section B, we prove the
minimum-energy $\gamma$-flow pushes a non-zero amount of flow on each chain
spanning $\gamma.$.

Some of the key properties of effective resistance in graphs are the series
and parallel formulas and Rayleigh Monotonicity. In Appendix B, we prove
analogous results for higher-dimensional effective resistance.

While effective resistance has previously been generalized from graphs to
simplicial complexes [Hansen2019, Kook2018, osting2020sparsification], to our
knowledge, we are the first to generalize effective capacitance from graphs to
simplicial complexes. Unfortunately, effective capacitance is more opaque than
effective resistance, both in graphs and simplicial complexes. The definition
of effective capacitance is less intuitive than the definition for effective
resistance, and there are fewer results about effective capacitance in graphs
than effective resistance.

Before defining effective capacitance in simplicial complexes, we review the
definition of effective capacitance in graphs, which can be found in
[jarret_et_al:LIPIcs:2018:9512]. Let $G$ be a graph such that $s$ and $t$ are
connected in $G$, and let $H\subseteq G$ be a subgraph such that $s$ and $t$
are not connected in $H$. A unit $st$-potential is a function $p\colon
V(G)\rightarrow\mathbb{R}$ such that $p(t)=1$, $p(s)=0$, and $p(u)=p(v)$ for
any two vertices $u,v$ in the same connected component. The potential energy
of $p$ is $\sum_{\\{u,v\\}\in E(G)}(p(u)-p(v))^{2}$. The effective capacitance
of $s$ and $t$ is the minimum potential energy of any $st$-potential.

Our definition of effective capacitance in simplicial complexes will be
analogous to the defintion in graphs; namely, the effective capacitance of a
cycle $\gamma$ will be the minimum energy of a unit $\gamma$-potential.

Figure 2: Left: A 1-cycle $\gamma$ with $\pm 1$ coefficients on the blue
edges. Right: A unit $\gamma$-potential $p$ with $\pm 1$ coefficients on the
red edges. If this complex is unweighted, then the potential energy of $p$ is
$1$. It can be proved that $p$ is a minimal energy unit $\gamma$-potential
777The proof that $p$ is the minimal energy unit $\gamma$-potential is
analogous to the proof of Theorem 5.14. The trick to proving this is to
realize that because there is a single 2-simplex in
$\mathcal{K}\setminus\mathcal{L}$, all unit $\gamma$-potentials have the same
potential energy., so $\mathcal{C}_{\gamma}(\mathcal{L},\mathcal{K})=1$

######  Definition 6.

Let $\mathcal{L}$ be a simplicial complex, and let $\gamma\in
C_{d-1}(\mathcal{L})$ be a $(d{-}1)$-cycle that is not null-homologous in
$\mathcal{L}$. A unit $\gamma$-potential in $\mathcal{L}$ is a $(d{-}1)$-chain
$p$ such that $\delta_{d-1}[\mathcal{L}]p=0$ and $p^{T}\gamma=1$.

Figure 7 shows a $\gamma$-potential in a simplicial complex.

######  Definition 7.

Given simplicial complexes $\mathcal{L}\subset\mathcal{K}$ with weight
function $w:C_{d}(\mathcal{K})\to\mathbb{R}$ and a $\gamma$-potential $p$ in
$\mathcal{L}$, the potential energy of $p$ on $\mathcal{K}$ is

$\mathcal{J}(p)=\sum_{\sigma\in\mathcal{K}_{d}}\delta[\mathcal{K}]p(\sigma)^{2}w(\sigma)=(\delta[\mathcal{K}]p)^{T}W(\delta[\mathcal{K}]p).$

######  Definition 8.

Let $\mathcal{L}\subset\mathcal{K}$ be simplicial complexes, and let
$\gamma\in C_{d-1}(\mathcal{L})$ be a $(d-1)$-cycle that is null-homologous in
$\mathcal{K}$. If $\gamma$ is not null-homologous in $\mathcal{L}$, the
effective capacitance of $\gamma$ in $\mathcal{L}$ and $\mathcal{K}$ is

$\mathcal{C}_{\gamma}(\mathcal{L},\mathcal{K})=\begin{cases}\underset{p:\text{$p$
unit $\gamma$-potential}}{\min}\>\mathcal{J}(p)&\text{$\gamma$ is not null-
homologous}\\\ \infty&\text{$\gamma$ is null-homologous}\end{cases}$

Our definition of effective capacitance in simplicial complexes matches the
definition of effective capacitance in graphs; however, this may not be
obvious at first glance, as our definition of $st$-potential is more general.
A function $p:V(G)\to\mathbb{R}$ is equivalent to a 0-chain $p\in C_{0}(H)$,
and the requirement that $p(u)=p(v)$ for any two vertices $u,v$ in the same
connected component is equivalent to saying $\delta_{0}[H]=0$; however, not
all chains $p$ such that $p^{T}(s-t)=1$ satisfy $p(s)=1$ and $p(t)=0$. (For
example, it could be the case that $p(s)=\frac{1}{2}$ and
$p(t)=-\frac{1}{2}$.) This difference in the definition ends up not mattering
though. This is because the all-1s vectors $1\in\ker\delta_{0}$ for any graph.
Using this fact, we can see that for any $st$-potential $p$ under our
definition, there is an $st$-potential $p^{\prime}$ under the previous
definition with the same potential energy, namely the potential
$p^{\prime}=p-p(t)1$.

There is one small detail left to show. It is not obvious from the definition
that a unit $\gamma$-potential will even exist for $\gamma$. We prove this in
the following lemma.

######  Lemma 4.3.

Let $\mathcal{L}$ be a simplicial complex, and let $\gamma\in
C_{d-1}(\mathcal{L})$ be a cycle. Then there exists a unit $\gamma$-potential
in $\mathcal{L}$ if and only if $\gamma$ is not null-homologous in
$\mathcal{L}$.

###### Proof.

Observe that
$\ker\delta_{d-1}[\mathcal{L}]=(\operatorname{im}\partial_{d}[\mathcal{L}])^{\perp}$
as $\delta_{d-1}[\mathcal{L}]=\partial_{d}[\mathcal{L}]^{T}$. Assume there is
a $\gamma$-potential $p$ in $\mathcal{L}$. As $\delta[\mathcal{L}]p=0$, then
$p\in\ker\delta_{d-1}[\mathcal{L}]=(\operatorname{im}\partial_{d}[\mathcal{L}])^{\perp}$.
As $\gamma^{T}p=1$ we see that $\gamma$ has a non-zero component in
$(\operatorname{im}\partial_{d}[\mathcal{L}])^{\perp}$, so
$\gamma\not\in\operatorname{im}\partial_{d}[\mathcal{L}]$.

Alternatively, suppose that $\gamma$ is not null-homologous in $\mathcal{L}$.
Then $\gamma$ has a non-zero component in
$(\operatorname{im}\partial_{d}[\mathcal{L}])^{\perp}=\ker\delta_{d-1}[\mathcal{L}]$.
Let $q=\Pi_{\ker\delta[\mathcal{L}]}\gamma$, where
$\Pi_{\ker\delta[\mathcal{L}]}$ is the projection operator onto
$\ker\delta_{d-1}[\mathcal{L}]$. Then $\gamma^{T}q\neq 0$ and
$\delta_{d-1}[\mathcal{L}]q=0$. The vector $q$ is not necessarily a unit
$\gamma$-potential as it is not necessarily the case that $\gamma^{T}q=1$, but
the scaled vector $p=\frac{1}{\gamma^{T}q}q$ is a unit $\gamma$-potential. ∎

One interesting property of effective resistance and capacitance in graphs is
that, in planar graphs, the effective resistance between certain pair of nodes
in the dual graph equals the effective capacitance between certain pairs of
nodes in the primal graph. In Appendix C, we show that an analogous property
holds for higher-dimensional embedded simplicial complexes.

####  4.3.2 Effective Resistance and the Spectral Gap.

In this section, we give a characterization of the spectral gap of the
combinatorial Laplacian in terms of the effective resistance of a cycle. While
the proof of this lemma follows from some simple linear algebra, the advantage
of this theorem comes down to the fact that effective resistance is easier to
work with than eigenvectors of the Laplacian (in our opinion). We first relate
effective resistance to the spectral gap of the up Laplacian. We then show how
this relates effective resistance to the spectral gap of the combinatorial
Laplacian. We prove this relationship for unweighted simplicial complexes;
however, the theorems also hold for weighted simplicial complexes.

######  Lemma 4.4.

The spectral gaps of the up Laplacian $L^{up}_{d-1}$ and down Laplacian
$L^{down}_{d}$ are

$\lambda_{\min}(L^{down}_{d})=\lambda_{\min}(L^{up}_{d-1})=\min\\{\mathcal{R}^{-1}_{\gamma}(\mathcal{K}):\gamma\in\operatorname{im}\partial_{d},\,\|\gamma\|=1\\}.$

###### Proof.

We first prove this is the case for the spectral gap of the up Laplacian
$L^{up}_{d}$. We then show the equivalence of $\lambda_{\min}(L^{down}_{d})$
and $\lambda_{\min}(L^{up}_{d-1})$.

The lemma follows from some standard facts about symmetric matrices. First,
because $L^{up}_{d}$ is symmetric, a vector $x$ is an eigenvector of
$L^{up}_{d}$ with non-zero eigenvalue $\lambda$ if and only if $x$ is an
eigenvector of $(L_{d}^{up})^{+}$ with non-zero eigenvalue $\lambda^{-1}$.
This follows from the fact that the singular values and vectors of a symmetric
matrix are also its eigenvalues and eigenvectors. Therefore, the smallest non-
zero eigenvalue of $L^{up}_{d}$ is the inverse of the largest non-zero
eigenvalue of $(L^{up}_{d})^{+}$, or
$\lambda_{\min}(L_{d}^{up})=\lambda^{-1}_{\max}((L_{d}^{up})^{+})$ for short.

Next, we can characterize the eigenvalues of the symmetric matrix
$(L_{d}^{up})^{+}$ with the Courant-Fischer Theorem. We use a special case of
the theorem, which says that
$\lambda_{\max}((L_{d}^{up})^{+})=\max\\{x^{T}(L_{d}^{up})^{+}x:\|x\|=1\\}$
and $x_{\max}=\arg\max\\{x^{T}(L_{d}^{up})^{+}x:\|x\|=1\\}$, where $x_{\max}$
is an eigenvector corresponding to $\lambda_{\max}((L_{d}^{up})^{+})$. The
lemma follows from the fact that
$x_{\max}\in\operatorname{im}L_{d}^{up}=\operatorname{im}\partial_{d}$, which
is the case because $x_{\max}$ is the eigenvector of a non-zero eigenvalue of
$L_{d}^{up}$.

Finally, $\lambda_{\min}(L^{up}_{d})=\lambda_{\min}(L^{down}_{d-1})$ by Lemma
2.2 Part 1. ∎

####  4.3.3 Effective Capacitance and the Spectral Gap.

In the previous section, we saw that the effective resistance of a unit-length
cycle is always bounded above by the inverse of the spectral gap of the
combinatorial Laplacian. While we don’t know such a bound for the effective
capacitance of arbitrary cycles, we can prove such a bound for the effective
capacitance for the boundaries of simplices. This is sufficient for our
analysis of the incremental algorithm as the only cycles we consider are the
boundaries of simplices.

Before proving our upper bound on the effective capacitance of a cycle, we
need to prove an upper bound on the largest singular value of the coboundary
matrix.

######  Lemma 4.5.

Let $\mathcal{K}$ be a simplicial complex with $n_{0}$ vertices. For any
$d\geq 1$, the largest singular value of the coboundary matrix
$\delta_{d-1}[\mathcal{K}]$ is
$\sigma_{\text{max}}(\delta_{d-1})=O(\sqrt{n_{0}})$.

###### Proof.

This follows as the squared singular values of $\delta_{d-1}$ are the
eigenvalues of the up Laplacian $\delta_{d-1}^{T}\delta_{d-1}=L_{d-1}^{up}$.
(This is true for any matrix of the form $A^{T}A$.) The maximum eigenvalue of
$L_{d-1}^{up}$ is known to be at most $n_{0}$ by Theorem 2.4. ∎

######  Theorem 4.6.

Let $\mathcal{L}\subset\mathcal{K}$ be $d$-dimensional simplicial complexes.
Let $\gamma\in C_{d-1}(\mathcal{L})$ be a $(d-1)$-cycle that is null-
homologous in $\mathcal{K}$ but not in $\mathcal{L}$. Assume that
$\gamma=\partial\sigma$ for a $d$-simplex $\sigma\notin\mathcal{L}$.888The
theorem holds whether or not $\sigma\in\mathcal{K}$.The effective capacitance
of $\gamma$ in $\mathcal{K}$ is bounded above by
$\mathcal{C}_{\gamma}(\mathcal{L},\mathcal{K})=O\left(n_{0}\cdot\lambda_{\min}^{-1}(L_{d-1}[\mathcal{L}\cup\\{\sigma\\}])\right)$.

###### Proof.

We can express the constraints of a $\gamma$-potential $p$ in the following
set of linear equations:

$\begin{bmatrix}\phantom{0}\\\ \delta[\mathcal{L}]\\\ \phantom{\vdots}\\\
\gamma^{T}\end{bmatrix}p=\begin{bmatrix}0\\\
0\vphantom{\delta[\mathcal{L}]}\\\ \vdots\\\ 1\end{bmatrix}$

To simplify notation, let
$C=\begin{bmatrix}\delta[\mathcal{L}]^{T}&\gamma\end{bmatrix}^{T}$ and
$b=\begin{bmatrix}0&0&\cdots&1\end{bmatrix}^{T}$

We consider the smallest vector $p$ which satisfies these equations, which is
$p=C^{+}b$. Because $\gamma=\partial\sigma$, we can see that
$C=\delta[\mathcal{L}\cup\\{\sigma\\}]$. Therefore,
$\|p\|=O(\|C^{+}b\|)=O(\sigma^{-1}_{\min}(\delta[\mathcal{L}\cup\\{\sigma\\}])$,
where $\sigma_{\min}(\delta[\mathcal{L}\cup\\{\sigma\\}])$ is the smallest
non-zero singular value of $\delta[\mathcal{L}\cup\\{\sigma\\}]$. However, we
know that
$\sigma_{\min}=\sqrt{\lambda_{\min}(L_{d-1}^{up}[\mathcal{L}\cup\\{\sigma\\}])}\in\Omega(\sqrt{\lambda_{\min}(L_{d-1}[\mathcal{L}\cup\\{\sigma\\}])})$.
Therefore, $\|p\|\in
O\left(\sqrt{\lambda_{\min}^{-1}(L_{d-1}[\mathcal{L}\cup\\{\sigma\\}])}\right)$.

We now want to bound the potential energy of $p$. Using Lemma 4.5, we can
bound $\|\delta[\mathcal{K}]p\|^{2}\in
O(n_{0}\cdot\lambda_{\min}^{-1}(L_{d-1}[\mathcal{L}\cup\\{\sigma\\}]))$. ∎

####  4.3.4 Connecting Effective Resistance and Capacitance to Witness Sizes.

Given a string $x\in\\{0,1\\}^{n_{d}}$, we show in the following two lemmas
that $w_{+}(x,\mathcal{P}_{\mathcal{K}})=\mathcal{R}_{\gamma}(\mathcal{K}(x))$
and
$w_{-}(x,\mathcal{P}_{\mathcal{K}})=\mathcal{C}_{\gamma}(\mathcal{K}(x),\mathcal{K})$.
The proofs are simple calculations following from the definitions of effective
resistance and capacitance.

######  Lemma 4.7.

Let $x\in\\{0,1\\}^{n_{d}}$ be a positive instance. There is a bijection
between positive witnesses $\lvert w\rangle$ for $x$ and unit $\gamma$-flows
$f$ in $\mathcal{K}(x)$. Moreover, the positive witness size is equal to the
effective resistance of $\gamma$ in $\mathcal{K}(x)$; that is,
$w_{+}(x,\mathcal{P}_{\mathcal{K}})=\mathcal{R}_{\gamma}(\mathcal{K}(x))$.

###### Proof.

Let $\lvert w_{+}\rangle\in C_{d}(\mathcal{K})$ be a positive witness for $x$,
so $\partial_{d}\sqrt{W}\lvert w_{+}\rangle=\gamma$. We construct a unit
$\gamma$-flow $f$ in $\mathcal{K}(x)$ by $f=\sqrt{W}\lvert w_{+}\rangle$; $f$
is indeed a unit $\gamma$-flow as $\partial_{d}f=\partial_{d}\sqrt{W}\lvert
w_{+}\rangle=\gamma$. Moreover, $\lvert w_{+}\rangle=W^{-1/2}\lvert f\rangle$.
The flow energy of $\gamma$ is

$\displaystyle\mathsf{J}(f)$ $\displaystyle=\langle f\rvert W^{-1}\lvert
f\rangle$ $\displaystyle=\langle W^{-1/2}f|W^{-1/2}f\rangle$
$\displaystyle=\langle w_{+}|w_{+}\rangle$ $\displaystyle=\|\lvert
w_{+}\rangle\|^{2}.$

Hence, the flow energy of $f$ equals the witness size of $x$.

Conversely, let $f$ be a unit $\gamma$-flow in $\mathcal{K}(x)$ and define the
positive witness for $x$ as $\lvert w_{+}\rangle=W^{-1/2}\lvert f\rangle$. The
same computation in the above paragraph shows that the flow energy of $f$
equals the positive witness size of $x$. ∎

######  Lemma 4.8.

Let $x\in\\{0,1\\}^{n_{d}}$ be a negative instance. There is a bijection
between negative witnesses $\langle w_{-}\rvert$ for $x$ and unit
$\gamma$-potentials $p$ in $\mathcal{K}(x)$. Moreover, the negative witness
size is equal to the effective capacitance of $\gamma$ in $\mathcal{K}(x)$;
that is, $w_{-}(x,\mathcal{P}_{\mathcal{K}})=C_{\gamma}(\mathcal{K}(x))$.

###### Proof.

Let $\langle w_{-}\rvert$ be a negative witness for $x$. As $\langle w\rvert$
is a linear function from $C_{d-1}(\mathcal{K})$ to $\mathbb{R}$ we may view
it as a $(d-1)$-chain $p^{T}=\langle w\rvert$. Since $\langle
w_{-}|\gamma\rangle=1$, then $p^{T}\gamma=1$. To show that $p$ is a unit
$\gamma$-potential we must show that the coboundary of $p$ is zero in
$\mathcal{K}(x)$. By the definition of a negative witness we have

$\displaystyle 0$ $\displaystyle=\langle
w_{-}\rvert\partial_{d}\sqrt{W}\Pi_{\mathcal{K}(x)}$ $\displaystyle=\langle
p\rvert\partial_{d}\sqrt{W}\Pi_{\mathcal{K}(x)}$
$\displaystyle=\langle\delta_{d}(p)\rvert\sqrt{W}\Pi_{\mathcal{K}(x)}.$

Since $\sqrt{W}$ is a diagonal matrix and $\Pi_{\mathcal{K}(x)}$ restricts the
coboundary to the subcomplex $\mathcal{K}(x)$ we see that
$\langle\delta_{d}(p)|\sigma\rangle=0$ for any $\sigma\in\mathcal{K}(x)_{d}$.
To show that the witness size of $\langle w_{-}\rvert$ is equal to the
potential energy of $p$ we have

$\displaystyle\|\langle w_{-}\rvert\partial_{d}\sqrt{C}\|^{2}$
$\displaystyle=\langle p\partial_{d}\sqrt{W}|p\partial_{d}\sqrt{W}\rangle$
$\displaystyle=\langle\sqrt{W}\delta_{d}(p)|\sqrt{W}\delta_{d}(p)\rangle$
$\displaystyle=\sum_{\sigma\in\mathcal{K}_{d}}\langle\delta_{d}(p)|\sigma\rangle^{2}w(\sigma)$
$\displaystyle=\mathcal{J}(p).$

Conversely, let $p$ be a unit $\gamma$-potential for $\mathcal{K}(x)$ we
construct a negative witness for $x$ by setting $\langle w_{-}\rvert\coloneqq
p^{T}$. Since the coboundary of $p$ is zero in $\mathcal{K}(x)$ we have
$\langle\delta_{p}(p)|\sigma\rangle=0$ for each $\sigma\in\mathcal{K}(x)_{d}$
which implies $\langle w_{-}\rvert\partial_{d}\sqrt{W}\Pi_{\mathcal{K}(x)}=0$
by the reasoning in the previous paragraph. Also by the previous paragraph we
have that the potential energy of $p$ is equal to the negative witness size of
$\langle w_{-}\rvert$ which concludes the proof. ∎

From these two lemmas we obtain the main theorem of the section, the quantum
query complexity of $\gamma$.

######  Theorem 4.9.

Given a $d$-dimensional simplicial complex $\mathcal{K}$, a
$(d-1)$-dimensional cycle $\gamma$ that is null-homologous in $\mathcal{K}$,
and a $d$-dimensional subcomplex $\mathcal{K}(x)\subseteq\mathcal{K}$, there
exists a quantum algorithm deciding whether or not $\gamma$ is null-homologous
in $\mathcal{K}(x)$ with quantum query complexity
$O\left(\sqrt{\mathcal{R}_{\max}(\gamma)\mathcal{C}_{\max}(\gamma)}\right)$,
where $\mathcal{R}_{\max}(\gamma)$ is the maximum finite effective resistance
$\mathcal{R}_{\gamma}(\mathcal{L})$ in any subcomplex
$\mathcal{L}\subset\mathcal{K}$, and $\mathcal{C}_{\max}(\gamma)$ is the
maximum finite effective capacitance
$\mathcal{C}_{\gamma}(\mathcal{L},\mathcal{K})$ in any subcomplex
$\mathcal{L}\subset\mathcal{K}$.

###### Proof.

By Theorem 4.1, the span program $\mathcal{P}_{\mathcal{K}}$ can be converted
into a quantum algorithm whose query complexity is
$O\left(\sqrt{W_{+}(f,\mathcal{P}_{\mathcal{K}})W_{-}(f,\mathcal{P}_{\mathcal{K}})}\right)$
where $W_{+}(f,\mathcal{P}_{\mathcal{K}})=\max_{x\in
f^{-1}(1)}\mathcal{R}_{\gamma}(\mathcal{K}(x))=\mathcal{R}_{\max}(\gamma)$ and
$W_{-}(f,\mathcal{P}_{\mathcal{K}})=\max_{x\in
f^{-1}(0)}\mathcal{C}_{\gamma}(\mathcal{K}(x),\mathcal{K})=\mathcal{C}_{\max}(\gamma)$.
∎

###  4.4 Time Efficient Implementations of the Span Program.

We have given bounds on the query complexity of null-homology testing;
however, this does not imply a bound on the time complexity of evaluating this
span program, as the query complexity does not account for the work outside of
the oracle calls. In Appendix D, we describe the details of an implementation
of this algorithm. For certain special cases, we are able to analyse the time
complexity of the algorithm. We describe this special case below.

There are two obstacles to a time-efficient implementation of the span
program: the weights and the input cycle $\gamma$. The weights on the
$d$-simplices make it difficult to implement the matrix $\partial\sqrt{W}$, as
the weights on the simplices can be arbitrary real numbers. The input cycle
$\gamma$ is difficult to create on a quantum computer as the entries of
$\gamma$ can also be arbitrary real numbers.

Accordingly, we can give a quantum algorithm of bounded time complexity in one
particular instance: when $\mathcal{K}$ is unweighted and $\gamma$ is the
boundary of a $d$-simplex. (We do not require the $d$-simplex to actually
appear in the complex.) While this is only a special case of the generic null-
homology testing algorithm, this is the only case we need for the incremental
algorithm for computing Betti numbers (Algorithm 1). The time complexity of
this case is given in the following theorem.

######  Theorem 4.10.

Let $\mathcal{K}$ be an unweighted simplicial complex with $n_{0}$ vertices,
let $\gamma\in C_{d-1}(\mathcal{K})$ a null-homologous cycle in $\mathcal{K}$,
and $\mathcal{K}(x)\subset\mathcal{K}$ be a simplicial complex. Furthermore,
assume that $\gamma$ is the boundary of a $d$-simplex and the complex is
unweighted. There is a quantum algorithm for deciding if $\gamma$ is null-
homologous in $\mathcal{K}(x)$ that runs in time

$\tilde{O}\left(\sqrt{\frac{\mathcal{R}_{\max}(\gamma)\mathcal{C}_{\max}(\gamma)}{\tilde{\lambda}_{\min}}}n_{0}+\sqrt{\mathcal{R}_{\gamma}(\mathcal{K})n_{0}}\right),$

where $\mathcal{R}_{\max}(\gamma)$ is the maximum finite effective resistance
$\mathcal{R}_{\gamma}(\mathcal{L})$ of $\gamma$ in any subcomplex
$\mathcal{L}\subset\mathcal{K}$, $\mathcal{C}_{\max}(\gamma)$ is the maximum
finite effective capacitance $\mathcal{C}_{\gamma}(\mathcal{L},\mathcal{L})$
in any subcomplex $\mathcal{K}(x)$, and $\tilde{\lambda}_{\min}$ is the
spectral gap of the normalized up-Laplacian
$\tilde{L}_{d-1}^{up}[\mathcal{K}]$.

###  4.5 Runtime of the Quantum Incremental Algorithm

In the previous section, we saw an implementation of an algorithm for testing
if the boundary of a $d$-simplex was null-homologous. Combined with the
framework of the Incremental Algorithm (Algorithm 1), this allows us to
compute the $d$-Betti number.

See 1.1

###### Proof.

The Incremental Algorithm (Algorithm 1) incrementally adds each $d$ and
$(d+1)$-simplex $\sigma$ to the simplicial complex and checks if the cycle
$\partial\sigma$ is null-homologous. We can use the span-program algorithm of
Theorem 4.10 to check if $\partial\sigma$ is null-homologous. The theorem
follows by using this algorithm for each of the $(n_{d}+n_{d+1})$ $d$\- and
$(d+1)$-simplices. ∎

###  4.6 Comparison with Existing Algorithms.

In this section, we compare our algorithm to existing algorithms for QTDA.
This presentation specifically compares our algorithm to the LGZ algorithm
[Lloyd2016lgz], but most of these ideas also hold for other existing QTDA
algorithms.

##### Input.

Our algorithm makes different assumptions about how the simplicial complex is
stored compared to previous algorithms. We assume we have a list of simplices
in the simplicial complex; this is required for the incremental algorithm as
we must iteratively add the simplices and test if their boundaries are null-
homologous. Compare this to existing quantum algorithms, which assume we have
a way of checking if a simplex is included in the simplicial complex.

Our algorithm assumes we have a list oracle that can return the simplices in
the simplicial complex:

$\mathcal{O}_{list}:\lvert i\rangle\lvert 0\rangle\to\lvert
i\rangle\lvert\sigma_{i}\rangle,$

where $\sigma_{i}$ is the $i$th $d$-simplex of our simplicial complex.

Compare this to the membership oracle used in other QTDA algorithms that can
check whether a simplex is in the simplicial complex:

$\mathcal{O}_{memb}:\lvert\sigma_{i}\rangle\lvert
j\rangle\to\lvert\sigma_{i}\rangle\lvert j\oplus b_{i}\rangle,$

where $b_{i}$ is a bit indicating if $\sigma_{i}\in\mathcal{K}_{d}$.

These oracles come with different trade-offs. The oracle $\mathcal{O}_{memb}$
does not require computing the set of simplices in advanced, while
$\mathcal{O}_{list}$ does. However, algorithms that use the membership oracle
$\mathcal{O}_{memb}$ pay for this in the time it takes to compute a uniform
superposition of the $d$-simplices, a costly operation leading to a factor of
$\zeta_{d}=n_{d}/\binom{n_{0}}{d+1}$ in the runtime. Thus, our algorithm is
better suited for sparse simplicial complexes—complexes where
$n_{d}<<\binom{n}{d+1}$ and where the list of simplices can be computed
efficiently—a family of complexes where existing QTDA algorithms perform
poorly; see the section “Runtime” below for more discussion.

##### Output.

The LGZ algorithm estimates the $d$th Betti number up to an additive factor by
returning a value $\chi_{d}$ such that $\left|\chi_{d}-\frac{\beta_{d}}{\dim
C_{d}(\mathcal{K})}\right|\leq\epsilon$; the problem of computing $\chi_{d}$
has been deemed Betti number estimation. Our algorithm instead returns the
Betti number $\beta_{k}$.

##### Runtime.

To compare our algorithm to existing quantum algorithms, we bound the runtime
of our algorithm with respect to the spectral gap of the combinatorial
Laplacian. Note that while we can bound the runtime of our algorithm by the
inverse of the spectral gap, this bound is not necessarily tight.

######  Corollary 4.11.

Let $\mathcal{K}$ be a simplicial complex with $n_{i}$ $i$-simplices. There is
a quantum algorithm for computing the $d$th Betti number $\beta_{d}$ in time

$\tilde{O}\left(\Lambda_{\min}^{-3/2}n_{0}^{5/2}\cdot(n_{d}+n_{d+1})\right)$

where $\Lambda_{\min}$ is the minimum spectral gap of $L_{d}[\mathcal{L}]$
over all subcomplexes $\mathcal{L}\subset\mathcal{K}$.

###### Proof.

This follows from Theorem 1.1 by applying the bounds of Lemma 4.4, Theorem
4.6, and Lemma 2.5 to bound $\mathcal{R}_{\max}$, $\mathcal{C}_{\max}$, and
$\frac{1}{\tilde{\lambda}_{\min}}$ respectively. The bounds on the effective
resistance of Lemma 4.4 only apply to unit vectors, so one factor of $n_{0}$
is because of the fact that $\|\partial\sigma\|=\sqrt{d}$, so
$\mathcal{R}_{\max}(\partial\sigma)\leq d\Lambda_{\min}^{-1}$. ∎

Compare this to the LGZ algorithm, which runs in time

$O\left(\epsilon^{-2}\lambda_{\min}^{-1}n_{0}^{4}\sqrt{\zeta_{d}^{-1}}\right)$

where $n_{0}$ is the number of vertices, $\epsilon$ is the error term,
$\lambda_{\min}$ is the spectral gap of the combinatorial Laplacian, and
$\zeta_{d}$ is a density term given by

$\zeta_{d}=\frac{n_{d}}{\binom{n_{0}}{d+1}}.$

The density term is the ratio of the number $k$-simplices in the $\mathcal{K}$
to number of $k$-simplices in the complete complex on $n_{0}$ vertices, which
may be exponentially small. For example, when $\mathcal{K}$ is sparse, meaning
that the number of $d$-simplices is polynomial in the number of vertices, the
density may be exponentially small with respect to $d$. Specifically, if
$\zeta_{d}=\Omega\left(n_{0}^{O(1)}/n_{0}^{d+1}\right)=\Omega\left(1/n_{0}^{O(d+1)}\right)$,
then the runtime of LGZ is

$O\left(\epsilon^{-2}\lambda_{\min}^{-1}n_{0}^{O(d+1)}\right).$

Compare this to our algorithm, which in this case has runtime

$\tilde{O}\left(\Lambda_{\min}^{-3/2}n_{0}^{O(1)}\right).$

In this case, our algorithm has a better asymptotic dependence on the size of
the complex as it avoids the factor of $\binom{n_{0}}{d+1}$. This factor of
$\binom{n_{0}}{d+1}$ shows up in many of the alternatives to the LGZ
algorithm, so our algorithm has a more favorable dependence on $n_{0}$
compared to these algorithms as well. Additionally, we note that the term
$\Lambda_{\min}$ in our algorithm and $\lambda_{\min}$ in the LGZ algorithm
are similar but not directly comparable. See the following section.

##### Effective Resistance and Capacitance vs. Spectral Gap.

Our algorithm is parameterized by the maximum effective resistance and
capacitance of all subcomplexes of a simplicial complex and the square root of
the inverse of spectral gap of the simplicial complex, whereas previous QTDA
algorithm are only parameterized by the inverse of the spectral gap of the
simplicial complex. Although for a fixed complex, effective resistance and
capacitance are upper bounded by the inverse of the spectral gap, the fact
that our algorithm is parameterized by the maximum effective resistance and
capacitance over all subcomplexes means that the runtime of our algorithm is
not entirely comparable to the runtime of existing QTDA algorithms. It is
possible are complexes where the effective resistance and capacitance in
subcomplexes are significantly lower than the spectral gap of the entire
complex, and complexes where the effective resistance or capacitance of a
cycle in a subcomplex is larger than the spectral gap of the entire complex.
The complete complex is an example of the second case, as it has the maximal
possible spectral gap of $n_{0}$.

##### Randomized Order for the Incremental Algorithm.

Building on the previous point, while our algorithm is parameterized by the
maximum effective resistance and capacitance in various subcomplexes, our
algorithm can also incrementally add the simplices in any order. This is
potentially beneficial as a simplex may have smaller effective resistance or
capacitance in one order than another. Of course, we likely will not know in
advance whether or not a particular order of the simplices results in less or
greater resistance and capacitance. However, we still may able to use this
fact to our advantage, as we could run our algorithm multiple times with
different orders to gain confidence that our Betti number computations are
accurate, which is not the case with previous QTDA algorithms.

##  5 Bounds on Effective Resistance and Capacitance.

In this section, we provide upper bounds on the resistance and capacitance of
a cycle $\gamma$ in an simplicial complex $\mathcal{K}$. Throughout this
section, all simplicial complexes are unweighted.

Our upper bounds are polynomial in the number of $d$-simplices and the
cardinality of the torsion subgroup of the relative homology groups. In
particular, our bounds on resistance and capacitance are dependent on the
maximum cardinality of the torsion subgroup of the relative homology group
$H_{d-1}(\mathcal{L},\mathcal{L}_{0},\mathbb{Z})$, where
$\mathcal{L}\subset\mathcal{K}$ is a $d$-dimensional subcomplex and
$\mathcal{L}_{0}\subset\mathcal{L}$ is a $(d{-}1)$-dimensional subcomplex. In
the worst case, our upper bounds are exponential.

In Theorem 5.9 we provide an example of a simplicial complex containing a
cycle $\gamma$ whose effective resistance is exponential in the number of
simplices in the complex. It is important to reiterate that our bounds are in
terms of the torsion of the relative homology groups, not the torsion of the
(non-relative) homology groups. The simplicial complex we provide has no
torsion in its homology groups, only torsion in its relative homology groups.

###  5.1 Upper Bounds

Our upper bounds rely on a change of basis on the boundary matrix called the
Smith normal form which reveals information about the torsion subgroup of
$H_{d-1}(\mathcal{K},\mathbb{Z})$. We state the normal form theorem below.

######  Theorem 5.1 (Munkres, Chapter 1 Section 11 [Munkres1984]).

There are bases for $C_{d}(\mathcal{K})$ and $C_{d-1}(\mathcal{K})$ such that
the matrix for the boundary operator $\partial_{d}\colon
C_{d}(\mathcal{K},\mathbb{Z})\rightarrow C_{d-1}(\mathcal{K},\mathbb{Z})$ is
in Smith normal form, i.e.

$\tilde{\partial}_{d}=\begin{bmatrix}D&0\\\ 0&0\end{bmatrix}$

where $D$ is a diagonal matrix with positive integer entries
$d_{1},\dots,d_{m}$ such that each $d_{i}$ divides $d_{i+1}$ and each $0$ is a
zero matrix of appropriate dimensionality. The normal form of $\partial_{d}$
satisfies the following properties:

  1. 1.

The entries $d_{1},\dots,d_{m}$ correspond to the torsion coefficients of
$H_{d-1}(\mathcal{K},\mathbb{Z})\cong\mathbb{Z}^{\beta_{d}}\oplus\mathbb{Z}_{d_{1}}\oplus\dots\oplus\mathbb{Z}_{d_{m}}$
$($where $\mathbb{Z}_{1}=0)$,

  2. 2.

The number of zero columns is equal to the dimension of $\ker(\partial_{d})$.

Moreover, the boundary matrix $\partial$ in the standard basis can be
transformed to $\tilde{\partial}$ by elementary row and column operations. If
$\partial$ is square, these operations multiply $\det\partial$ by $\pm 1$.

Using Theorem 5.1, we obtain an upper bound on the determinants of the square
submatrices of the boundary matrix $\partial_{d}[\mathcal{K}]$ in terms of the
relative homology groups of $\mathcal{K}$. Let $\mathcal{L}$ be
$d$-dimensional subcomplex of $\mathcal{K}$, and let $\mathcal{L}_{0}$ be a
$(d{-}1)$-dimensional subcomplex of $\mathcal{K}$. The relative boundary
matrix $\partial_{d}[\mathcal{L},\mathcal{L}_{0}]$ is the submatrix of
$\partial_{d}$ obtained by including the columns of the $d$-simplices in
$\mathcal{L}$ and excluding the rows of the $(d{-}1)$-simplices in
$\mathcal{L}_{0}$. With the relative boundary matrices, one can define the
relative homology groups as
$H_{d}(\mathcal{L},\mathcal{L}_{0},\mathbb{Z})=\ker\partial_{d}[\mathcal{L},\mathcal{L}_{0}]/\operatorname{im}\partial_{d+1}[\mathcal{L},\mathcal{L}_{0}]$.
More information on the relative boundary matrix can be found in [Dey2011]. We
denote the cardinality of the torsion subgroup of the relative homology group
$H_{d-1}(\mathcal{L},\mathcal{L}_{0},\mathbb{Z})$ by
$\mathcal{T}(\mathcal{L},\mathcal{L}_{0})$. Similarly, we denote the maximum
$\mathcal{T}(\mathcal{L},\mathcal{L}_{0})$ over all relative homology groups
as $\mathcal{T}_{\max}(\mathcal{K})$.

######  Lemma 5.2.

Let $\partial_{d}[\mathcal{L},\mathcal{L}_{0}]$ be a $k\times k$ square
submatrix of $\partial_{d}$ constructed by including columns for the
$d$-simplices in $\mathcal{L}$ and excluding rows for the $(d-1)$-simplices in
$\mathcal{L}_{0}$. The magnitude of the determinant of
$\partial_{d}[\mathcal{L},\mathcal{L}_{0}]$ is bounded above by the
cardinality of the torsion subgroup of
$H_{d-1}(\mathcal{L},\mathcal{L}_{0},\mathbb{Z})$, i.e

$|\det\left(\partial_{d}[\mathcal{L},\mathcal{L}_{0}]\right)|\leq\mathcal{T}(\mathcal{L},\mathcal{L}_{0}).$

###### Proof.

Without loss of generality, we assume that
$\det(\partial_{d}[\mathcal{L},\mathcal{L}_{0}])\neq 0$; if
$\det(\partial_{d}[\mathcal{L},\mathcal{L}_{0}])=0$, the bound is trivial.
Since $\partial_{d}[\mathcal{L},\mathcal{L}_{0}]$ is a non-singular square
matrix, its normal form $\tilde{\partial}_{d}[\mathcal{L},\mathcal{L}_{0}]$ is
a diagonal matrix $D=\operatorname{diag}(d_{1},\dots,d_{k})$. The determinant
is equal to $\pm\prod_{i=1}^{k}d_{i}$ and by Theorem 5.1 the torsion subgroup
of $H_{d-1}(\mathcal{L},\mathcal{L}_{0})$ is
$\mathbb{Z}_{d_{1}}\oplus\dots\oplus\mathbb{Z}_{d_{k}}$ which has cardinality
$\mathcal{T}(\mathcal{L},\mathcal{L}_{0})=\prod_{i=1}^{k}d_{i}$. ∎

####  5.1.1 Upper Bounds on Effective Resistance

We are now ready to upper bound the effective resistance of a cycle in a
simplicial complex.

######  Theorem 5.3.

Let $\mathcal{K}$ be a $d$-dimensional simplicial complex and $\gamma$ a unit-
length null-homologous $(d{-}1)$-cycle in $\mathcal{K}$. Let
$n=\min\\{n_{d-1},n_{d}\\}$. The effective resistance of $\gamma$ is bounded
above by $\mathcal{R}_{\gamma}(\mathcal{K})\in
O\left(n^{2}\cdot\mathcal{T}_{\max}(\mathcal{K})^{2}\right)$.

###### Proof.

First, we remove $d$-simplices from $\mathcal{K}$ to create a new complex
$\mathcal{L}$ such that $\ker(\partial_{d}[\mathcal{L}])=0$ and
$\operatorname{im}\partial_{d}[\mathcal{K}]=\operatorname{im}\partial_{d}[\mathcal{L}]$.
Theorem B.3 proves that removing $d$-simplices only increases the effective
resistance, so
$\mathcal{R}_{\gamma}(\mathcal{K})\leq\mathcal{R}_{\gamma}(\mathcal{L})$. As
$\ker(\partial_{d}[\mathcal{L}])=0$, there is a unique unit $\gamma$-flow
$f\in C_{d-1}(\mathcal{L})$ which implies
$\mathcal{R}_{\gamma}(\mathcal{L})=\|f\|^{2}$. Let $n\leq n_{d}$ denote the
number of $d$-simplices in $\mathcal{L}$.

The matrix $\partial_{d}[\mathcal{L}]$ has full column rank, so we can find a
non-singular $n\times n$ square submatrix of $\partial_{d}[\mathcal{L}]$; call
this submatrix $B$. Let $\mathcal{L}_{0}$ be the $(d-1)$-dimensional
subcomplex that contains the $(d-1)$-simplices corresponding to rows excluded
from $B$; $B$ is the relative boundary matrix
$\partial_{d}[\mathcal{L},\mathcal{L}_{0}]$. We have that $Bf=c$, where $c$ is
the restriction of $\gamma$ to the rows of $B$. Observe that
$\|c\|\leq\|\gamma\|=1$

We will apply Cramer’s rule to upper bound the size of $f$. By Cramer’s rule
we have the equality

$f(\sigma)=\frac{\det(B_{\sigma,c})}{\det(B)}$

where $B_{\sigma,c}$ is the matrix obtained by replacing the column of $B$
indexed by $\sigma$ with the vector $c$. Since $\det(B)$ is integral,
$|\det(B)|\geq 1$, so we drop the denominator and focus on the inequality
$|f(\sigma)|\leq|\det(B_{\sigma,c})|$. We bound $|\det(B_{\sigma,c})|$ by its
cofactor expansion,

$\displaystyle|\det(B_{\sigma,c})|$
$\displaystyle=\left|\sum_{i=1}^{n_{d}}(-1)^{i}\cdot
c_{i}\cdot\det(B_{\sigma,c}^{c,i})\right|$
$\displaystyle\leq\sum_{i=1}^{n_{d}}|c_{i}|\cdot\mathcal{T}_{\max}(\mathcal{K})$
$\displaystyle=\|c\|_{1}\cdot\mathcal{T}_{\max}(\mathcal{K})$
$\displaystyle=O\left(\sqrt{n}\cdot\mathcal{T}_{\max}(\mathcal{K})\right)$

where $B_{\sigma,c}^{c,i}$ denotes the submatrix obtained by removing the
column $c$ and removing the $i$th row and $c_{i}$ denotes the $i$th component
of $c$. The first inequality comes from Lemma 5.2, as $B_{\sigma,c}^{c,i}$ is
the relative boundary matrix
$\partial_{d}[\mathcal{L}\setminus\\{\sigma\\},\mathcal{L}_{0}\cup\sigma_{i}]$,
where $\sigma_{i}$ is the $(d{-}1)$-simplex corresponding to the $i$th row of
$B$. The factor of $\sqrt{n}$ comes from the fact that
$\|c\|_{1}\leq\sqrt{n}\|c\|_{2}$ and $\|c\|_{2}\leq 1$. Finally, we compute
the flow energy of $f$ as

$\displaystyle\mathsf{J}(f)$
$\displaystyle=\sum_{\sigma\in\mathcal{L}_{d}}f(\sigma)^{2}$
$\displaystyle\leq\sum_{i=1}^{n}n\cdot\mathcal{T}_{\max}(\mathcal{K})^{2}$
$\displaystyle=O\left(n^{2}\cdot\mathcal{T}_{\max}(\mathcal{K})^{2}\right).$

The effective resistance of $\gamma$ is the flow energy of $f$, so the result
follows. ∎

If $\mathcal{L}\subset\mathcal{K}$, then the boundary matrix
$\partial_{d}[\mathcal{L}]$ is a submatrix of $\partial_{d}[\mathcal{K}]$. In
particular,
$\mathcal{T}_{\max}(\mathcal{L})\leq\mathcal{T}_{\max}(\mathcal{K})$.
Therefore, the proof of Theorem 5.3 gives an upper bound on the effective
resistance for any subcomplex $\mathcal{L}\subset\mathcal{K}$.

######  Corollary 5.4.

Let $\mathcal{L}\subset\mathcal{K}$ be a $d$-dimensional simplicial complex
and $\gamma$ a null-homologous $(d{-}1)$-cycle in $\mathcal{L}$. Let
$n=\min\\{n_{d-1}[\mathcal{L}],n_{d}[\mathcal{L}]\\}$. The effective
resistance of $\gamma$ in $\mathcal{L}$ is bounded above by
$\mathcal{R}_{\gamma}(\mathcal{L})=O\left(n^{2}\cdot\mathcal{T}_{\max}(\mathcal{K})^{2}\right)$.

In Section 5.1.3, we give an upper bound on relative torsion, which implies an
upper bound on the effective resistance purely in terms of the size of the
complex.

####  5.1.2 Upper Bounds on Capacitance.

We now provide an upper bound for the effective capacitance of a cycle. While
upper bounds on the effective resistance only depended on the norm of the
cycle, upper bounds on the capacitance of the cycle are not. Therefore, we
consider the special case where $\gamma$ is the boundary of a $d$-simplex.
This is a natural assumption as these are exactly the type of cycles
considered in the incremental algorithm for computing Betti numbers (Algorithm
1). While we only prove this special case, we note that our proof could be
adapted to bound the effective capacitance of a cycle whose entries have
constant upper and lower bounds.

######  Theorem 5.5.

Let $\mathcal{L}\subset\mathcal{K}$ be $d$-dimensional simplicial complexes.
Let $\gamma\in C_{d-1}(\mathcal{L})$ be a $(d-1)$-cycle that is null-
homologous in $\mathcal{K}$ but not in $\mathcal{L}$. Let
$n=\min\\{n_{d-1},n_{d}\\}$. Assume that $\gamma=\partial\sigma$ for a
$d$-simplex $\sigma\notin\mathcal{L}$. The effective capacitance of $\gamma$
in $\mathcal{K}$ is bounded above by
$\mathcal{C}_{\gamma}(\mathcal{L},\mathcal{K})\in O\left(n\cdot
n_{0}\cdot\mathcal{T}_{\max}(\mathcal{K})^{2}\right)$.

###### Proof.

Let $p$ be a $\gamma$-potential. We upper bound the potential energy of $p$.
By definition, $\delta[\mathcal{L}]p=0$ and $\gamma^{T}p=1$. We can express
these constraints as the linear system

$\begin{bmatrix}\phantom{0}\\\ \delta[\mathcal{L}]\\\ \phantom{\vdots}\\\
\gamma^{T}\end{bmatrix}p=\begin{bmatrix}0\\\
0\vphantom{\delta[\mathcal{L}]}\\\ \vdots\\\ 1\end{bmatrix}$

We first remove linearly-dependent columns from this linear system until this
system has full column rank. Columns of the matrix are indexed by $(d{-}1)$
simplices of $\mathcal{L}$, and rows are indexed by $d$-simplices of
$\mathcal{L}$. Removing columns from $\delta[\mathcal{L}]$ changes it to the
relative coboundary matrix $\delta[\mathcal{L},\mathcal{L}_{0}]$ where
$\mathcal{L}_{0}$ is the $(d-1)$-subcomplex corresponding to the columns that
were removed. Removing linearly-dependent columns does not change the image of
the system of equation, so there is still a solution $r$, i.e.

$\begin{bmatrix}\phantom{0}\\\ \delta[\mathcal{L},\mathcal{L}_{0}]\\\
\phantom{\vdots}\\\ c^{T}\end{bmatrix}r=\begin{bmatrix}0\\\
0\vphantom{\delta[\mathcal{L}]}\\\ \vdots\\\ 1\end{bmatrix}$

where $c$ is the subvector of $\gamma$ after removing the columns. The vector
$r$ is not a $\gamma$-potential as it is a vector in
$C_{d-1}(\mathcal{L},\mathcal{L}_{0})$, not $C_{d-1}(\mathcal{L})$. However,
we can extend $r$ to be a $\gamma$-potential by adding zeros in the entries
indexed by $\mathcal{L}_{0}$. Adding zero-valued entries preserves the length
of $r$.

We now want to remove rows from this matrix so that it has full row rank.
Topologically, removing rows corresponds to removing $d$-simplices from the
complex $\mathcal{L}$ to create a new complex $\mathcal{L}_{1}$. Note that we
must always include the row $c$ to have full row rank; otherwise, $r$ would be
a non-zero vector in the kernel of this system, meaning the system does not
have full rank. Removing these rows gives the linear system

$\begin{bmatrix}\phantom{0}\\\ \delta[\mathcal{L}_{1},\mathcal{L}_{0}]\\\
\phantom{\vdots}\\\ c\end{bmatrix}r=\begin{bmatrix}0\\\
0\vphantom{\delta[\mathcal{L}]}\\\ \vdots\\\ 1\end{bmatrix}.$

Let
$C=\begin{bmatrix}\delta[\mathcal{L}_{1},\mathcal{L}_{0}]^{T}&c^{T}\end{bmatrix}^{T}$
and $b=\begin{bmatrix}0&0&\cdots&1\end{bmatrix}^{T}$. Note that $C$ is an
square matrix of size (say) $m\times m$, where $m\leq n+1$.

We use Cramer’s rule to bound the size of $\|r\|$. By Cramer’s rule, $r_{i}$,
the $i$th entry of $r$, is

$r_{i}=\frac{\det(C_{i,b})}{\det(C)}.$

where $C_{i,b}$ is the matrix obtained by replacing the $i$th column with $b$.

We first lower bound $|\det{(C)}|$. As $C$ is a full-rank integral matrix,
then $|\det{(C)}|\geq 1$. We now upper bound $|\det(C_{i,b})|$. We calculate
$\det(C_{i,b})$ with the cofactor expansion on the column replaced by $b$. As
$b$ has 1 in its last entry and 0s elsewhere, the cofactor expansion gives
$\det(C_{i,b})=\pm 1\cdot\det(C_{i,b}^{i,c})$ where $C_{i,b}^{i,c}$ is the
matrix where we dropped the $i$th column and the row $c$ from $C_{i,b}$. The
matrix $C_{i,b}^{i,c}$ is a square submatrix of $\delta[\mathcal{K}]$, so we
can bound $|\det(C_{i,b})|\leq\mathcal{T}_{\max}(\mathcal{K})$. Thus,
$r_{i}=\det(C_{i,b})/\det(C)\leq\mathcal{T}_{\max}(\mathcal{K})$ and

$\displaystyle\|r\|$ $\displaystyle=\sqrt{\sum_{i=1}^{m}r_{i}^{2}}$
$\displaystyle\leq\sqrt{m\cdot\mathcal{T}_{\max}(\mathcal{K})^{2}}$
$\displaystyle\leq\sqrt{n\cdot\mathcal{T}_{\max}(\mathcal{K})^{2}}$
$\displaystyle=\sqrt{n}\cdot\mathcal{T}_{\max}(\mathcal{K})$

The potential energy of $r$ is $\|\delta[\mathcal{K}]r\|^{2}$. We can use
Lemma 4.5 to obtain the bound $\|\delta[\mathcal{K}]r\|^{2}=O\left(n\cdot
n_{0}\cdot\mathcal{T}_{\max}(\mathcal{K})^{2}\right)$. ∎

####  5.1.3 Upper Bound on Relative Torsion.

To conclude this section, we provide an upper bound on
$\mathcal{T}_{\max}(\mathcal{K})$.

######  Lemma 5.6.

Let $\mathcal{K}$ be a simplicial complex. Let $n=\min\\{n_{d-1},n_{d}\\}$.
Then the maximum rank of any $(d-1)$-dimensional relative torsion group of $K$
is $\mathcal{T}_{\max}(\mathcal{K})\in O((\sqrt{d+1})^{n})$.

###### Proof.

By the proof of Lemma 5.2, the quantity $\mathcal{T}_{\max}(\mathcal{K})$ is
the absolute value of the determinant of some submatrix of $\partial_{d}$. We
therefore bound the determinant of such a submatrix. We prove this bound using
Hadamard’s Inequality: the determinant of an $m\times m$ matrix $B$ is upper-
bounded by the product of the norms of its columns.

Consider a square, $m\times m$ submatrix $B$ of $\partial_{d}$. We know that
$m\leq n$. Moreover, any column of $B$ has norm bounded above by $\sqrt{d+1}$.
This bound follows from the fact that each column of $\partial_{d}$ has norm
exactly $\sqrt{d+1}$; each column has $d+1$ nonzero entries, each of which is
$\pm 1$. The bound of the lemma follows by Hadamard’s Inequality. ∎

Lemma 5.6 immediately implies the corollaries to Theorem 5.3 and Theorem 5.5.

######  Corollary 5.7.

Let $\mathcal{K}$ be a $d$-dimensional simplicial complex and $\gamma$ a unit-
length null-homologous $(d{-}1)$-cycle in $\mathcal{K}$. Let
$n=\min\\{n_{d-1},n_{d}\\}$. The effective resistance of $\gamma$ is bounded
above by $\mathcal{R}_{\gamma}(\mathcal{K})\in O\left(n^{2}(d+1)^{n}\right)$.

######  Corollary 5.8.

Let $\mathcal{L}\subset\mathcal{K}$ be $d$-dimensional simplicial complexes.
Let $\gamma\in C_{d-1}(\mathcal{L})$ be a $(d-1)$-cycle that is null-
homologous in $\mathcal{K}$ but not in $\mathcal{L}$. Let
$n=\min\\{n_{d-1},n_{d}\\}$. Assume that $\gamma=\partial\sigma$ for a
$d$-simplex $\sigma\notin\mathcal{L}_{d}$. The effective capacitance of
$\gamma$ in $\mathcal{K}$ is bounded above by
$\mathcal{C}_{\gamma}(\mathcal{L},\mathcal{K})\in O\left(n\cdot
n_{0}\cdot(d+1)^{n}\right)$.

###  5.2 Lower Bounds.

####  5.2.1 Lower Bounds on Effective Resistance

At the end of the previous section, we gave an exponential upper bound on the
effective resistance of a $(d-1)$-cycle in a simplicial complex (Corollary
5.7). In this section, we describe a $d$-dimensional simplicial complex
$\mathcal{B}_{d}^{n}$ with a $(d-1)$-cycle $\gamma$ with exponentially-large
effective resistance with respect to the size of the complex.

######  Theorem 5.9.

Let $d$, $n$ be positive integers. There is a constant $c_{d}\geq 1$ that
depends only on $d$ and a $d$-dimensional simplicial complex
$\mathcal{B}_{d}^{n}$ with $n_{d}\in\Theta((d+1)^{3}n)$ $d$-simplices and a
unit-length null-homologous cycle $\gamma\in C_{d-1}(\mathcal{B}_{d}^{n})$
such that $\mathcal{R}_{\gamma}(\mathcal{B}_{d}^{n})\in\Theta(c_{d}^{n_{d}})$.

##### The building block.

Figure 3: Left: Stellar subdivision of a triangle. Middle and Right: Top and
bottom view of the stellar prism of a triangle with the tetrahedra pushed
apart.

Our simplicial complex will be obtained by gluing together multiple instances
of the same “building block” $B_{d}$. A formal description of $B_{d}$ is given
in Appendix E; here, we give an intuitive description of the complex. Let
$\Delta^{d}$ denote the closure of the $d$-simplex
$\sigma=\\{v_{0},\ldots,v_{d}\\}$, and let $\partial\Delta^{d}$ denote the
$(d-1)$-dimensional simplicial complex $\Delta^{d}\setminus\\{\sigma\\}$. Our
construction starts with a triangulation of the space
$\partial\Delta^{d}\times[0,1]$ that we call the stellar prism. The “bottom
copy” $\partial\Delta^{d}\times\\{0\\}$ is triangulated like the original
complex $\partial\Delta^{d}$, and the “top copy”
$\partial\Delta^{d}\times\\{1\\}$ is triangulated with the stellar
subdivision, the subdivision that adds a vertex to the center of each
$(d-1)$-simplex. See Figure 3. The relevant property of this triangulation is
that the bottom copy has $d+1$ $(d-1)$-simplices, and the top copy has
$d\cdot(d+1)$ $(d-1)$-simplices. The building block $B_{d}$ is obtained from
this triangulation by identifying the vertex in the center of each
$(d-1)$-simplex $\tau\times\\{1\\}$ with the unique vertex in
$\sigma\times\\{1\\}\setminus\tau\times\\{1\\}$, the unique vertex in the
_set_ $\sigma\times\\{1\\}$ that is not a vertex of the simplex
$\tau\times\\{1\\}$. See Figure 4.

When we identify the vertices, each $(d-1)$-simplex in the top of the stellar
prism is replaced by one of the $(d-1)$ faces of $\sigma\times\\{1\\}$.
Moreover, this is replacement is $d$-to-1, meaning each face of
$\sigma\times\\{1\\}$ replaces a $(d-1)$-simplex exactly $d$ times, or
informally, each $(d-1)$-simplex “appears $d$ times” in the top copy of
$B_{d}$. Of course, this is not literally true, as a simplicial complex can
only contain a single copy of each simplex. However, something to this effect
is true. Namely, there is a $d$-chain $f\in C_{d}(B_{d})$ whose boundary
assigns value $\pm 1$ to each $(d-1)$-simplex in the bottom copy and value
$\pm d$ to each $(d-1)$-simplex in the top copy. The key properties of the
building block $B_{d}$ are summarized in the following lemma.

######  Lemma 5.10.

Let $\sigma=\\{v_{0},\ldots,v_{d}\\}$ be a set. There is a $d$-dimensional
simplicial complex $B_{d}$ with vertices $\sigma\times\\{0,1\\}$ such that

  1. 1.

$B_{d}$ has $\Theta((d+1)^{3})$ $d$-simplices.

  2. 2.

there is a $d$-chain $f\in C_{d}(B_{d})$ such that

    1. (i)

$\partial f=\partial(\sigma\times\\{0\\})+d\cdot\partial(\sigma\times\\{1\\})$

    2. (ii)

$\|f\|^{2}\in\Omega((d+1)^{3})$

Note that neither of the simplices $\sigma\times\\{0\\}$ or
$\sigma\times\\{1\\}$ are in $B_{d}$; however, all of their faces are in the
complex, so the boundary of these simplices are well-defined.

##### The total complex.

Figure 4: The complex $\mathcal{B}_{2}^{3}$. Recall that the vertices of
$\mathcal{B}_{2}^{3}$ are of the form $(v_{i},j)$ for $0\leq i\leq 2$ and
$0\leq j\leq 3$; colors in the figure denote the second coordinate of the
vertices. Vertices with the same label are identified.

The complex $\mathcal{B}_{d}^{n}$ is obtained by gluing together $n$ copies of
$B_{d}$. We describe this gluing inductively on $n$. The vertices of
$\mathcal{B}_{d}^{n}$ are $\sigma\times\\{0,\ldots,n\\}$. The base case
$\mathcal{B}_{d}^{0}$ is the complete complex on the vertices
$\sigma\times\\{0\\}$. Inductively, the complex $\mathcal{B}_{d}^{n}$ is
obtained from $\mathcal{B}_{d}^{n-1}$ by identifying the vertices
$\sigma\times\\{n-1\\}$ of $\mathcal{B}_{d}^{n-1}$ with the vertices
$\sigma\times\\{1\\}$ of a copy of $B_{d}$. We will denote this copy of
$B_{d}$ as $B_{d}^{n}$ and the vertices $\sigma\times\\{0\\}$ of $B^{n}_{d}$
as $\sigma\times\\{n\\}$. See Figure 4.

The key property of $\mathcal{B}_{d}^{n}$ is that is has an exponentially-
large chain with constant-sized boundary.

######  Lemma 5.11.

Let $d\geq 1$ and $n\geq 1$. There is a $d$-chain $y_{n}\in
C_{d}(\mathcal{B}_{d}^{n})$ such that

  1. 1.

$\|y_{n}\|^{2}\in\Omega(d^{2n}(d+1))$

  2. 2.

$\|\partial y_{n}\|^{2}=d+1$

###### Proof.

We construct this chain by induction on $n$. The chain $y_{n}$ will have
$\partial y_{n}=\partial(\sigma\times\\{n\\})$. For the base case $n=0$, the
chain $y_{0}=\sigma\times\\{0\\}$ clearly has this property.

For the inductive case, recall from Lemma 5.10 that there is a $d$-chain $f\in
C_{d}(B_{d})$ such that $\partial
f=\partial(\sigma\times\\{0\\})+d\cdot\partial(\sigma\times\\{1\\})$. Let
$f_{n}$ denote this chain in $B_{d}^{n}$. We define the chain
$y_{n}:=f_{n}-d\cdot y_{n-1}$. We now verify that $y_{n}$ has boundary
$\partial(\sigma\times\\{n\\})$.

$\displaystyle\partial y_{n}=$ $\displaystyle\partial f_{n}-d\cdot\partial
y_{n-1}$ $\displaystyle=$
$\displaystyle\partial(\sigma\times\\{n\\})+d\cdot\partial(\sigma\times\\{n-1\\})-d\cdot\partial(\sigma\times\\{n-1\\}$
$\displaystyle=$ $\displaystyle\partial(\sigma\times\\{n\\})$

It is clear that $\|\partial y_{n}\|^{2}=d+1$, so we just need to lower bound
$\|y_{n}\|^{2}$. We prove that $\|y_{n}\|^{2}\in\Omega(d^{2n}(d+1))$ by
induction. For the base case of $n=1$, we know that
$\|y_{1}\|^{2}\in\Omega((d+1)^{3})$ by Lemma 5.10. For the inductive case, we
can see that $f_{n}\perp y_{n-1}$ as these chains are supported on different
sets of simplices. Therefore,
$\|y_{n}\|^{2}=\|f_{n}\|^{2}+d^{2}\cdot\|y_{n-1}\|\in\Omega(d^{2n}(d+1))$. ∎

Lemma 5.11 shows that $\mathcal{B}_{d}^{n}$ has an exponentially-large
$d$-chain $f$ with constant-sized boundary. If we can show that
$\ker\partial_{d}=0$, this will prove that $\partial f$ has exponentially-
large effective resistance, as $f$ will be the only $d$-chain with boundary
$\partial f$.

######  Corollary 5.12.

The kernel of the boundary matrix $\partial_{d}[\mathcal{B}_{d}^{n}]$ is
trivial, i.e. $\ker\partial_{d}[\mathcal{B}_{d}^{n}]=0$.

###### Proof.

Lemma F.3 in Appendix F shows that $\mathcal{B}_{d}^{n}$ collapses to a
$(d-1)$-dimensional subcomplex; call this subcomplex $L$. This implies that
$\mathcal{B}_{d}^{n}$ is homotopy equivalent to $L$, so in particular, the
$d$-dimensional homology $H_{d}(\mathcal{B}_{d}^{n})=0$. As
$\mathcal{B}_{d}^{n}$ is $d$-dimensional, then
$\operatorname{im}\partial_{d+1}[\mathcal{B}_{d}^{n}]=0$, so the only way that
$H_{d}(\mathcal{B}_{d}^{n})$ can equal 0 is if
$\ker\partial_{d}[\mathcal{B}_{d}^{n}]=0$. ∎

###### Proof of Theorem 5.9.

Our cycle is the normalized cycle $\gamma=\partial y_{n}/\|\partial y_{n}\|$
where $y_{n}$ is the $d$-chain from Lemma 5.11. We know that
$\|y_{n}\|^{2}/\|\partial y_{n}\|^{2}\in\Omega(d^{2n})$. Moreover, we know
that $\ker\partial_{d}=0$ by Corollary 5.12. Therefore, we conclude that
effective resistance
$\mathcal{R}_{\gamma}(\mathcal{B}_{d}^{n})\in\Theta(d^{2n})$.

Now we need to restate this bound in terms of the number of $d$-simplices of
$\mathcal{B}_{d}^{n}$. Each copy of $B_{d}$ has $\Theta((d+1)^{3})$
$d$-simplices. Therefore, the entire complex $\mathcal{B}_{d}^{n}$ has
$n_{d}=\Theta(n\cdot(d+1)^{3})$ $d$-simplices. If we substitute $n_{d}$ into
our bound, we find that the effective resistance is bound below by
$O((d+1)^{2n_{d}/c\cdot(d+1)^{3}})$ for some constant $c$. Therefore, the
constant in the theorem statement is $c_{d}=(d+1)^{2/c\cdot(d+1)^{3}}$. ∎

##### Related Work.

Variants of this construction are sometimes called the Iterated Mapping
Cylinder and have been used as a worst-case construction for other topological
properties like torsion [Newman2018], homotopy [Filakovský2018], or
embeddability [brehm1992linear, Freedman2014]. However, ours is the first work
showing these complexes have a cycle with exponentially-large effective
resistance (or exponentially-small spectral gap, as we will see later.) We
were specifically inspired by the work of Newman [Newman2018].

However, our construction is more efficient than previous constructions of the
Iterated Mapping Cylinder in terms of the number of $d$-simplices; this is why
we dedicate several pages in the appendix to this construction. As an example,
the building block in Newman’s construction is the iterated suspension of the
Möbius band, and the number of $d$-simplices in the suspension grows
exponentially with the dimension $d$. Comparatively, the number of
$d$-simplices in our building block only grows polynomially with the
dimension. Additionally, our construction has a cycle with $\pm 1$
coefficients that is homologous to a cycle with $\pm d$ coefficients; in
contrast, previous works have a cycle with $\pm 1$ coefficients that is
homologous to a cycle with $\pm 2$ coefficients. Both of these properties
result in a larger constant $c_{d}$ in Theorem 5.9. It is an open question if
there is a simplicial complex with a cycle whose effective resistance exactly
matches the constant of the lower bound, i.e. $c_{d}\in\Theta(d+1)$.

####  5.2.2 Lower Bounds on Capacitance.

In this section, we describe a pair of nested simplicial complexes that have a
cycle with exponentially large effective capacitance. This complex will be
built from the same building block as the complex for lower bounding effective
resistance, but the simplicial complex will built by gluing together the
building blocks in slightly different ways.

Recall that the building block is a simplicial complex $B_{d}$ with vertices
$\sigma\times\\{0,1\\}$, where $\sigma=\\{v_{0},\ldots,v_{d}\\}$ is a
$d$-simplex. For a natural number $n$, we recursively construct the simplicial
complex $\mathcal{Q}_{d}^{n}$. The simplicial complex $\mathcal{Q}_{d}^{n}$ is
obtained by gluing together $n$ copies of $B_{d}$. The vertices of
$\mathcal{Q}_{d}^{n}$ will be denoted $\sigma\times\\{0,\ldots,n\\}$. The base
case $\mathcal{Q}_{d}^{n}$ is the complete complex on the vertices
$\sigma\times\\{0\\}$. Inductively, the complex $\mathcal{Q}_{d}^{n}$ is
obtained from $\mathcal{Q}_{d}^{n-1}$ by identifying the vertices
$\sigma\times\\{n-1\\}$ of $\mathcal{Q}_{d}^{n-1}$ with the vertices
$\sigma\times\\{0\\}$ of a copy of $B_{d}$.999 It is worth comparing
$\mathcal{Q}_{d}^{n}$ to the simplicial complex $\mathcal{B}_{d}^{n}$ from the
bounds on effective resistance. Both complexes are obtained by identifying
vertices of copies of the building block $B_{d}$, but the identifications are
made in different ways. When a building block is added to
$\mathcal{B}_{d}^{i}$ to form $\mathcal{B}_{d}^{i+1}$, its “top”
$\sigma\times\\{1\\}$ is identified with $\sigma\times\\{i\\}$. When a
building block is added to $\mathcal{Q}_{d}^{i}$ to form
$\mathcal{Q}_{d}^{i+1}$, its “bottom” $\sigma\times\\{0\\}$ is identified with
$\sigma\times\\{i\\}$. It is easiest to see the difference between
$\mathcal{B}_{d}^{n}$ and $\mathcal{Q}_{d}^{n}$ by considering the cycle
$\partial(\sigma\times\\{n\\})$ in both complexes. The unique $d$-chain $f\in
C_{d}(\mathcal{B}_{d}^{n})$ with boundary $\partial(\sigma\times\\{n\\})$
assigns exponentially-large coefficients to some $d$-simplices. In contrast,
the unique $d$-chain $f\in C_{d}(\mathcal{Q}_{d}^{n})$ assigns exponentially-
small coefficients to some $d$-simplices. (This is a corollary to the proof of
Lemma 5.13.) We will denote this copy of $B_{d}$ as $B_{d}^{n}$ and the
vertices $\sigma\times\\{1\\}$ as $\sigma\times\\{n\\}$. The simplicial
complex $\mathcal{P}_{d}^{n}$ is defined $Q_{d}^{n-1}$ minus the simplex
$\sigma\times\\{0\\}$.

We will prove that the cycle $\gamma=\partial(\sigma\times\\{n\\}$ has
exponentially large capacitance in
$\mathcal{P}_{d}^{n}\subset\mathcal{Q}_{d}^{n}$. In order for $\gamma$ to have
finite capacitance, the cycle $\gamma$ must be null-homologous in
$\mathcal{Q}_{d}^{n}$ but not null-homologous in $\mathcal{P}_{d}^{n}$. We
prove this in the following lemma.

######  Lemma 5.13.

Let $\mathcal{P}_{d}^{n}$ and $\mathcal{Q}_{d}^{n}$ as described above.
Consider the chain $\partial(\sigma\times\\{n\\})\in
C_{d}(\mathcal{P}_{d}^{n})$.

  1. 1.

The $(d-1)$-chain
$\partial(\sigma\times\\{n\\})+(-1)^{n-1}\frac{1}{d^{n}}\partial(\sigma\times\\{0\\})$
is null-homologous in $\mathcal{P}_{d}^{n}$.

  2. 2.

The $(d-1)$-chain $\partial(\sigma\times\\{n\\})$ is null-homologous in
$Q_{d}^{n}$.

  3. 3.

The $(d-1)$-chain $\partial(\sigma\times\\{n\\})$ is not null-homologous in
$P_{d}^{n}$.

###### Proof.

Proof of Part (1) We will prove that the cycle
$\partial(\sigma\times\\{i\\})+\frac{1}{d^{i}}\partial(\sigma\times\\{0\\})$
is null-homologous in $Q_{d}^{i}$ by induction on $i$. Specifically, we will
find a $d$-chain $y_{i}$ such that $\partial
y_{i}=\partial(\sigma\times\\{i\\})+\frac{1}{d^{i}}\partial(\sigma\times\\{0\\})$.
For each copy of the building block $B_{d}^{i}$, let $f_{i}\in
C_{d}(B_{d}^{i})$ be the $d$-chain guaranteed by Lemma 5.10 such that
$\partial
f_{i}=\partial(\sigma\times\\{i-1\\})+d\cdot\partial(\sigma\times\\{i\\})$.
For the base case of $i=1$, the $d$-chain $y_{1}=\frac{1}{d}f_{1}$.
Inductively, we define the chain $y_{i}=\frac{1}{d}f_{i}-\frac{1}{d}y_{i-1}$.
We can verify that $y_{i}$ has the claimed boundary as

$\displaystyle\partial y_{i}=$ $\displaystyle\frac{1}{d}\partial
f_{i}-\frac{1}{d}\partial y_{i-1}$ $\displaystyle=$
$\displaystyle\partial(\sigma\times\\{i\\})+\frac{1}{d}\partial(\sigma\times\\{i-1\\})-\frac{1}{d}\partial(\sigma\times\\{i-1\\})+(-1)^{i-1}\frac{1}{d^{i}}\partial(\sigma\times\\{0\\})$
$\displaystyle=$
$\displaystyle\partial(\sigma\times\\{i\\})+(-1)^{i-1}\frac{1}{d^{i}}\partial(\sigma\times\\{0\\})$

Proof of Part (2) As the simplex
$(\sigma\times\\{0\\})\in\mathcal{Q}_{d}^{n}$, then the chain
$y_{n}+(-1)^{n}\frac{1}{d^{n}}\cdot(\sigma\times\\{0\\})$ obviously has
boundary $\partial(\sigma\times\\{n\\})$.

Proof of Part (3) To prove that $\partial(\sigma\times\\{n\\})$ is not null-
homologous in $\mathcal{P}_{d}^{n}$, we will use two lemmas we prove in the
appendix. Lemma F.4 shows that $\mathcal{P}_{d}^{n}$ collapses to a
$(d-1)$-dimensional subcomplex—call it $L$—containing the support of
$\partial(\sigma\times\\{n\\})$. Lemma F.2 shows that for nested complexes
$L\subset K$ such that $K$ collapses to $L$, a cycle is null-homologous in $L$
if and only if it is null-homologous in $K$. As
$\partial(\sigma\times\\{n\\})$ is not null-homologous in $L$ ($L$ is
$(d-1)$-dimensional, so $\operatorname{im}\partial_{d}[L]=0$), then
$\partial(\sigma\times\\{n\\})$ is not null-homologous in
$\mathcal{P}_{d}^{n}$ either. ∎

######  Theorem 5.14.

Let $d$, $n$ be positive integers. There is a pair of nested $d$-dimensional
simplicial complexes $\mathcal{P}_{d}^{n}\subset\mathcal{Q}_{d}^{n}$ with
$n_{d}\in\Theta((d+1)^{3}n)$ $d$-simplices, a unit-length null-homologous
cycle $\gamma\in C_{d-1}(\mathcal{Q}_{d}^{n})$, and a constant $c_{d}\geq 1$
that depends only on $d$ such that
$\mathcal{C}_{\gamma}(\mathcal{P}_{d}^{n},\mathcal{Q}_{d}^{n})\in\Theta(c_{d}^{n_{d}})$.

###### Proof.

The complexes $\mathcal{P}_{d}^{n}$ and $\mathcal{Q}_{d}^{n}$ are the
complexes described in the preceding paragraphs. The cycle
$\gamma=\partial(\sigma\times\\{n\\})/\sqrt{d+1}$, where $\sqrt{d+1}$ is a
normalization factor. We must show that any unit $\gamma$-potential $p$ has
exponentially-large potential energy.

Let $p$ be any unit $\gamma$-potential in $\mathcal{P}_{d}^{n}$. We know that
$\gamma^{T}p=1$ and $\delta_{d-1}[\mathcal{P}_{n}^{d}]p=0$. As
$\delta_{d-1}[\mathcal{P}_{n}^{d}]=\partial_{d}^{T}[\mathcal{P}_{n}^{d}]$, the
second condition is equivalent to saying that $p^{T}b=0$ for any vector
$b\in\operatorname{im}\partial_{d}[\mathcal{P}_{d}^{n}]$. Lemma 5.13 Part 1
proves that
$\partial(\sigma\times\\{n\\})+(-1)^{n-1}d^{-n}\partial(\sigma\times\\{0\\})\in\operatorname{im}\partial_{d}[\mathcal{P}_{d}^{n}]$,
so the previous two facts imply
$p^{T}\big{(}\partial(\sigma\times\\{n\\})+(-1)^{n-1}d^{-n}(\partial(\sigma\times\\{0\\}))\big{)}=0$.
As $p^{T}\partial(\sigma\times\\{n\\})=\sqrt{d+1}$ and
$p^{T}\big{(}\partial(\sigma\times\\{n\\})+(-1)^{n-1}d^{-n}(\partial(\sigma\times\\{0\\}))\big{)}=0$,
then we conclude that
$p^{T}\partial(\sigma\times\\{0\\})=(-1)^{n-1}d^{n}/\sqrt{d+1}$. Moreover, as
the only $d$-simplex in $\mathcal{Q}_{d}^{n}$ that is not in
$\mathcal{P}_{d}^{n}$ is $\sigma\times\\{0\\}$, then the fact that
$\delta_{d-1}[\mathcal{P}_{d}^{n}]p=0$ implies that the potential energy
$\|\delta_{d-1}[\mathcal{Q}_{d}^{n}]p\|^{2}=\big{(}p^{T}\partial(\sigma\times\\{0\\})\big{)}^{2}=\Omega(d^{2n})$.

This shows that $p$ has exponentially-large potential energy with respect to
$n$. By the same argument as in the proof of Theorem 5.9, we can show that $p$
also has exponentially-large potential energy with respect to $n_{d}$, but for
a different (but constant) base of the exponent $c_{d}$. ∎

##  6 Bounds on the Spectral Gap

Our lower and upper bounds on effective resistance imply lower and upper
bounds on the spectral gap of the combinatorial Laplacian. This is because the
spectral gap is the inverse of the maximum effective resistance of all unit-
length, null-homologous cycles, a fact we proved in Lemma 4.4. Therefore, a
corollary of Theorem 5.9 is that the spectral gap of the combinatorial
Laplacian can be exponentially-small in the worst-case. This resolves one of
the most important open questions in the field of Quantum Topological Data
Analysis and shows that Betti Number Estimation algorithms must run for an
exponentially-long time to exactly compute Betti numbers.

###  6.1 Exponentially-small spectral gap.

Based on this connection between the spectral gap and effective resistance of
Lemmas 4.4 and 2.3, we can derive lower and upper bounds on the spectral gap
of the $d$-combinatorial Laplacian as corollaries of the upper and lower
bounds on the effective resistance (Corollary 5.7 and Theorem 5.9). While
lower bounds on the spectral gap were previously known (see for example
[Freedman2014, Proof of Theorem 1.2]), one advantage of our proof is that it
provides a necessary condition for large spectral gap, namely the existence of
a subcomplex with exponentially-large relative torsion.

See 1.2

######  Theorem 6.1.

Let $d$, $n\geq 1$. There is a $d$-dimensional simplicial complex
$\mathcal{B}_{d}^{n}$ with $n_{d}\in\Theta((d+1)^{3}\cdot n)$ $d$-simplices
and a constant $c_{d}\geq 1$ that depends only on $d$ such that the spectral
gaps of $L_{d-1}[\mathcal{B}_{d}^{n}]$ and $L_{d}[\mathcal{B}_{d}^{n}]$ are
$O(\frac{1}{c_{d}^{n_{d}}})$.

We remark that we can also derive lower bound of the spectral gap in terms of
relative torsion as a corollary to Theorem 5.3. This implies bounded spectral
gap for simplicial complexes with no relative torsion, as remarked upon by
Friedman [Friedman1998BettiNumbers, Theorem 7.2] in the case of orientable
$d$-manifolds.

###  6.2 Many Small Eigenvalues.

Corollary 6.1 shows there is a simplicial complex with a single small
eigenvalue. It is natural to ask whether there is a bound on the number of
very small eigenvalues a simplicial complex can have. This is relevant to QTDA
algorithms that work by counting the number of eigenvalues smaller than a
given threshold. Here, we provide a complex ${\mathcal{M}}_{d}^{n}$ with a
polynomial number of exponentially-small eigenvalues.

######  Corollary 6.2.

Let $n,d\geq 1$. There exists a simplicial complex ${\cal M}_{d}^{n}$ with
$n_{d}\in\Theta((d+1)^{3}\cdot n)$ $d$-simplices and a constant $c_{d}>1$ that
depends only on $d$ such that both $L_{d-1}[{\cal M}_{d}^{n}]$ and
$L_{d}[{\cal M}_{d}^{n}]$ have $\Omega(\sqrt{n_{d}})$ eigenvalues of size
$O(\frac{1}{c_{d}^{\sqrt{n_{d}}}})$.

###### Proof of Theorem 6.2.

This follows from Part 2 of Lemma 2.2 relating the spectrum of a complex to
the spectra of its connected components. We define the complex ${\cal
M}_{d}^{n}$ to be $n_{d}$ disjoint copies of the ${\cal B}_{d}^{n}$ of
Corollary 6.1. The complex ${\cal M}_{d}^{n}$ has $n_{d}^{2}$ $d$-simplices
and $n_{d}$ eigenvalues of size $O(\frac{1}{c_{d}^{n_{d}}})$. ∎

###  6.3 Clique-Dense Complexes.

Existing QTDA algorithms perform best when the simplicial complex is clique-
dense, meaning that the simplicial complex has close to the maximal number of
$d$-simplices, i.e $n_{d}\sim\binom{n_{0}}{d+1}$; However, the simplicial
complex we constructed in Theorem 6.1 is sparse: it only has
$n_{d}\in\Theta((d+1)^{2}n_{0})$ $d$-simplices. Therefore, Theorem 6.1 does
not rule out the possibility that clique-dense complexes avoid worst-case
spectral gap.

However, in this section, we show that we can extend the construction of
Theorem 6.1 to clique-dense complexes (at the expense of making the constant
$c_{d}$ of the exponent smaller.) To do this, we use a probabilistic coloring
argument of Newman [Newman2018] that reduces the number of vertices of a
simplicial complex while preserving the number of $d$-simplices and the
Laplacian.

We begin with definitions. A coloring of a simplicial complex is a map on its
vertices $c:\mathcal{K}_{0}\to\mathbb{N}$. The pattern complex of a simplicial
complex $K$ with coloring $c$ is the simplicial complex
$\mathcal{K}_{c}=\\{\\{c(v):v\in\sigma\\}:\sigma\in\mathcal{K}\\}$;
intuitively, the pattern complex of $\mathcal{K}$ is the simplicial complex
obtained by identify all vertices of $\mathcal{K}$ of the same color and
identifying all simplices whose vertices have the same set of colors. While a
simplex in $\mathcal{K}$ may be mapped to a lower-dimensional simplex in the
pattern complex $\mathcal{K}_{c}$ if two of its vertices are the same color,
we are only considered with colorings where this does not happen. A proper
coloring of a $d$-dimensional simplicial complex $\mathcal{K}$ is a coloring
$c:\mathcal{K}_{0}\to\mathbb{N}$ such that (1) the endpoints of each edge in
$\mathcal{K}$ are different colors and (2)
$\\{c(v):v\in\sigma_{1}\\}\neq\\{c(v):v\in\sigma_{2}\\}$ for any distinct
$(d-1)$-simplices $\sigma_{1},\sigma_{2}\in K$. Note that for a proper
coloring, condition (1) guarantees that each simplex in $\mathcal{K}$
corresponds to a simplex of the same dimension in $\mathcal{K}_{c}$.
Additionally, $\mathcal{K}$ and $\mathcal{K}_{c}$ have the same set of $(d-1)$
and $d$-simplices up to recoloring. Proper colorings are relevant to our paper
as they preserve the spectral gap.

######  Lemma 6.3.

Let $\mathcal{K}$ be a $d$-dimensional simplicial complex and let $c$ be a
proper coloring of $\mathcal{K}$. Then
$\lambda_{\min}(L_{d-1}^{up}[\mathcal{K}])=\lambda_{\min}(L_{d-1}^{up}[\mathcal{K}_{c}])$

###### Proof.

This follows as $\mathcal{K}$ and $\mathcal{K}_{c}$ have the same set of
$(d-1)$ and $d$-simplices up to recoloring, so the boundary maps
$\partial_{d}[\mathcal{K}]$ and $\partial_{d}[\mathcal{K}_{c}]$ are the same
up to the signs on the simplices; however, the spectrum of the up Laplacians
$L_{d-1}^{up}[\mathcal{K}]$ and $L_{d-1}^{up}[\mathcal{K}_{c}]$ are unaffected
by different orientations of the simplices ([Goldberg2002, Theorem 4.1.1]), so
the lemma follows. ∎

Newman’s method also requires bounds on a generalized notion of degree. For a
$d$-dimensional simplicial complex $\mathcal{K}$ and natural numbers $0\leq
i<j\leq d$, define
$\Delta_{i,j}(\mathcal{K})=\max_{\sigma\in\mathcal{K}_{i}}|\\{\tau\in
K_{j}:\sigma\subset\tau\\}|$ and $\Delta(\mathcal{K})=\max_{1\leq i<j\leq
d}\Delta_{i,j}(\mathcal{K})$. Newman used a probabilistic argument to show
that for a $d$-dimensional simplicial complex $\mathcal{K}$ there was always a
proper coloring with a bounded number of colors.

######  Lemma 6.4 (Lemma 3, Newman [Newman2018]).

Let $\mathcal{K}$ be a $d$-dimensional simplicial complex such that
$\Delta(K)\geq 4$. Then there is a proper coloring $c$ of $\mathcal{K}$ with
at most $18(\Delta(K)+1)^{6}d^{6}\sqrt[d]{n_{0}}$ colors.

This implies the following corollary of our bound on the spectral gap.

See 1.3

###### Proof.

This is a corollary to Theorem 6.1, Lemma 6.3, and Lemma 6.4. The simplicial
complex $\mathcal{C}_{d}^{n}$ is a pattern complex of a coloring $c$ of the
complex $\mathcal{B}_{d}^{n}$ from Theorem 6.1. This coloring $c$ is the
coloring guaranteed by Lemma 6.4. This coloring has $f(d)\sqrt[d]{n_{0}}$
colors for some function $f$; we can see this by bounding
$\Delta(\mathcal{B}_{d}^{n})$ by a function of $d$. Examining its construction
in Section 5.2, each simplex in $\mathcal{B}_{d}^{n}$ is in at most two
different building blocks. Each building block has $2(d+1)$ vertices, so for
any $1\leq i<j\leq d$, an $i$-simplex in $\mathcal{B}_{d}^{n}$ is incident to
at most $\binom{4d-i-1}{j-i}$ $j$-simplices. Thus,
$\Delta(\mathcal{B}_{d}^{n})$ is at most some function of $d$. Therefore,
there is a simplicial complex with $\tilde{n_{0}}=f(d)\sqrt[d]{n_{0}}$
vertices and $\theta\left(\frac{(d+1)^{3}}{f(d)^{d}}\tilde{n_{0}}^{d}\right)$
$d$-simplices. As
$\binom{n_{0}}{d}\leq\left(\frac{e\tilde{n_{0}}}{d}\right)^{d}$, then there
are $\Omega(\kappa_{d}\binom{\tilde{n_{0}}}{d})$ $d$-simplices in
$\mathcal{C}_{d}^{n}$ for some appropriate function
$f(d)=\Omega\left(\frac{(d+1)^{3}}{f(d)^{d}e^{d}}\right)$. ∎

###  6.4 Variants of the Laplacian.

We finish this section by showing how our results imply upper and lower bounds
on the spectral gap of several variants of the Laplacian.

####  6.4.1 Boundary Matrix.

The QTDA algorithm of McArdle, Gilyén, and Berta [mccardle2023streamlined] is
not parameterized by the spectral gap of the combinatorial Laplacian; rather,
it is parameterized by the spectral gap of the boundary matrices. However, the
non-zero singular values of the $d$th boundary matrix $\partial_{d}$ are the
square roots of the eigenvalues of the $(d-1)$st up Laplacian $L_{d-1}^{up}$
as $L_{d-1}^{up}=\partial_{d}\partial_{d}^{T}$. Therefore, Theorem 1.2 and
Theorem 6.1 imply exponential upper and lower bounds on the spectral gap of
the boundary matrix.

####  6.4.2 Normalized Laplacian.

We now show that the normalized up Laplacian $\tilde{L}_{d}^{up}$ can also
have exponentially-small spectral gap. While the eigenvalues of the
unnormalized $d$th up Laplacian $L_{d}^{up}$ are in the range $[0,\,n_{0}]$,
the eigenvalues of the normalized $d$th up Laplacian are in the range
$[0,\,d+2]$ [Horak2013, Theorem 3.2.i]. As the normalized up Laplacian has a
constant upper bound on its eigenvalues, it is reasonable to suspect the
normalized up Laplacian also has a constant lower bound on its eigenvalues.
Theorem 6.5 shows this is not the case.

######  Corollary 6.5.

Let $d$, $n\geq 1$. There is a $d$-dimensional simplicial complex
$\mathcal{B}_{d}^{n}$ with $n_{d}\in\Theta(\operatorname{poly}(d)\cdot n)$
$d$-simplices and a constant $c_{d}\geq 1$ that depends only on $d$ such that
the spectral gap the normalized up Laplacian is
$\lambda_{\min}(\tilde{L}_{d}^{up})\in O(\frac{1}{c_{d}^{n_{d}}})$.

###### Proof.

This follows from Theorem 1.2 and Lemma 2.5. The statement follows as
$d_{\min}[\mathcal{B}_{d}^{n}]=1$. ∎

####  6.4.3 Persistent Laplacian.

Recently, Wang, Nguyen, and Wei [wang2020persistent] introduced the persistent
Laplacian of simplicial filtrations as a generalization of the combinatorial
Laplacian. The spectral gap of the persistent Laplacian has since appeared as
a parameter of quantum algorithms for computing persistent Betti number
[Hayakawa2022quantumalgorithm], so lower bounding it is also of interest to
QTDA. Mémoli, Wan, and Wang [memoli2022persistent, Theorem SM5.8] prove that
persistent Laplacians preserve effective resistance of cycles; therefore, the
bounds on the spectral gap of the combinatorial Laplacian also apply to the
persistent Laplacian by Lemma 4.4.

##  7 Conclusion and Open Questions.

In this paper, we propose a new span-program-based quantum algorithm for
computing Betti numbers. This algorithm is a novel approach to QTDA that is
more similar to classical incremental algorithms for computing Betti numbers
than previous QTDA algorithms. Unfortunately, we show that, in the worse case,
the span-program based algorithm takes exponential time due to cycles with
exponentially-large effective resistance or effective capacitance. However, as
a corollary to exponentially-large effective resistance, we prove that the
spectral gap of the combinatorial Laplacian can be exponentially small. This
proves that all known QTDA algorithms also require exponential time in the
worst case. Below we discuss some of the questions left open by our work.

##### Incremental Quantum Algorithm for Persistent Betti numbers.

Our algorithm incrementally computes the Betti number of a simplicial complex.
While the classical algorithm for computing persistent Betti numbers is
incremental [zomorodian2004computing], our algorithm is unable to perform
persistent pairing. In other words, our algorithm can identify when a homology
class dies, but it cannot identify when that homology class was born. It is an
open question whether our algorithm can be adapted to compute the persistent
Betti numbers of a simplicial complex. There are quantum algorithms for
computing persistent Betti numbers [Hayakawa2022quantumalgorithm,
mccardle2023streamlined], but these algorithms are not incremental.

##### Lower Bounds or Expectation of the Spectral Gap.

Theorem 6.1 shows that the spectral gap of the combinatorial Laplacian can be
exponentially small. However, it is an open question how common these sorts of
worst-case complexes are. While there are exact or expected lower bounds for
certain families of simplicial complexes [beit2020spectral,
Friedman1998BettiNumbers, gundert2016eigenvalues, lew2020spectralb,
lew2020spectral, lew2023garland, STEENBERGEN201456, yamada2019spectrum], it is
still unknown what the expected spectral gap is, or if there are lower bounds
on the spectral gap, for all simplicial complexes, or for families of
simplicial complexes of interest like Vietoris-Rips complexes.

##### Cheeger Inequalities and Implications of Exponentially-Small Spectral
Gaps.

The existence of simplicial complexes with exponentially-small spectral gap
implies that existing QTDA algorithms cannot exactly compute Betti numbers
without running for an exponentially long time; however, they can solve the
related problem of Approximate Betti Number Estimation [gyurik2022advantage]
of counting the number of eigenvalues of the Laplacian smaller than a given
threshold. However, it remains an open question how useful approximate Betti
number estimation is in practice.

A potential interpretation for approximate Betti number estimation could come
in the form of a higher-dimensional Cheeger inequality. The Cheeger inequality
in graphs relates the smallest eigenvalue(s) of the graph Laplacian to a value
called the Cheeger constant that measures the existence of (multi-way) sparse
graph cuts [chung1996laplacians, lee2014multiway]. Intuitively, if the Hodge
Theorem (Theorem 2.1) says that the graph Laplacian has more than one zero
eigenvalue if and only if the graph is disconnected, then the Cheeger
inequality says that it has small non-zero eigenvalues if and only if it is
“almost” disconnected.

However, higher-dimensional generalizations of the Cheeger inequality remain
elusive. Ideally, a higher-dimensional Cheeger inequality would say something
similar: a simplicial complex “almost has non-trivial $d$-homology” or “has a
sparse cut” if and only the $d$th combinatorial Laplacian has small non-zero
eigenvalues. One hurdle is that it is not clear how to generalize the notion
of “sparse cut” to higher dimensions. While there have been several
definitions proposed for a Cheeger constant for higher-dimensional Laplacians
[Gromov2010Expanders, LinialMeshulam2006HomConn, MeshulamWallach2009HomConn,
ParzanchevskiEtal2016IsoperSimpComp], one or both sides of a Cheeger
inequality have failed for these constants [Gunder2015HighDimCheeger,
gundert2016eigenvalues, ParzanchevskiEtal2016IsoperSimpComp,
SteenBergen2014CheegerType]. Our work provides another counterexample to these
Cheeger inequalities; the spectral gap of our worst-case complexes is
exponentially small, but the proposed notions of Cheeger constant cannot be.

A recent paper presents a two-sided Cheeger inequality [jost2023cheeger] that
connects the spectral gap of the combinatorial Laplacian to a Cheeger constant
based on the 1-norm of chains. This Cheeger inequality does not have the same
interpretation as the graph Cheeger inequality of implying that simplicial
complexes with small eigenvalues “almost have non-trivial homology” though. It
remains an open question if such a higher-dimensional Cheeger inequality
exists.

## Acknowledgements.

This work was supported by NSF grants CCF-1816442 and CCF-1617951

## References

  * [1] Scott Aaronson.  Read the fine print.  Nature Physics, 11(4):291–293, Apr 2015.
  * [2] Michał Adamaszek and Juraj Stacho.  Complexity of simplicial homology and independence complexes of chordal graphs.  Computational Geometry, 57:8–18, 2016.
  * [3] Simon Apers, Sayantan Sen, and Dániel Szabó.  A (simple) classical algorithm for estimating betti numbers.  arXiv preprint arXiv:2211.09618, 2022.
  * [4] Orr Beit-Aharon and Roy Meshulam.  Spectral expansion of random sum complexes.  Journal of Topology and Analysis, 12(04):989–1002, 2020.
  * [5] Aleksandrs Belovs and Ben W. Reichardt.  Span programs and quantum algorithms for $st$-connectivity and claw detection.  In Algorithms – ESA 2012, pages 193–204. Springer Berlin Heidelberg, 2012.
  * [6] Béla Bollobás.  Modern graph theory, volume 184.  Springer Science & Business Media, 1998.
  * [7] Ulrich Brehm and Karanbir S Sarkaria.  Linear vs. piecewise-linear embeddability of simplicial complexes.  1992\.
  * [8] Chris Cade and P. Marcos Crichigno.  Complexity of supersymmetric systems and the cohomology problem, 2021\.
  * [9] Chris Cade, Ashley Montanaro, and Aleksandrs Belovs.  Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness.  Quantum Info. Comput., 18(1–2):18–50, February 2018.
  * [10] Gunnar Carlsson and Mikael Vejdemo-Johansson.  Topological data analysis with applications.  Cambridge University Press, 2021.
  * [11] Fan RK Chung.  Laplacians of graphs and cheeger’s inequalities.  Combinatorics, Paul Erdos is Eighty, 2(157-172):13–2, 1996.
  * [12] Marcos Crichigno and Tamara Kohler.  Clique homology is qma1-hard, 2022.
  * [13] Cecil Jose A. Delfinado and Herbert Edelsbrunner.  An incremental algorithm for betti numbers of simplicial complexes.  In Proceedings of the Ninth Annual Symposium on Computational Geometry, SCG ’93, page 232–239, New York, NY, USA, 1993. Association for Computing Machinery.
  * [14] Tamal K. Dey, Anil N. Hirani, and Bala Krishnamoorthy.  Optimal homologous cycles, total unimodularity, and linear programming.  SIAM J. Comput., 40(4):1026–1044, July 2011.
  * [15] Tamal K. Dey, Tao Hou, and Sayan Mandal.  Computing minimal persistent cycles: Polynomial and hard cases.  In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’20, page 2587–2606, USA, 2020. Society for Industrial and Applied Mathematics.
  * [16] Tamal Krishna Dey and Yusu Wang.  Computational topology for data analysis.  Cambridge University Press, 2022.
  * [17] Nathan M. Dunfield and Anil N. Hirani.  The least spanning area of a knot and the optimal bounding chain problem.  In Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, SoCG ’11, page 135–144, New York, NY, USA, 2011. Association for Computing Machinery.
  * [18] Christoph Dürr, Mark Heiligman, Peter HOyer, and Mehdi Mhalla.  Quantum query complexity of some graph problems.  SIAM Journal on Computing, 35(6):1310–1328, January 2006.
  * [19] Beno Eckmann.  Harmonische funktionen und randwertaufgaben in einem komplex.  Commentarii Mathematici Helvetici, 17(1):240–255, Dec 1944.
  * [20] Herbert Edelsbrunner and John Harer.  Computational Topology - an Introduction. American Mathematical Society, 2010.
  * [21] Marek Filakovský, Peter Franek, Uli Wagner, and Stephan Zhechev.  Computing simplicial representatives of homotopy group elements.  Journal of Applied and Computational Topology, 2(3):177–231, Dec 2018.
  * [22] Michael Freedman and Vyacheslav Krushkal.  Geometric complexity of embeddings in $\mathbb{R}^{d}$.  Geometric and Functional Analysis, 24(5):1406–1430, Oct 2014.
  * [23] J. Friedman.  Computing betti numbers via combinatorial laplacians.  Algorithmica, 21(4):331–346, Aug 1998.
  * [24] Timothy Goldberg.  Combinatorial laplacians of simplicial complexes.  B.S. Thesis, Bard College, Annandale-on-Hudson, NY, 2002.
  * [25] Mikhail Gromov.  Singularities, expanders and topology of maps. part 2: from combinatorics to topology via algebraic isoperimetry.  Geometric and Functional Analysis, 20(2):416–526, Aug 2010.
  * [26] Anna Gundert.  On expansion and spectral properties of simplicial complexes.  PhD thesis, ETH Zurich, Zürich, 2013.
  * [27] Anna Gundert and May Szedlák.  Higher dimensional discrete cheeger inequalities.  J. Comput. Geom., 6(2):54–71, 2015.
  * [28] Anna Gundert and Uli Wagner.  On eigenvalues of random complexes.  Israel Journal of Mathematics, 216:545–582, 2016.
  * [29] Sam Gunn and Niels Kornerup.  Review of a quantum algorithm for betti numbers, 2019.
  * [30] Casper Gyurik, Chris Cade, and Vedran Dunjko.  Towards quantum advantage via topological data analysis.  Quantum, 6:855, November 2022.
  * [31] Jakob Hansen and Robert Ghrist.  Toward a spectral theory of cellular sheaves.  Journal of Applied and Computational Topology, 3(4):315–358, Aug 2019.
  * [32] Allen Hatcher.  Algebraic topology.  Cambridge Univ. Press, Cambridge, 2000.
  * [33] Ryu Hayakawa.  Quantum algorithm for persistent Betti numbers and topological data analysis.  Quantum, 6:873, December 2022.
  * [34] Danijela Horak and Jürgen Jost.  Interlacing inequalities for eigenvalues of discrete laplace operators.  Annals of Global Analysis and Geometry, 43:177–207, 2013.
  * [35] Danijela Horak and Jürgen Jost.  Spectra of combinatorial laplace operators on simplicial complexes.  Advances in Mathematics, 244:303–336, 2013.
  * [36] Tsuyoshi Ito and Stacey Jeffery.  Approximate span programs.  Algorithmica, 81(6):2158–2195, November 2018.
  * [37] Michael Jarret, Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita.  Quantum algorithms for connectivity and related problems.  In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:13, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [38] Stacey Jeffery and Shelby Kimmel.  Quantum algorithms for graph connectivity and formula evaluation.  Quantum, 1:26, August 2017.
  * [39] Jürgen Jost and Dong Zhang.  Cheeger inequalities on simplicial complexes, 2023.
  * [40] M. Karchmer and A. Wigderson.  On span programs.  In [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference. IEEE Comput. Soc. Press, 1993.
  * [41] A. Yu. Kitaev.  Quantum measurements and the Abelian Stabilizer Problem.  arXiv e-prints, pages quant–ph/9511026, November 1995.
  * [42] Woong Kook and Kang-Ju Lee.  Simplicial networks and effective resistance.  Advances in Applied Mathematics, 100:71–86, 2018.
  * [43] James R Lee, Shayan Oveis Gharan, and Luca Trevisan.  Multiway spectral partitioning and higher-order cheeger inequalities.  Journal of the ACM (JACM), 61(6):1–30, 2014.
  * [44] Alan Lew.  Spectral gaps, missing faces and minimal degrees.  Journal of Combinatorial Theory, Series A, 169:105127, 2020.
  * [45] Alan Lew.  The spectral gaps of generalized flag complexes and a geometric hall-type theorem.  International Mathematics Research Notices, 2020(11):3364–3395, 2020.
  * [46] Alan Lew.  Garland’s method for token graphs.  arXiv preprint arXiv:2305.02406, 2023.
  * [47] Nathan Linial and Roy Meshulam.  Homological connectivity of random 2-complexes.  Combinatorica, 26(4):475–487, aug 2006.