Expansion Testing using Quantum Fast-Forwarding
and Seed Sets
Simon Apers
CWI (The Netherlands) and ULB (Belgium)
Expansion testing aims to decide whether an n-node graph has expansion
at least Φ, or is far from any such graph. We propose a quantum expansion
tester with complexity
e
O(n
1/3
Φ
−1
). This accelerates the
e
O(n
1/2
Φ
−2
) classical
tester by Goldreich and Ron [Algorithmica ’02], and combines the
e
O(n
1/3
Φ
−2
)
and
e
O(n
1/2
Φ
−1
) quantum speedups by Ambainis, Childs and Liu [RANDOM
’11] and Apers and Sarlette [QIC ’19], respectively. The latter approach builds
on a quantum fast-forwarding scheme, which we improve upon by initially
growing a seed set in the graph. To grow this seed set we use a so-called
evolving set process from the graph clustering literature, which allows to grow
an appropriately local seed set.
1 Introduction and Summary
The (vertex) expansion of a graph is a measure for how well connected the graph is. For
an undirected graph G = (V, E), with |V| = n and |E| = m, it is defined as
Φ(G) = min
S⊂V:|S|≤n/2
|∂S|
|S|
,
where ∂S is the set of nodes in V\S that have an edge going to S. See [LR99] for a discussion
on the relevance of expansion for a range of graph approximation algorithms, and [HLW06]
for a survey on expander graphs and their applications. Since exactly determining Φ(G) is
an NP-hard problem [LRV13], we consider the relaxed objective of testing the expansion.
Goldreich and Ron [GR02, GR11] initially studied this problem in the bounded-degree
model, where they proposed the following question: given query acces to G, does it have
expansion at least some Φ, or is it far from any graph having expansion
e
Ω(Φ
2
)? In this
model, given graphs G and G
0
with degree bound d, G is -far from G
0
if at least nd edges
have to be added or removed from G to obtain G
0
. They proved an Ω(n
1/2
) lower bound
on the query complexity of this problem, and proposed an elegant tester based on random
walk collision counting with complexity
1
e
O(n
1/2
Φ
−2
).
In rough strokes, the algorithm picks a uniformly random node, and counts collisions
between
e
O(n
1/2
) independent random walks of length
e
O(Φ
−2
) all starting from this node.
If the graph is far from being an expander, then the random walk will get stuck in certain
low-expansion subsets, leading to an increased number of collisions. The graph is hence
rejected if the number of collisions exceeds some constant.
Simon Ap ers: smgapers@gmail.com, Most of the work was done while part of the CWI-Inria International Lab.
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 1
arXiv:1907.02369v3 [quant-ph] 11 Sep 2020
?
Figure 1: The GR tester counts collisions between independent random walks starting from some seed
node. Low expansion of the graph results in an increased number of collisions.
Goldreich and Ron had to base the correctness of their tester on a certain unproven
combinatorial conjecture. However, in later works by Czumaj and Sohler [CS10], Kale and
Seshadhri [KS11] and Nachmias and Shapira [NS10] the correctness was unconditionally
established. The ideas underlying this tester and its analysis were more recently extended
towards testing the k-clusterability of a graph [CPS15, CKK
+
18], which is a multipartite
generalization of the expansion testing problem.
In this work we consider the expansion testing problem in the quantum setting, where
we allow to perform queries in superposition. We refer to the nice survey by Montanaro and
de Wolf [MdW16] for a general overview of quantum property testing. Ambainis, Childs
and Liu [ACL11] were the first to describe a quantum algorithm for expansion testing.
The gist of their algorithm is to combine an appropriate derandomization of the GR tester
with Ambainis’ quantum algorithm for element distinctness [Amb07]. The latter allows
to count collisions among the set of
e
O(n
1/2
) random walk endpoints using only
e
O(n
1/3
)
quantum queries. The improved complexity of their quantum expansion tester is
e
O(n
1/3
Φ
−2
).
In addition they proved an
e
Ω(n
1/4
) lower bound on the quantum query complexity.
In later work of the current author together with Sarlette [AS19], as well as in the
current work, a very different approach is taken. Quantum walks, which form the quantum
counterpart of random walks, are used to explore the graph. Rather than picking random
neighbors, a quantum walk explores a graph through quantum queries to its neighborhood.
In particular, this allows to create a “quantum sample” that appropriately encodes the
random walk distribution. As we detail in Section 1.1 below, we can then use standard
tools from quantum algorithms to estimate the random walk collision probability. In [AS19]
we introduced a new quantum walk technique called “quantum fast-forwarding” (QFF) that
allows to approximately prepare these quantum samples in the square root of the random
walk runtime. This yielded a new quantum expansion tester with complexity
e
O(n
1/2
Φ
−1
),
quadratically improving the dependency of the GR tester on Φ, which corresponds to
the random walk runtime. Up to this work, this left the problem of quantum expansion
testing with two different testers with a complementary speedup. In this work, however,
we present a new quantum tester which closes this gap. Essentially we improve the QFF
tester from [AS19] by initially doing some classical work in the graph: from the initial node
v, we first grow a local node subset or “seed set” of size n
1/3
. In earlier work by the author
[A19] it was already shown that such seed sets allow to more efficiently create quantum
samples, essentially by improving the projection of the initial state on the final quantum
sample. Indeed, starting from this seed set, rather than directly from v, we can run the
1
In this section we hide polynomial dependencies on log n, the degree bound d
M
of the graph, and the
distance parameter . In the rest of the paper,
e
O simply hides any poly-logarithmic dependencies.
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 2
Goldreich and Ron [GR02]
e
O(n
1/2
Φ
−2
)
(conj.)
RW collision counting
Czumaj and Sohler [CS10],
Kale and Seshadhri [KS11],
Nachmias and Shapira [NS10]
e
O(n
1/2
Φ
−2
) prove GR conjecture
Ambainis, Childs and Liu [ACL11]
e
O(n
1/3
Φ
−2
) (q) quantum element distinctness
Apers and Sarlette [AS19]
e
O(n
1/2
Φ
−1
) (q) QFF
this work
e
O(n
1/3
Φ
−1
) (q) QFF and seed sets
Table 1: Complexity for expansion testing. (q) denotes quantum complexity.
QFF tester with an improved complexity
e
O(n
1/3
Φ
−1
). To prove correctness of the tester,
we must ensure that if the initial node v is inside some low-expansion set, then the seed set
largely remains inside that set. Thereto we borrow a so-called “evolving set process” from
the local graph clustering literature [AGPT16], allowing to grow such a set in complexity
e
O(n
1/3
Φ
−1
). This allows to prove our main result:
Theorem 1. There exists a quantum expansion tester with complexity
e
O(n
1/3
Φ
−1
).
The resulting speedup combines the quantum speedups of [ACL11] and [AS19]. To sum-
marize, we gather the different algorithms and approaches in Table 1.
1.1 QFF Tester
Our tester builds on the QFF tester from [AS19], hence we describe this tester first. Let
P denote the random walk (RW) transition matrix, and P
t
|vi the t-step RW probability
distribution
2
starting from a node v. The tester builds on the observation that the squared
2-norm kP
t
|vik
2
exactly equals the collision probability of a pair of random walks:
kP
t
|vik
2
=
X
u∈V
P
t
(u, v)
2
=
X
u∈V
P(X
t
= u |X
0
= v)
2
,
where we let X
t
denote the random walk position at time step t. Hence, we can estimate
the collision probability between the t-step RW endpoints simply by estimating kP
t
|vik
2
.
This we can do rather straightforwardly using quantum algorithms, in particular making
use of quantum walks (QWs). Starting from an initial node v of the graph, a QW allows
to generate the quantum sample
|ψ
t
i = P
t
|vi + |Γi,
which encodes the RW probability distribution P
t
|vi as one of its component, with |Γi
some auxiliary garbage component that is orthogonal to the RW component, and which
we will not care about. Given the ability to generate such quantum samples, we can then
use a standard quantum routine called quantum amplitude estimation to estimate the norm
kP
t
|vik
2
of the RW component. Now, similarly to the GR tester, if we set t ∈ O(Φ
−2
)
then we can reject the graph if kP
t
|vik
2
, and hence the collision probability, is larger than
some threshold.
2
We use the ket-notation |vi to simply denote the indicator vector on node v.
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 3
The amplitude estimation routine requires
e
O(kP
t
|vik
−1
) quantum samples, so that the
complexity of this quantum expansion tester is
e
O(kP
t
|vik
−1
QS
t
), where QS
t
denotes the
quantum complexity of creating the quantum sample |ψ
t
i. If the graph is regular
3
then P
has a uniform stationary distribution, i.e., the vector |πi = n
−1/2
P
u∈V
|ui is the unique
eigenvalue-1 eigenvector of P . This allows to bound
kP
t
|vik ≥ |hπ|vi| = n
−1/2
, (1)
so that
e
O(kP
t
|vik
−1
QS
t
) ∈
e
O(n
1/2
QS
t
). In order to bound QS
t
, we can use an existing
QW approach by Watrous [Wat01] which gives QS
t
∈ O(t). Since we choose t ∈
e
O(Φ
−2
),
this yields a complexity
e
O(n
1/2
Φ
−2
), thus giving no speedup with respect to the GR tester.
In [AS19] however, we introduced a more involved QW technique called quantum fast-
forwarding (QFF). Building on a Chebyshev truncation of the P
t
operator, this technique
allows to quadratically improve the complexity to QS
t
∈ O(t
1/2
), resulting in a complexity
e
O(n
1/2
Φ
−1
).
Given that the GR tester has complexity
e
O(n
1/2
Φ
−2
), this yields a complementary speedup
to the
e
O(n
1/3
Φ
−2
) expansion tester in [ACL11]. Whereas their speedup follows from a
quantum routine for accelerating the collision counting procedure, the speedup in the QFF
tester follows from accelerating the random walk runtime.
1.2 QFF Tester with Seed Sets
In this paper we refine the QFF tester, improving its complexity to
e
O(n
1/3
Φ
−1
). We
improve its suboptimal n
1/2
-dependency by initially constructing or “growing” a seed set
around the initial node, from which we then run the QFF tester. This idea is derived from
earlier work of the author [A19], where seed sets are used to create a superposition over the
edges of a graph, leading to a similar speedup. The main insight is derived from the bound
in (1), showing that the suboptimal n
1/2
-dependency stems from a small projection of the
initial state |vi onto the uniform superposition |πi. Growing a seed set allows to improve
this dependency: if we grow a set S ⊆ V from v, and we use the quantum superposition
|Si = |S|
−1/2
P
u∈S
|ui as an initial state, this bound becomes
kP
t
|Sik ≥ |hπ|Si| = |S|
1/2
n
−1/2
.
This suggests the following new tester: (i) pick a uniformly random node v, (ii) grow a
seed set S from v of appropriate size, and (iii) create
e
O(n
1/2
|S|
−1/2
) QW samples |ψ
t
i =
P
t
|Si+|Γi, allowing to estimate kP
t
|Sik. Assuming that the construction of S requires |S|
queries, and momentarily ignoring the Φ-dependency, this tester has a combined complexity
of
e
O(|S|+kP
t
|Sik
−1
) ∈
e
O(|S|+n
1/2
|S|
−1/2
). If we choose |S| = n
1/3
, this becomes
e
O(n
1/3
)
as we aimed for.
Using a similar reasoning as before, we again wish to reject the graph if our estimate
is larger than some threshold. Indeed, as depicted in Figure 2, if the seed set is localized
in some low-expansion set, then the 2-norm kP
t
|Sik will be larger than when the graph
has no low-expansion sets. The difficulty however is to ensure that the seed set S, when
grown from some initial node v in a low-expansion set, effectively remains inside that set.
If this is not the case, then a RW from S will no longer be stuck in the low-expansion set,
thus no longer giving rise to an increased 2-norm. As a consequence, we cannot simply
3
Later on we adapt the graph to ensure this.
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 4
use a breadth-first search from v, as we did in [A19]: a BFS might exit a low-expansion
set more easily than a random walk. Luckily, however, the problem of locally exploring a
low-expansion set (or “cluster”) turns out to be well-studied under the name “local graph
clustering” [ST13, ACL06, AGPT16, OSV12].
?
Figure 2: The new tester classically grows an appropriately local seed set around the initial node. From
this set a quantum sample can be generated more efficiently. We use an evolving set process to ensure
that the seed set mostly remains inside the initial low-expansion set.
In particular, we can use a so-called “evolving set process” (ESP) as used by Andersen,
Oveis-Gharan, Peres and Trevisan in [AGPT16]. An ESP is a Markov chain on subsets
of the nodes, which evolves by expanding or contracting its boundary based on the RW
behavior on the graph. Given an initial node v inside a low-expansion set, they simulate
an ESP to explicitly retrieve this set. Since we are interested in growing a potentially
much smaller seed set S inside the cluster, we slightly adapt their algorithm, leading to the
following result. The algorithm either returns a low-expansion set, allowing to immediately
reject the graph, or it returns an appropriate seed set.
Proposition 1. Fix a parameter M ≥ 0. Given a random node v from a set S
0
of
expansion
e
O(Φ
2
), we can use an ESP to return a set S such that with constant probability
either Φ(S) < Φ or |S| ≥ M and |S ∩ S
0
|/|S| ∈ Ω(1). The complexity of generating this
set is
e
O(MΦ
−1
).
Building on this tool, we can now sketch our new quantum tester, summarized in Algo-
rithm 1. Since the ESP process requires
e
O(n
1/3
Φ
−1
) steps by the above proposition, and
estimating kP
t
|Sik requires
e
O(kP
t
|SikΦ
−1
) ∈
e
O(n
1/3
Φ
−1
) steps, we retrieve the promised
tester complexity
e
O(n
1/3
Φ
−1
).
Algorithm 1 Quantum Expansion Tester
1: select a uniformly random starting node v
2: grow a seed set S from v using an ESP
3: if Φ(S) < Φ then reject
4: use quantum amplitude estimation to estimate kP
t
|Sik for t ∈
e
O(Φ
−1
)
5: if kP
t
|Sik too large then reject else accept
1.3 Open Questions
We finish this section by discussing some open questions related to this work.
• In [A19] a breadth-first search is used to grow a seed set S, requiring a number of
steps
e
O(|S|). In the current work we use a more refined ESP algorithm to grow S,
which in particular ensures that the set remains inside some low-expansion subset (say
with expansion at most Φ). This procedure however requires an increased number of
steps
e
O(|S|Φ
−1
). We leave it as an open question whether such an appropriate set
can be grown in
e
O(|S|) steps. The complexity of the tester then becomes
e
O(|S| +
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 5
n
1/2
|S|
−1/2
Φ
−1
). Setting |S| = n
1/3
Φ
−2/3
this would lead to an improved complexity
e
O(n
1/3
Φ
−2/3
).
• The use of an ESP for the expansion testing problem could also be useful for improv-
ing the Φ-dependency of the classical GR tester. If we could for instance grow a pair
of seed sets, both of size n
1/2
, that behave to some extent as “random subsets” of a
local cluster, then we could simply count collisions between these sets, thus avoiding
the use of random walks. A higher number of collisions would then again signal a
low expansion of the graph. Ideally an ESP-like procedure would allow to grow these
sets in
e
O(n
1/2
Φ
−1
) steps, improving on the
e
O(n
1/2
Φ
−2
) complexity of the GR tester.
• Clusterability testing, as recently studied in [CPS15, CKK
+
18], uses very similar
techniques to the GR expansion tester. It seems feasible that we can use the tech-
niques from this paper to similarly improve on these testers.
• Goldreich and Ron [GR02] proved a classical lower bound Ω(n
1/2
) for expansion
testing, suggesting that their tester has an optimal dependency on n. In the quantum
setting however, the only known lower bound is Ω(n
1/4
) as proven by Ambainis,
Childs and Liu [ACL11], thus leaving a large gap to all current quantum testers,
which have a
e
O(n
1/3
)-dependency. While our work does not provide any new insights
towards closing this gap, we do feel that this is an interesting question to resolve.
2 Preliminaries
In this section we formalize the computational model, the query model and the definition of
an expansion tester. We also describe some necessary random walk properties, and define
the notion of a quantum walk.
2.1 Complexity, Computational Model and QRAM
The quantum query complexity of an algorithm simply denotes the number of quantum
queries that the algorithm makes to the input (see Section 2.2 for details).
In contrast, the actual runtime or complexity of the algorithm is defined with respect
to a computational model. We specify our computation model as a system that
1. can run quantum routines on O(log n) qubits, where n is the number of nodes in the
input graph,
2. can make quantum queries to the input (see Section 2.2), and
3. has access to a quantum-read/classical-write RAM (QRAM) of
e
O(n
1/3
) classical bits.
A single QRAM operation corresponds to either (i) classically writing a bit to the
QRAM, or (ii) making a quantum query to bits stored in the QRAM.
By the complexity of an algorithm we denote the total number of (i) queries, (ii) elementary
classical and quantum operations (gates), and (iii) QRAM operations. By definition, the
complexity of an algorithm forms an upper bound on the query complexity of an algorithm,
irrespective of the computational model or QRAM assumptions.
Let S ⊂ V be a subset of nodes. As in [A19], we can use the QRAM to efficiently
create, and reflect around, the quantum state |Si = |S|
−1/2
P
v∈S
|vi. To this end, we rely
on the following theorem by Kerenidis and Prakash [KP17].
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 6
Theorem 2 ([KP17, Theorem 15]). Assume that we are given a subset S ⊂ V. With a
one-off preprocessing cost of
e
O(|S|) QRAM operations, we can repeatedly (i) create the
quantum state |Si, and (ii) reflect around the quantum state |Si, both using
e
O(1) QRAM
operations per repetition.
We make two final comments on our QRAM assumption, as it is often subject of
debate. First, such an assumption is native to any quantum algorithm that makes use
of quantum-accessible classical input or memory. We note that the actual qubits that a
QRAM query acts on (i.e., the superposition of queried addresses plus the target register)
is only logarithmic in the number of stored bits. In that sense our memory requirement is
weaker than for instance that of Ambainis’s element distinctness algorithm [Amb07] and
its application in the quantum expansion tester of [ACL11], which effectively require a
polynomial-sized memory of qubits. Second, as already pointed out above, the complexity
is an upper bound on the query complexity, irrespective of the computational model or
QRAM assumptions. In that sense, our work improves on the query complexity of the
former works [ACL11, AS19], also without these assumptions.
2.2 Query Model and Property Testing
We are given query access to some undirected graph G = (V, E), with node set V = [n]
and edge set E. We denote |E| = m. For any v ∈ V, we let d(v) denote the degree of v,
the maximum degree d
M
= max
v∈V
d(v), and d(S) =
P
v∈S
d(v) denotes the total degree
of a set S ⊆ V. We say that G has degree bound d if d
M
≤ d. In the context of property
testing of bounded-degree graphs [GR02], the following queries are allowed:
• uniform node query: return uniformly random node v ∈ V
• degree query: given v ∈ V, return degree d(v)
• neighbor query: given v ∈ V, k ∈ [d(v)], return k-th neighbor of v
Throughout the paper we will assume that G is regular. If this is not the case, then we
can always modify the graph to ensure this: to any node i with degree d(i) < d we add
d − d(i) parallel self loops. This effectively renders the graph regular, ensuring that a
random walk converges to the uniform distribution, as we will require later. Notably this
does not change the expansion of the graph. Goldreich and Ron [GR11] achieve the same
effect by modifying the random walk rather than the graph, but modifying the graph will
prove more elegant for our purpose.
Since we wish to study quantum algorithms, we will allow to perform degree and
neighbor queries in superposition. To illustrate this, assume that a neighbor query, given
v ∈ V and k ∈ [d(v)], returns a node u. Using quantum notation, this is described as a
unitary transformation
|vi|ki|xi 7→ |vi|ki|x + ui,
where x is some arbitrary dlog ne-bit string, and “+” denotes addition modulo dlog ne. We
can now imagine the first register being in a superposition d(v)
−1/2
P
k∈[d(v)]
|vi|ki|xi, so
that the query operation now becomes
1
p
d(v)
X
i∈[d(v)]
|vi|ki|xi 7→
1
p
d(v)
X
i∈[d(v)]
|vi|ki|x + u
(k)
i, (2)
where we let u
(k)
denote the k-th neighbor of v. We will call a single such query a “quantum
query”. We refer the interested reader to the survey by Montanaro and de Wolf [MdW16]
for more details on the quantum query model.
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 7
We will follow the property testing model for bounded-degree graphs by Goldreich and
Ron [GR02]. Given two n-node graphs G = ([n], E) and G
0
= ([n], E
0
) with degree bound
d, they define the relative distance between G and G
0
as the number of edges that needs
to be added or removed to turn G into G
0
, divided by the maximum number of edges nd.
This is equal to |E4E
0
|/(nd), with 4 the symmetric difference between E and E
0
. G is
then said to be -far from G
0
if |E4E
0
|/(nd) ≥ . When studying a certain property P
of graphs, G is said to be “-far from having property P ” if G is -far from any graph G
0
having property P .
2.3 Expansion Testing
We define the (vertex) expansion of a subset S ⊂ V as Φ(S) = |∂S|/|S|. Here ∂S = {u ∈
S
c
| ∃v ∈ S s.t. (u, v) ∈ E} is the set of nodes in S
c
that have an edge going to S. The
expansion of a graph G is then defined as
Φ(G) = min
S⊂V:|S|≤n/2
Φ(S).
We consider the following definition of an expansion tester due to Czumaj and Sohler
[CS10].
Definition 1. An algorithm is a (Φ, )-expansion tester if there exists a constant c > 0,
possibly dependent on d, such that given parameters n, d, and query access to an n-node
graph with degree bound d it holds that
• if the graph has expansion at least Φ, then the algorithm outputs “accept” with
probability at least 2/3,
• if the graph is -far from any graph having expansion at least cΦ
2
log
−1
(dn), then
the algorithm outputs “reject” with probability at least 2/3.
We note that this is a slightly more constrained definition than the one in e.g. [KS11,
ACL11, AS19]. In these works the log-factor in the reject case is actually left as an addi-
tional free parameter µ, which is compensated in the runtime. While our algorithm might
also work in that more general setting, we believe that the corresponding technicalities
would go beyond the scope and main ideas of this paper, and we leave it as a minor open
question. We also mention that in the traditional setting of property testing, the expression
“cΦ
2
log
−1
(dn)” in the second bullet should be replaced by “Φ”. Although unproven, the
relaxation in this definition seems necessary to allow for efficient (sublinear) testing using
random walks. This is a consequence of the fact that the expansion only characterizes the
random walk mixing behavior up to a quadratic factor. We stress that this quadratic gap
is present in all works on expansion testing.
Apart from the vertex expansion, we also define the conductance. When studying
random walks, this is often a slightly more appropriate measure. For a subset S ⊂ V
it is defined as φ(S) = |E(S, S
c
)|/d(S), where E(S, S
c
) = {(u, v) ∈ E | u ∈ S, v ∈ S
c
}
denotes the set of edges between S to S
c
. The conductance of a graph G with m edges
is then defined as φ(G) = min
S⊂V:d(S)≤m/2
φ(S). If G is d-regular, as we will assume
throughout the paper, this simplifies to φ(G) = min
S⊂V:|S|≤n/2
|E(S, S
c
)|/(d|S|). Since
|∂S| ≤ |E(S, S
c
)| ≤ d|∂S|, this allows to relate vertex expansion and conductance as
follows:
Φ(S)/d ≤ φ(S) ≤ Φ(S). (3)
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 8
2.4 Random Walks
We will consider lazy random walks (RWs), described by a Markov chain on the node set.
From any node the RW jumps with probability 1/2 to any of its neighbors uniformly at
random, and otherwise stands still. If we let P (u, v) denote the RW transition probability
from node v to node u, then P (u, v) = 1/(2d(v)) for (v, u) ∈ E, P (u, v) = 1/2 if u = v and
P (u, v) = 0 elsewhere. If the underlying graph is connected, then the RW converges to a
unique limit distribution in which every node has a probability proportional to its degree.
On a regular graph, this corresponds to a uniform distribution.
2.4.1 Diffusion Core
Central to the study of expansion testers is the so-called “diffusion core” of a set S ⊆ V.
The diffusion core allows to lower bound the probability that a RW of given length stays
entirely inside S, as a function of its conductance φ(S). Let τ
v
(S
c
) denote the escape time
of S from v, i.e., the hitting time of a RW from v ∈ S to the complement S
c
. We then
define the diffusion core of S as follows:
Definition 2. For α, β > 0, the (α, β)-diffusion core of S is defined as
S
α,β
=
v ∈ S
P(τ
v
(S
c
) > αφ(S)
−1
) ≥ β
.
Throughout we define the “canonical” diffusion core S
d
= S
1/40,3/4
. Using a reasoning
similar to Spielman and Teng [ST13], we can lower bound the size of the diffusion core.
Lemma 1.
d(S
α,β
)
d(S)
> 1 −
α
2(1 − β)
.
Proof. Let Y
v
denote the event that τ
v
(S
c
) > αφ(S)
−1
, let π denote the stationary
distribution of the RW, and let π
S
denote the distribution π conditioned on being in
the set S: π
S
(v) = I(v ∈ S)π(v)/π(S). From [ST13, Proposition 2.5] we know that
P
v∼π
S
(Y
v
) ≥ 1 − α/2. For all v /∈ S
α,β
, it holds by definition that P(Y
v
) < β, so that we
can bound
P
v∼π
S
(Y
v
) =
X
v∈S
π
S
(v)P(Y
v
) < (1 − π
S
(S
α,β
))β + π
S
(S
α,β
).
Combined with the former inequality, and the fact that π
S
(S
α,β
) = d(S
α,β
)/d(S), this
proves the claimed statement.
This lemma implies that d(S
d
)/d(S) > 19/20. As we will require this later, we also
wish to prove something slightly stronger: there exists a subset S
0
of the diffusion core S
d
,
from which we can bound the probability that a random walk stays inside the diffusion
core, rather than only inside S.
Lemma 2. There exists a node subset S
0
of the diffusion core S
d
, with d(S
0
) > d(S)/3,
from which a (120φ(S))
−1
-step RW remains inside S
d
with probability at least 9/10:
∀v ∈ S
0
: P(τ
v
(S
c
d
) > (120φ(S))
−1
) ≥ 9/10.
Proof. In the following we use the shorthand φ = φ(S). We can set S
0
equal to the
(1/30, 39/40)-diffusion core, S
0
= S
1/30,39/40
. Using Definition 2 we see that S
0
⊆ S
d
⊆ S.
From Lemma 1 we know that d(S
0
) > d(S)/3.
We will show that S
0
serves as a diffusion core for S
d
. Thereto fix any v ∈ S
0
and
let κ denote the hitting time κ = τ
v
(S
c
d
). Then we define t such that P(κ ≤ t) > 1/10.
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 9
Now let Y be the event that κ ≤ t and τ
u
(S
c
) ≤ (40φ)
−1
, with u = X
κ
a random variable
corresponding to the node at which the RW hits S
c
d
. Then we have that Y ⇒ (τ
v
(S
c
) ≤
t + (40φ)
−1
). Since u /∈ S
d
, it holds that P(τ
u
(S
c
) ≤ (40φ)
−1
) > 1/4. Combined with
the assumption that P(κ ≤ t) > 1/10, this allows to bound P(Y ) > (1/4)(1/10) = 1/40,
and therefore P(τ
v
(S
c
) ≤ t + (2φ)
−1
) > 1/40. However, since v ∈ S
0
we also have that
P(τ
v
(S
c
) > 1/(30φ)) ≥ 39/40, or equivalently P(τ
v
(S
c
) ≤ 1/(30φ)) ≤ 1/40. This gives
a contradiction if t + (40φ)
−1
≤ 1/(30φ), or equivalently t ≤ 1/(120φ). For such t the
initial hypothesis P(κ ≤ t) > 1/10 must hence be false, and therefore it must hold that
P(κ ≤ (120φ)
−1
) ≤ 1/10 for all v ∈ S
0
. This proves the claimed statement.
We will also use the following lemma, which in essence was already present in [CS10,
NS10, KS11]. It argues that a graph which is -far from having a certain expansion must
have a large subset with low expansion.
Lemma 3. Let G be an undirected n-node graph with degree bound d that is -far from
having expansion ≥ β, with β ≤ 1/10. Then the following holds:
• There exists a subset A ⊂ V, with n/12 ≤ |A| ≤ (1 + )n/2, such that Φ(A) < r
d
β,
with r
d
a constant dependent on d.
• For any t ≤ 1/(2r
d
β) and distribution v having a γ-overlap with the diffusion core
of A, with γ > 2(1 + )/3, it holds that
kP
t
vk
2
≥
1
n
1 + 4
3γ
4
−
1 +
2
2
!
.
Proof. The first bullet is proven in [CS10, Corollary 4.6]. To prove the second bullet, we
use the fact that for a general probability distribution w it holds that
kwk
2
≥
1
n
1 + kw − uk
2
1
,
with u the uniform distribution. This bound can be found in the proof of [CS10, Lemma
4.3]. To lower bound the right hand side, we will use that
kw − uk
1
= 2 max
S⊆V
|w(S) − u(S)| ≥ 2|w(A) − u(A)|.
If w = P
t
v, we can lower bound (P
t
v)(A) since this represents the probability that a t-step
RW from v end in A. By definition of the diffusion core, we know that a (t ≤ 1/(40Φ(A)))-
step RW, starting anywhere in the diffusion core A
d
of A, remains inside A with probability
at least 3/4. Since v has a γ-overlap with A
d
, this proves that a (t ≤ 1/(40r
d
β))-step RW
from v remains inside A with probability at least 3γ/4. This implies that (P
t
v)(A) ≥ 3γ/4
and hence kP
t
v −uk
1
≥ 2|3γ/4 −u(A)|. By our assumption that γ > 2(1+ )/3, and since
u(A) = |A|/n ≤ (1 + )/2, this implies that kP
t
v −uk
1
≥ 2(3γ/4 −(1 + )/2). Combining
this with the above inequality proves the claimed bound.
2.5 Quantum Walks
Quantum walks (QWs) form an elegant quantum counterpart to random walks on graphs.
They similarly explore a graph in a local manner, by performing queries in superposition
to the neighbors of certain nodes, as illustrated in (2) in Section 2.2. In the following, let P
be a symmetric random walk transition matrix (as will be the case for us), and let S ⊆ V
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 10
be the initial seed set. We denote by |Si = |S|
−1/2
P
v∈S
|vi the quantum state that is a
uniform superposition over nodes in S. Starting from |Si, QWs allow to create a quantum
state or “quantum sample” of the form
|ψ
t
i = P
t
|Si + |Γi.
Here the first component forms a quantum encoding of the RW probability distribution
started from a uniformly random node in S. The second component denotes some auxiliary
garbage state in which we will not be interested. In our earlier work on quantum expansion
testing, we introduced a QW technique called “quantum fast-forwarding” (QFF) that allows
to approximate the above quantum sample in the square root of the classical runtime. The
following lemmas follow from [AS19], recalling that d
M
denotes the maximum degree of
the graph.
Lemma 4 (QFF). Starting from the state |Si, there exists a QW algorithm that outputs
a state -close to the quantum sample |ψ
t
i in complexity
e
O(t
1/2
d
1/2
M
log
1/2
(1/)).
Proof. We first note that, starting from |Si, the state |ψ
t
i can be -approximated using a
number of QW steps that scales as
e
O(t
1/2
log
1/2
(1/)) (hiding polylog-dependencies on t,
n, ). An explicit statement of this fact can be found as Theorem 7 in [AGJK20]. Second
we note that a single QW step can be implemented in complexity O(d
1/2
M
), as is mentioned
in [AS19, A19]. Combining both facts proves the lemma.
For clarity of exposition, we will ignore the approximation error of QFF in the rest
of the paper. By linearity it suffices to set inverse polynomially small in n, and so the
approximation error will only add a log-factor to the overall complexity (this in contrast
to the approximation error in the lemma below, which in fact is important).
Given access to such quantum samples, we can use a standard quantum routine called
“quantum amplitude estimation” to estimate kP
t
|Sik. This leads to the following lemma,
which is an immediate corollary from [AS19, Theorem 5] and Lemma 4.
Lemma 5 (2-norm estimator). There exists a QW algorithm that, with probability at least
1 − δ, outputs an estimate a such that
kP
t
|vik − a
≤ . The algorithm has complexity
e
O(t
1/2
d
1/2
M
−1
log δ
−1
) and uses
e
O(
−1
log δ
−1
) reflections around |Si.
As discussed in Section 2.1 (and equal to the approach in [A19]), we can use a QRAM
data structure to prepare and reflect around the quantum state |Si. The effective com-
plexity of these operations in our computation model is then
e
O(1) (i.e., polylogarithmic in
n).
3 Evolving Set Processes
Evolving Set Processes (ESPs) have been used for analyzing the mixing time of Markov
chains [MP05], and as an algorithmic tool for performing local graph clustering [AP09,
AGPT16]. Derived from some original Markov chain over a node set V, an ESP is a
Markov chain over subsets of the node set. For our particular case we will assume that the
original Markov chain corresponds to the (lazy) RW. Given that the current state of the
ESP is S ⊆ V, its next state is then determined by the following rule: draw a variable U
uniformly at random from the interval [0, 1], and set the next state
S
0
=
v ∈ V : P (S, v) ≥ U
.
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 11
Here P (S, v) denotes the probability that a single RW step from v ends up in S, and is
given by P (v, S) = |E(v, S)|/(2d(v)) + I(v ∈ S)/2. This gives rise to an ESP transition
matrix K : 2
V
× 2
V
→ [0, 1]. Notice that only states in the inner or outer boundary of S
can be added or removed: |E(v, S)| = d(v) and I(v ∈ S) = 1 if y and all of its neighbors lie
in S, whereas |E(v, S)| = I(v ∈ S) = 0 if v nor any of its neighbors lie in S. This process
has absorbing states S = ∅ and S = V, both of which have no boundary. For algorithmic
purposes, it is desirable to prevent the ESP from being absorbed in the empty set. To this
end, the transition probabilities can be slightly altered:
ˆ
K(S, S
0
) =
d(S
0
)
d(S)
K(S, S
0
).
Clearly the transition probability to the empty set is now equal to zero.
ˆ
K is again a
stochastic transition matrix, and the resulting process is called the volume-biased ESP (yet
for brevity we will simply refer to it as the ESP). We refer the reader to [AGPT16, LPW17]
for more details on the ESP and its volume-biased variant.
Starting inside some low-expansion set S, ESPs are used as a means of locally con-
structing or exploring S. In our case, we only wish to retrieve a smaller subset, typically
of size |S|
1/3
. This subset however should be sufficiently localized “inside” S, i.e., have
a sufficient overlap with the smaller diffusion core of S. To this end we refine the ESP
analysis: we use our Lemma 2 to show that also the ESP will remain in the diffusion core
with large probability. The following Section 3.1 introduces some useful properties of the
ESP, and in Section 3.2 we prove the main tool.
3.1 ESP Complexity and Properties
As we wish to use an ESP as an algorithmic means, it is desirable to quantify the resources
needed to simulate it. Thereto we define the cost of a sample path
cost(S
0
, . . . , S
t
) = d(S
0
) +
t
X
i=1
d(S
i
4S
i−1
) + |∂(S
i−1
)|
,
with d(S) the total degree of a subset S and S4S
0
the symmetric difference between S
and S
0
. We also define a stopping time τ (T, B, θ) for the ESP:
Definition 3. The stopping time τ(T, B, θ) is a random variable that equals the first time
τ at which either φ(S
τ
) ≤ θ, τ = T , or cost
τ
> B.
The following theorem from [AGPT16] bounds the complexity of sampling from the ESP
with stopping rule τ(T, B, θ).
Theorem 3 ([AGPT16, Proposition 5.3]). There exists an algorithm that takes as input
a node v, two integers T, B ≥ 0 and θ ∈ [0, 1]. Let S
0
= {v} and define the stopping
time τ = τ(T, B, θ). The algorithm generates a sample path (S
0
, . . . , S
τ
) of the ESP and
outputs the last set S
τ
. The complexity of the algorithm is O(B log m).
3.2 ESP for Growing Seed Set
Using known results on ESPs, combined with our new Lemma 2, we can derive the following
theorem. This constitutes the main tool that we will use to grow seed sets. We defer the
proof technicalities to Appendix A.
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 12
Theorem 4. Fix a parameter M ≥ 0. Let S ⊆ V be such that φ(S) ≤ γ
2
/(2400 log m).
Let S
0
⊆ S be as defined in Lemma 2, and assume that S
0
= {v} for some v ∈ S
0
.
Let S
τ
be the set returned by the ESP with stopping rule τ (T, B, θ) and parameters T =
20θ
−2
log m, B = 25M
√
T log m, and θ = γ. Then with probability at least 1/5 we have
that d(S
τ
∩ S
d
)/d(S
τ
) ≥ 3/4, and either φ(S
τ
) ≤ γ or d(S
τ
) ≥ M. The complexity of
generating this set is O(Mγ
−1
log
2
m).
4 Quantum Expansion Tester
We are now ready to construct our new quantum expansion tester, yielding the main
contribution of this paper.
Algorithm 2 Quantum Expansion Tester
Input: parameters n and d; query access to an n-node graph G with degree bound d;
expansion parameter Φ; promise parameter
Do:
1: set parameters:
t = 16d
2
Φ
−2
log n, δ = /1000, K = 200/((1 − δ)),
θ = Φ/(2d), B = 800
√
5dn
1/3
dedΦ
−1
log m, T = 320Φ
−2
d
2
log m
2: do K times
3: select a uniformly random starting node v
4: run ESP from S
0
= {v} with stopping rule τ(T, B, θ), outputting S
5: if |S| ≤ n/2 and Φ(S) ≤ Φ/2 then abort and output “reject”
6: use 2-norm estimator to create estimate a of kP
t
|Sik
to precision
0
=
p
|S|/n(1 −
p
1 + 1/256)/4 with probability 1 − δ
7: if a >
p
|S|n
−1
(1 + n
−1
) +
0
then abort and output “reject”
Output: if no “reject”, output “accept”
Theorem 5 (Quantum Expansion Tester). If d ≥ 3 and < 1/16, then Algorithm 2 is a
(Φ, ) expansion tester for c = 1/(2400(2d)
2
r
d
), with r
d
as in Lemma 3. The complexity
of the algorithm is bounded by
e
O(n
1/3
Φ
−1
d
3/2
−1
).
Proof. First we prove that if Φ(G) ≥ Φ, then the algorithm accepts with probabil-
ity at least 2/3. Thereto note that by definition of the vertex expansion, necessarily
Φ(S) ≥ Φ(G) ≥ Φ if |S| ≤ n/2. Hence the algorithm cannot falsely reject in step 5.
To exclude rejection in step 7, we use the result in [NS10, Proof of Theorem 2.1] show-
ing that if Φ(G) ≥ Φ then for all nodes v ∈ V and time t ≥ 16d
2
Φ
−2
log n it holds
that kP
t
|vik ≤
p
n
−1
(1 + n
−1
). This allows to bound kP
t
|Sik ≤ |S|
−1/2
P
s∈S
kP
t
|sik ≤
p
|S|n
−1
(1 + n
−1
). Using the 2-norm estimator from Lemma 5, the estimate a will with
probability 1 − δ be such that a ≤
p
|S|n
−1
(1 + n
−1
) +
0
. Step 7 will therefore reject
falsely only with probability at most δ. The total probability of a faulty rejection can
then be bounded by Kδ < 1/3. Since the algorithm accepts if it never rejects, it will
correctly accept the graph with probability at least 2/3.
Next we prove that if G is -far from having expansion ≥ cΦ
2
log
−1
(dn), then the
algorithm rejects with probability at least 2/3. Thereto we use Lemma 3 from Section
2.4.1, which states that in this case there exist a “bad” subset A, with (1 + )n/2 ≥ |A| ≥
n/12, such that
Φ(A) < r
d
cΦ
2
log
−1
(dn) =
1
2400
Φ
2d
2
1
log(dn)
. (4)
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 13
From A, we can define the diffusion core A
d
and the subset A
0
⊆ A
d
as in Lemma 2, which
states that d(A
0
) > d(A)/3 and hence |A
0
| ≥ |A|/3. The initial node v will hence be in A
0
with probability at least |A|/(3n) ≥ /36.
Conditioning on v ∈ A
0
, we can analyze the ESP output set S using Theorem 4. We
choose M = dn
1/3
de. Using the bound (4), which by (3) implies the same upper bound
for φ(A), S will with probability at least 1/5 be such that (i) d(S ∩ A
d
) ≥ 3d(S)/4, and
therefore |S ∩A
d
| ≥ 3|S|/4, and (ii) either φ(S) ≤ Φ/(2d) or d(S) ≥ M. If φ(S) ≤ Φ/(2d)
and |S| ≤ n/2, then we have a proof that G has vertex expansion Φ(G) ≤ Φ/2, and
hence we reject the graph in step 5. To see this, simply note that φ(S) ≤ Φ/(2d) implies
that Φ(S) ≤ Φ/2 (again by (3)). In any other case, we know that d(S) ≥ M and hence
|S| ≥ M/d. Given such a set S, consider the uniform distribution π
S
over S. Since
|S ∩ A
d
| ≥ 3|S|/4, we know that π
S
has a 3/4-overlap with A
d
. By the second bullet of
Lemma 3 this implies that for all t ≤ log(dn)/(2r
d
cΦ
2
) = 1200(2d)
2
log(dn)Φ
−2
,
kP
t
π
S
k ≥
v
u
u
t
1
n
1 + 4
3γ
4
−
1 +
2
2
!
≥
s
1
n
1 +
1
256
.
using that γ = 3/4 and ≤ 1/16. By Lemma 5, the estimate a will then with probability
1 − δ be such that a ≥
p
|S|n
−1
p
1 + 1/256 −
0
. If
0
≤
p
|S|n
−1
(
p
1 + 1/256 − 1)/4,
then this is strictly larger than
p
|S|n
−1
(1 + n
−1
) +
0
for sufficiently large n, allowing to
correctly reject the graph with probability at least 1 − δ.
Now we can bound the total probability of correctly rejecting the graph in a single
iteration. Thereto we multiply the probability that v ∈ A
0
(≥ /36), the ESP process
succeeds (≥ 1/5) and the 2-norm estimator succeeds (≥ 1 − δ), yielding a total rejection
probability of at least p = (1−δ)/180. The total probability of correctly rejecting at least
once in K iterations is therefore at least 1 − (1 − p)
K
. Using the elementary inequality
(1 − p)
1/p
< 1/e for any 0 < p ≤ 1, we can lower bound the rejection probability as
1 − (1 − p)
K
> 1 −
1
e
Kp
≥
2
3
,
provided that K ≥ ln(3)/p = 180 ln(3)/((1 − δ)), which is ensured by our choice of K.
This concludes the proof that Algorithm 2 is a (Φ, )-expansion tester.
Towards bounding the complexity of the algorithm, we consider a single iteration
of the for-loop. By Theorem 4, the complexity of simulating the ESP in step 4 is
O(Mθ
−1
log
2
(dn)), which is O(n
1/3
d
2
Φ
−1
log
2
(dn)). By Lemma 5, the (
0
, δ) 2-norm esti-
mator in step 6 has complexity
e
O(t
1/2
d
1/2
0−1
log δ
−1
) ∈
e
O(n
1/3
d
3/2
Φ
−1
log
−1
).
Since we iterate the for-loop K ∈ O(
−1
) times, this gives the claimed complexity.
Acknowledgements
This work greatly benefited from discussions and comments by Alain Sarlette, Anthony
Leverrier, Ronald de Wolf and André Chailloux, as well as from comments and suggestions
by multiple anonymous referees. Most of the work was done while part of the CWI-
Inria International Lab. We acknowledge support from the QuantERA ERA-NET Cofund
in Quantum Technologies implemented within the European Union’s Horizon 2020 Pro-
gramme (QuantAlgo project) and from the Belgian Fonds de la Recherche Scientifique -
FNRS under grant no R.50.05.18.F (QuantAlgo).
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 14
References
[ACL06] Reid Andersen, Fan R.K. Chung, and Kevin Lang. Local graph partition-
ing using PageRank vectors. In Proceedings of the 47th IEEE Symposium on
Foundations of Computer Science (FOCS), pages 475–486. IEEE, 2006. doi:
10.1109/FOCS.2006.44
[ACL11] Andris Ambainis, Andrew M. Childs, and Yi-Kai Liu. Quantum property test-
ing for bounded-degree graphs. In Approximation, Randomization, and Com-
binatorial Optimization. Algorithms and Techniques, pages 365–376. Springer,
2011. doi: 10.1007/978-3-642-22935-0_31
[AGJK20] Andris Ambainis, András Gilyén, Stacey Jeffery, and Martins Kokainis.
Quadratic speedup for finding marked vertices by quantum walks. In Pro-
ceedings of the 52nd ACM Symposium on Theory of Computing (STOC), pages
412–424. ACM, 2020. doi: 10.1145/3357713.3384252
[AGPT16] Reid Andersen, Shayan Oveis Gharan, Yuval Peres, and Luca Trevisan. Al-
most optimal local graph clustering using evolving sets. Journal of the ACM,
63(2):15, 2016. doi: 10.1145/2856030
[Amb07] Andris Ambainis. Quantum walk algorithm for element distinctness.
SIAM Journal on Computing, 37(1):210–239, 2007. doi: 10.1137/
S0097539705447311
[AP09] Reid Andersen and Yuval Peres. Finding sparse cuts locally using evolving sets.
In Proceedings of the 41st ACM Symposium on Theory of Computing (STOC),
pages 235–244. ACM, 2009. doi: 10.1145/1536414.1536449
[A19] Simon Apers. Quantum walk sampling by growing seed sets. In Proceedings
of the 27th European Symposium on Algorithms (ESA), volume 144 of Leibniz
International Proceedings in Informatics (LIPIcs), pages 9:1–9:12. Springer,
2019. doi: 10.4230/LIPIcs.ESA.2019.9
[AS19] Simon Apers and Alain Sarlette. Quantum fast-forwarding Markov chains and
property testing. Quantum Information and Computation, 19(3&4):181–213,
2019. doi: 10.5555/3370245.3370246.
[CKK
+
18] Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, and
Yuval Peres. Testing graph clusterability: Algorithms and lower bounds. In
Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer
Science. IEEE, 2018. doi: 10.1109/FOCS.2018.00054
[CPS15] Artur Czumaj, Pan Peng, and Christian Sohler. Testing cluster structure of
graphs. In Proceedings of the 47th ACM Symposium on Theory of Computing
(STOC), pages 723–732. ACM, 2015. doi: 10.1145/2746539.2746618
[CS10] Artur Czumaj and Christian Sohler. Testing expansion in bounded-degree
graphs. Combinatorics, Probability and Computing, 19(5-6):693–709, 2010. doi:
10.1017/S096354831000012X
[GR02] Oded Goldreich and Dana Ron. Property testing in bounded degree graphs.
Algorithmica, 32(2):302–343, 2002. doi: 10.1007/s00453-001-0078-7
[GR11] Oded Goldreich and Dana Ron. On testing expansion in bounded-degree
graphs. In Studies in Complexity and Cryptography. Miscellanea on the In-
terplay between Randomness and Computation, pages 68–75. Springer, 2011.
doi: 10.1007/978-3-642-22670-0_9
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 15
[HLW06] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their
applications. Bulletin of the American Mathematical Society, 43(4):439–561,
2006. doi: 10.1090/S0273-0979-06-01126-8
[KP17] Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems.
In Proceedings of the 8th Innovations in Theoretical Computer Science Confer-
ence (ITCS), pages 49:1–49:21. Schloss Dagstuhl–Leibniz-Zentrum fuer Infor-
matik, 2017. doi: 10.4230/LIPIcs.ITCS.2017.49
[KS11] Satyen Kale and Comandur Seshadhri. An expansion tester for bounded degree
graphs. SIAM Journal on Computing, 40(3):709–720, 2011. doi: 10.1137/
100802980
[LPW17] David A Levin, Yuval Peres, and Elizabeth L Wilmer. Markov chains and
mixing times. American Mathematical Society, 2017. doi: 10.1090/mbk/058
[LR99] Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems
and their use in designing approximation algorithms. Journal of the ACM,
46(6):787–832, 1999. doi: 10.1145/331524.331526
[LRV13] Anand Louis, Prasad Raghavendra, and Santosh Vempala. The complexity of
approximating vertex expansion. In 2013 IEEE 54th Annual Symposium on
Foundations of Computer Science, pages 360–369. IEEE, 2013. doi: 10.1109/
FOCS.2013.46
[MdW16] Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing.
Theory of Computing Library Graduate Surveys, (7):1–81, 2016. doi: 10.4086/
toc.gs.2016.007
[MP05] Ben Morris and Yuval Peres. Evolving sets, mixing and heat kernel bounds.
Probability Theory and Related Fields, 133(2):245–266, 2005. doi: 10.1007/
s00440-005-0434-7
[NS10] Asaf Nachmias and Asaf Shapira. Testing the expansion of a graph. Information
and Computation, 208(4):309, 2010. doi: 10.1016/j.ic.2009.09.002
[OSV12] Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. Vishnoi. Approximating
the exponential, the Lanczos method and an
e
O(m)-time spectral algorithm for
balanced separator. In Proceedings of the 44th ACM Symposium on Theory of
Computing (STOC), pages 1141–1160. ACM, 2012. doi: 10.1145/2213977.
2214080
[ST13] Daniel A. Spielman and Shang-Hua Teng. A local clustering algorithm for
massive graphs and its application to nearly linear time graph partitioning.
SIAM Journal on Computing, 42(1):1–26, 2013. doi: 10.1137/080744888
[Wat01] John Watrous. Quantum simulations of classical random walks and undirected
graph connectivity. Journal of Computer and System Sciences, 62(2):376–391,
2001. doi: 10.1006/jcss.2000.1732
A Proof of ESP Algorithm
In this appendix we provide the proof of Theorem 4. We make use of several known
properties that can be attributed to the output set:
• Size: The cost of simulating the process is related to the size of the output set.
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 16
Lemma 6 ([AGPT16, Theorem 5.4]). For any starting set S
0
and any stopping time
τ that is upper bounded by T , it holds that
E[cost
τ
/d(S
τ
)] ≤ 1 + 4
p
T log m.
• Overlap: If a random walk has a high probability of staying inside a certain set, then
with high probability the ESP will also largely remain inside that set.
Lemma 7 ([AGPT16, Lemma 4.3]). Consider any set S ⊆ V, a starting set S
0
= {v}
for some v ∈ S, and an integer T ≥ 0. Then the following holds for all β > 0:
P
min
t≤T
d(S
t
∩ S)/d(S
t
) ≥ 1 − β P(τ
v
(S
c
) ≤ T )
≥ 1 − 1/β.
• Conductance: After T steps, the ESP encounters with high probability a set of
conductance
e
O(T
−1/2
).
Lemma 8 ([AP09, Corollary 1]). Fix any integer T , and let θ
T
=
p
4T
−1
log m.
For any starting set S
0
and constant c ≥ 0, it holds that
P
min
t<T
φ(S
t
) ≤
√
c θ
T
≥ 1 − 1/c.
Using these lemmas, combined with our Lemma 2, we can prove the theorem below. It
corresponds to Theorem 4 when setting the parameters α = 5 and β = 5/2.
Theorem 6. Fix constants α, β > 0 and a parameter M ≥ 0. Let S ⊆ V be such that
φ(S) ≤
1
480α
γ
2
log m
.
Let S
0
⊆ S be as defined in Lemma 2, and assume that S
0
= {v} for some v ∈ S
0
. Let S
τ
be
the set returned by the ESP with stopping rule τ (T, B, θ) and parameters T = 4αθ
−2
log m,
B = 5αM
√
T log m, and θ = γ. Then with probability at least 1 − 2α
−1
− β
−1
we have
that
d(S
τ
∩ S
d
)
d(S
τ
)
≥ 1 − β/10,
and either
φ(S
τ
) ≤ γ or d(S
τ
) ≥ M.
The complexity of generating this set is O(Mγ
−1
log
2
m).
Proof. Let X denote the event that d(S
τ
∪ S
d
)/d(S
τ
) ≥ 1 − β/10, and Y the event that
φ(S
τ
) ≤ γ or d(S
τ
) ≥ M. We will show that P(X) ≥ 1 − β
−1
and P(Y ) ≥ 1 − 2α
−1
, so
that by the union bound we find that P(X ∩Y ) ≥ P(X)+P(Y )−1 ≥ 1−2α
−1
−β
−1
. This
proves the statements on the output set. The complexity statement follows from Theorem
3.
Towards bounding P(X) we combine Lemma 7 with Lemma 2. Since v ∈ S
0
, we know
that
P(τ
v
(S
c
d
) ≤ (120φ(S))
−1
) ≤ 1/10.
Our assumption on φ(S) implies that T ≤ (120φ(S))
−1
, and so by Lemma 7 we get that
P
min
t≤T
d(S
t
∩ S
d
)/d(S
t
) ≥ 1 − β/10
≥ 1 − β
−1
.
Since τ ≤ T , the left-hand side lower bounds P(X), so that P(X) ≥ 1 − β
−1
.
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 17
Towards bounding P(Y ), we condition it on the possible stopping rule outcomes:
P(Y ) = P(Y |φ(S
τ
) ≤ θ) P(φ(S
τ
) ≤ θ) + P(Y |cost
τ
> B) P(cost
τ
> B)
+ P(Y |τ = T ) P(τ = T ).
Since θ = γ we know that P(Y |φ(S
τ
) ≤ θ) = 1. Next we wish to bound the second term by
using Lemma 6. In combination with Markov’s inequality this states that P(Z
α
) ≤ 1/α,
where we let Z
α
denote the event that
cost
τ
/d(S
τ
) ≥ α(1 + 4
p
T log m) = α + 4B/(5M).
If we lower bound P(Z
α
) ≥ P(Z
α
|cost
τ
> B) P(cost
τ
> B), then we find P(Z
α
|cost
τ
>
B) P(cost
τ
> B) ≤ α
−1
. With
¯
Z
α
the negation of Z
α
, this leads to the bound
P(
¯
Z
α
|cost
τ
> B) P(cost
τ
> B) ≥ P(cost
τ
> B) − α
−1
.
Now if both cost
τ
> B and
¯
Z
α
hold, then
d(S
τ
) >
cost
τ
α + 4B/(5M )
>
B
α + 4B/(5M )
> M,
using the bound B > 5αM. As a consequence, if both cost
τ
> B and Z
α
hold, then also
Y holds, and so P(Y |cost
τ
> B) ≥ P(Z
α
cost
τ
> B). This gives the desired bound
P(cost
τ
> B) P(Y |cost
τ
> B) ≥ P(cost
τ
> B) − α
−1
. (5)
Finally we will upper bound P(τ = T ) using Lemma 8. For c = α this states that
P
min
t<T
φ(S
t
) ≤ γ
≥ 1 − α
−1
.
Since min
t<T
φ(S
t
) ≤ γ implies that τ < T , this shows that
P(τ = T ) ≤ 1 − P
min
t<T
φ(S
t
) ≤ γ
≤ α
−1
. (6)
If now we combine the bounds (5) and (6) we get the final bound on P(Y ):
P(Y )
(5)
≥ P(φ(S
τ
) ≤ θ) + P(cost
τ
> B) − α
−1
≥ 1 − P(τ = T ) − α
−1
(6)
≥ 1 − 2α
−1
.
Accepted in Quantum 2020-09-10, click title to verify. Published under CC-BY 4.0. 18