Simon Apers
email: simon.apers@inria.fr

Alain Sarlette
email: alain.sarlette@inria.fr

QUANTUM FAST-FORWARDING: MARKOV CHAINS AND GRAPH PROPERTY TESTING

Keywords: quantum algorithms, quantum walks, property testing

We introduce a new tool for quantum algorithms called quantum fast-forwarding (QFF). The tool uses quantum walks as a means to quadratically fast-forward a reversible Markov chain. More specifically, with P the Markov chain transition matrix and D = √ P • P T its discriminant matrix (D = P if P is symmetric), we construct a quantum walk algorithm that for any quantum state |v and integer t returns a quantum state ǫ-close to the state D t |v / D t |v . The algorithm uses

expected reflections around |v . This shows that quantum walks can accelerate the transient dynamics of Markov chains, complementing the line of results that proves the acceleration of their limit behavior.

We show that this tool leads to speedups on random walk algorithms in a very natural way. Specifically we consider random walk algorithms for testing the graph expansion and clusterability, and show that we can quadratically improve the dependency of the classical property testers on the random walk runtime. Moreover, our quantum algorithm exponentially improves the space complexity of the classical tester to logarithmic. As a subroutine of independent interest, we use QFF for determining whether a given pair of nodes lies in the same cluster or in separate clusters. This solves a robust version of s-t connectivity, relevant in a learning context for classifying objects among a set of examples. The different algorithms crucially rely on the quantum speedup of the transient behavior of random walks.

Introduction and Summary

Quantum walks (QWs) have been shown to provide a speedup over classical Markov chains in a variety of settings. In the class of search problems, there exist quantum walk algorithms that accelerate tasks such as detecting element distinctness [START_REF] Ambainis | Quantum walk algorithm for element distinctness[END_REF], finding triangles [START_REF] Magniez | Quantum algorithms for the triangle problem[END_REF], and hitting marked elements [START_REF] Childs | Exponential algorithmic speedup by a quantum walk[END_REF][START_REF] Szegedy | Quantum speed-up of Markov chain based algorithms[END_REF][START_REF] Krovi | Quantum walks can find a marked element on any graph[END_REF]. In the class of sampling problems, there exist quantum walk algorithms that speed up mixing on graphs [START_REF] Ambainis | One-dimensional quantum walks[END_REF][START_REF] Aharonov | Quantum walks on graphs[END_REF][START_REF] Richter | Quantum speedup of classical mixing processes[END_REF] and simulated annealing [START_REF] Somma | Quantum simulations of classical annealing processes[END_REF][START_REF] Wocjan | Speedup via quantum sampling[END_REF], and allow for quantum state generation [START_REF] Aharonov | Adiabatic quantum state generation and statistical zero knowledge[END_REF]. A broader overview is given in the surveys by Ambainis [START_REF] Ambainis | Quantum walks and their algorithmic applications[END_REF] and Santha [START_REF] Santha | Quantum walk based search algorithms[END_REF].

In this work we further develop this list by showing that quantum walks can be used in a very natural way to speed up random walk algorithms for graph property testing. Central to this result is a new tool which we call quantum walk fast-forwarding, allowing to quadratically fast-forward the full dynamics of a reversible Markov chain. Whereas most existing quantum walk algorithms build on a quadratic speedup towards the Markov chain limit behavior, quantum fast-forwarding allows to accelerate the transient dynamics as well. This feature is crucial towards speeding up the classical algorithms for property testing.

Quantum Walk Fast-Forwarding

Many of the above mentioned algorithms are to some extent preceded and inspired by the work of Watrous [START_REF] Watrous | Quantum simulations of classical random walks and undirected graph connectivity[END_REF]. In this work, he introduced quantum walks as a means to quantum simulate random walks as a superposition on a quantum computer, without resorting to intermediate measurements. With P the transition matrix of a random walk on a regular graph, and |v some arbitrary initial quantum state, he shows that it is possible to create the quantum state |P t v = P t |v / P t |v using O( P t |v -2 t) expected QW steps, and O( P t |v -2 ) expected copies of |v . This allowed him to quantum simulate the famous random walk algorithm by Aleliunas et al [START_REF] Aleliunas | Random walks, universal traversal sequences, and the complexity of maze problems[END_REF] for undirected graph connectivity, thereby proving that the complexity class symmetric logspace is contained in a quantum analogue of randomized logspace.

In this work we show that quantum walks can create the state |P t v quadratically faster. Indeed, we show that quantum walks can quadratically fast-forward a general reversible Markov chain. More specifically, let P be the transition matrix of a reversible Markov chain on a finite state space with discriminant matrix D = √ P • P T , where the square root and "•"-product are elementwise. Note that if P is symmetric, as in the work of Watrous, then D = P . Following the work of Szegedy [START_REF] Szegedy | Quantum speed-up of Markov chain based algorithms[END_REF], generalizing the approach in [START_REF] Watrous | Quantum simulations of classical random walks and undirected graph connectivity[END_REF], we can associate a quantum walk to P whose spectral properties are closely tied to those of P . These results provide the ground for most existing quantum walk algorithms, building on a quadratic speedup of the Markov chain limit behavior. For intermediate times however the behavior of these quantum walks will in general be unrelated to the Markov chain behavior. We prove that applying a technique called linear combination of unitaries [START_REF] Childs | Hamiltonian simulation using linear combinations of unitary operations[END_REF][START_REF] Berry | Simulating hamiltonian dynamics with a truncated taylor series[END_REF][START_REF] Van Apeldoorn | Quantum SDP-solvers: better upper and lower bounds[END_REF] on the QW operator allows to mediate this shortcoming. Indeed, combining this technique with a truncated Chebyshev expansion of the Markov chain eigenvalue function allows to simulate and accelerate the (spectral) dynamics of the Markov chain. We name this scheme quantum walk fast-forwarding (QFF), and it condenses into the following theorem: Theorem 1 (Quantum walk fast-forwarding with reflection) Given any quantum state |v , t ≥ 0 and ǫ > 0, QFFg (Algorithm 2) outputs a quantum state ǫ-close to |D t v using

O D t |v -1 t log(ǫ D t |v ) -1
expected QW steps and O( D t |v -1 ) expected reflections around |v .

Much of the previous work that builds on Szegedy's quantum walk, such as [START_REF] Szegedy | Quantum speed-up of Markov chain based algorithms[END_REF][START_REF] Somma | Quantum simulations of classical annealing processes[END_REF], relies on the quadratic improvement of the spectral gap when compared to the original Markov chain. This suffices when one is interested in the limit behavior of the dynamics. Our result, however, captures the transient dynamics which are governed by the complete spectrum of eigenvalues and corresponding eigenvectors. Similarly to both the preceding work and the existing classical algorithms, our algorithm makes use of only local information on the graph and Markov chain. Indeed we show that our algorithm allows quantum walks to simulate the dynamics of this entire classical spectrum, all the while retaining a quadratic acceleration a .

Upon completion of this work, we became aware of the recent work on quantum singular value transformation by Gilyén, Su, Low and Wiebe [START_REF] Gilyén | Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics[END_REF]. This work generalizes a wide range of advances in quantum algorithms for Hamiltonian simulation, Gibbs sampling and others. In Section 2.3 we discuss how our algorithm and its properties can alternatively be proved using this framework.

Quantum Graph Property Testing

We will show that QFF allows to very naturally speed up random walk algorithms for graph property testing. Given query access to a graph, property testing aims to determine whether it has a certain property, or whether it is far from having this property. Among the graphs with degree bound d, as we will be focusing on, two N -node graphs are said to be ǫ-far from each other if at least ǫdN edges have to be removed or added to turn one graph into the other. As an example, one can ask whether a given graph is bipartite, or whether it is at least ǫ-far from any bipartite graph. Testing bipartiteness is a relaxation as compared to effectively deciding whether the graph is bipartite or not (but possibly very close to bipartite), allowing for algorithms to work in sublinear time, i.e., scale as o(N ) with N the number of nodes in the graph. This is in contrast to the complexity of deciding properties exactly, which typically requires a number of queries at least linear in the graph size. In many realistic settings, see for instance the discussion of massive graphs in [START_REF] Spielman | A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning[END_REF], linear in the graph size is no longer computationally feasible, hence sparking the interest in sublinear time algorithms.

We will consider property testers for the expansion and the clusterability of graphs. We start by discussing the expansion tester of Goldreich and Ron (GR) [START_REF] Goldreich | On testing expansion in bounded-degree graphs[END_REF], and we prove how QFF allows to accelerate this tester. Specifically the problem is to determine whether the given graph has vertex expansion ≥ Υ, or whether it is ǫ-far from any such graph. The expansion of a graph forms a measure for the random walk mixing time over the graph. The idea behind the GR tester is therefore to run a number of random walks and count the number of pairwise collisions between the end points. If a random walk is congested in some low expansion set, then this number will be greater than when the random walk mixes efficiently. It thus forms a measure for the mixing behavior and expansion of the random walk. The runtime of their algorithm is

O(N 1/2+µ Υ -2 d 2 ǫ -1 log N ),
with the d 2 Υ -2 -factor determined by the random walk runtime.

We show that QFF very naturally allows to speed up this algorithm by fast-forwarding the random walk, and then using quantum amplitude estimation to estimate the 2-norm of the random walk probability distribution. This 2-norm will similarly be large if the random walk congests and small otherwise, thus allowing to detect whether the random walk is able to efficiently spread out or not. The runtime of our quantum algorithm is

O(N 1/2+µ Υ -1 d 3/2 ǫ -1 log N ),
a This is reminiscent of the work by Miclo and Diaconis [START_REF] Diaconis | On the spectral analysis of second-order Markov chains[END_REF] on second order Markov chains, where they show that decreasing the probability that a Markov chain backtracks improves not only the spectral gap, but the entire spectrum. In contrast to quantum walks, however, this improvement will generally only be a constant factor, rather than quadratic.

which basically follows from quadratically improving the random walk runtime. In addition, our algorithm only requires polylog(N ) space, as compared to the poly(N ) space requirements of the GR tester. We note that in preceding work Ambainis, Childs and Liu [START_REF] Ambainis | Quantum property testing for bounded-degree graphs[END_REF] have also used quantum walks to speed up the GR tester, be it in an indirect way. Roughly they apply Ambainis' element distinctness algorithm [START_REF] Ambainis | Quantum walk algorithm for element distinctness[END_REF] to speed up the search of collisions between random walk end points from N 1/2 to N 1/3 . Compared to our result, they find a complimentary speedup to O(N 1/3+µ Υ -2 d 2 ǫ -1 log N ). Due to the use of the element distinctness algorithm, their algorithm does require poly(N ) space.

We continue by discussing the more recent line of algorithms for testing graph clusterability [START_REF] Czumaj | Testing cluster structure of graphs[END_REF][START_REF] Chiplunkar | Testing graph clusterability: Algorithms and lower bounds[END_REF], forming a natural generalization of the work of Goldreich and Ron. We discuss how these techniques make use of algorithms for classifying nodes in clusters, and show how QFF allows to accelerate these algorithms. Such node classification is of relevance beyond the setting of property testing, allowing for instance nearest-neighbor classification of nodes in a learning problem.

We remark that work by Valiant and Valiant [START_REF] Valiant | Testing symmetric properties of distributions[END_REF] shows that estimating the distance in 2norm between given probability distributions is much easier and more stable than estimating the distance in 1-norm, which would otherwise be the natural choice. This underlies the fact that many graph property testing algorithms estimate the 2-distance between random walk distributions. QFF allows to cast a probability distribution p as a quantum state |p = p/ p , which is naturally associated to the 2-norm. As a consequence, QFF very naturally leads to quantum algorithms for estimating the 2-norm distance between random walk distributions, directly leading to the quantization and speedup of the above graph property testers.

Quantum Walk Fast-Forwarding

In this section we elaborate the details of the quantum walk fast-forwarding scheme. First, we formally introduce the concept and characteristics of a quantum walk associated to a reversible Markov chain. These results provide the ground for most existing quantum walk algorithms, building on a quadratic speedup of the Markov chain limit behavior. We discuss how these results fall short for speeding up any transient behavior of the Markov chain. Second, we prove how a technique called linear combinations of unitaries can be used to mediate this shortcoming. By combining this technique with a truncated Chebyshev expansion of the general Markov chain eigenvalue function, we arrive at our quantum algorithm for quantum walk fast-forwarding.

Preliminaries: Quantum Walk Schemes

In this section we review the aforementioned quantum walk scheme by Watrous [START_REF] Watrous | Quantum simulations of classical random walks and undirected graph connectivity[END_REF], and show how it gives rise to the subsequent work on quantum walk speedups by Ambainis [START_REF] Ambainis | Quantum walk algorithm for element distinctness[END_REF], Szegedy [START_REF] Szegedy | Quantum speed-up of Markov chain based algorithms[END_REF], Magniez et al [START_REF] Magniez | Search via quantum walk[END_REF], and many others. Apart from a new proof of Proposition 1, the results in this section are known, and if necessary a reader could skip the section. For the rest of this paper we will only consider simple graphs G = (V, E) with node set V and edge set E ⊆ V × V. We will also refer to a Markov chain by its stochastic transition matrix P .

Watrous Scheme

Consider a Markov chain P on a graph G = (V, E), and an initial probability distribution v over V. In early work, Watrous [START_REF] Watrous | Quantum simulations of classical random walks and undirected graph connectivity[END_REF] proposed a quantum walk scheme for creating the quantum state |P t v associated to the classical distribution P t v, defined by

P t v = 1 P t v (P t v)(j) |j , (1)
where (P t v)(j) denotes the j-th component of the probability vector P t v. For a general nonzero vector w, we will use the notation |w = 1 w w(j) |j which associates a quantum state |w to w. The quantum walk associated to P takes places on the extended or "coined" node space V = V × {♭, V} = {(i, j) | i ∈ V, j ∈ {♭, V}}, where "♭" denotes some canonical initialization state. The associated Hilbert space is H = span{|i, j | (i, j) ∈ V}. We will call the subspace H ♭ = span{|i, ♭ | i ∈ V} the flat subspace, associated to the projector Π ♭ = I ⊗ |♭ ♭|, with I the identity operator on the first register. The discrete-time quantum walk is described by a unitary operator U P on H, defined by a shift operator S and a coin toss operator V ,

U P = V † SV. (2)
We will often write U instead of U P when the context allows it. The coin toss operator is defined as

V = i |i i| ⊗ V i , where V i is such that V |i, ♭ = |i ⊗ V i |♭ = |i ⊗ |ψ i = |i ⊗ j P (j, i) |j . (3)
By the design of the QW scheme, as we will see later, it suffices to characterize the action of V i on the state |♭ . The operators V i can then be arbitrarily completed into unitary matrices. The shift operator is defined by the permutation |i, j → S |i, j = |j, i , (i, j) ∈ E, |i, j , otherwise, and S |i, ♭ = S |i, ♭ . It is now easy to prove the below lemma, stating that the restriction of U to the flat subspace implements the discriminant matrix

D = √ P • P T ,
with the square root and "•"-product elementwise. The discriminant matrix is closely related to the original Markov chain P , and if P is reversible then they share the same eigenvalues. We will often write D |v, ♭ as shorthand for (D ⊗ I) |v, ♭ .

Lemma 1 ( [START_REF] Watrous | Quantum simulations of classical random walks and undirected graph connectivity[END_REF]) For any quantum state |v, ♭ , it holds that

Π ♭ U |v, ♭ = D |v, ♭ .
Proof. This directly follows from the fact that for any node i it holds that U |i, ♭ = j P (i, j)P (j, i) |j, ♭ + |ψ ⊥ , where |ψ ⊥ is some state perpendicular to the flat subspace H ♭ . By linearity, the proposition follows for general |v, ♭ . This gives rise to an easy QW algorithm for creating |D t v . Namely, do t times: (i) apply a single step of the QW U , (ii) perform the measurement corresponding to the measurement operators Π ♭ and I -Π ♭ . If each of the measurements returns "♭", which happens with a probability

D t |v 2 D t-1 |v 2 D t-1 |v 2 D t-2 |v 2 . . . D |v 2 |v 2 = D t |v 2 ,
then the output state is |D t v, ♭ . For symmetric P , as in Watrous' original paper, it holds that D = P , and so this approach effectively returns the quantum state |P t v that we were looking for. It requires t QW steps and succeeds with a probability D t |v 2 .

Quadratically Improved Spectrum

The main idea of our new QFF tool is that we can quadratically accelerate the number of QW steps required: we can create the state |D t v using O( √ t) QW steps, succeeding with the same probability D t |v 2 . To do so we make use of work that followed up on the QW approach by Watrous, mainly initiated by Ambainis [START_REF] Ambainis | Quantum walk algorithm for element distinctness[END_REF] and Szegedy [START_REF] Szegedy | Quantum speed-up of Markov chain based algorithms[END_REF] with the aim of accelerating classical search problems. We will discuss how in a certain sense this operator quadratically improves the Markov chain spectrum, yet falls short of speeding up its full dynamics. In the next section we then present our more fine-grained scheme that resolves this issue.

They proposed an alternative QW, essentially adding a reflection around the flat subspace H ♭ to the QW operator U by Watrous:

W = R ♭ U = (2Π ♭ -I)U. (4)
Their key insight is captured in the following proposition, for which we provide a new proof which explicitly builds on the insight from Watrous' work. We will denote by T t the t-th Chebyshev polynomial of the first kind.

Proposition 1 ([4]

) For any |v, ♭ , it holds that

Π ♭ W t |v, ♭ = T t (D) |v, ♭ .
As a consequence, if (cos θ, |v ) is an eigenpair of D, then

Π ♭ W t |v, ♭ = T t (cos θ) |v, ♭ = cos(tθ) |v, ♭ .
Proof. We easily find a recursion formula for Π ♭ W t :

Π ♭ W t = Π ♭ R ♭ U (2Π ♭ -I)U W t-2 = 2Π ♭ U (Π ♭ W t-1 ) -Π ♭ W t-2
using the fact that Π ♭ R ♭ = Π ♭ , and

U † = U so that U 2 = U U † = I. Since Π ♭ W 0 = Π ♭ and Π ♭ W = Π ♭ U
, this shows that we can express Π ♭ W t as a polynomial in Π ♭ U . The Chebyshev polynomials of the first kind T t are defined by

T 0 (x) = 1, T 1 (x) = x, T t (x) = 2xT t-1 (x) -T t-2 (x). Setting x = Π ♭ U and T 0 (Π ♭ U ) = Π ♭ , this shows that we can express Π ♭ W t as Π ♭ W t = T t (Π ♭ U ).
From Lemma 1 we know that (Π ♭ U ) t |v, ♭ = D t |v, ♭ , and therefore

Π ♭ W t |v, ♭ = T t (D) |v, ♭ .
Using the geometric definition of T t , T t (cos θ) = cos(tθ), we see that if D |v, ♭ = cos θ |v, ♭ then

Π ♭ W t |v, ♭ = T t (cos θ) |v, ♭ = cos(tθ) |v, ♭ .
This proposition constitutes the basis from which most of the aforementioned quantum algorithms start, and it will be the basis from which this work starts. The gist of the speedup comes from comparing the original action of D t on an eigenpair (cos θ, |v ), D t |v, ♭ = cos t (θ) |v, ♭ , with the action of Π ♭ W t , Π ♭ W t |v, ♭ = cos(tθ) |v, ♭ . Taylor expanding the respective eigenvalue functions g t (θ) = cos t (θ) and f t ′ (θ) = cos(t ′ θ) yields

g t (θ) = 1 - tθ 2 2 + O(t 2 θ 4 ), whereas f t ′ (θ) = 1 - t ′2 θ 2 2 + O(t ′4 θ 4 ).
Setting t ′ = √ t, we see that both expressions are equal up to second order in t. This suggests that the quantum walk quadratically fast-forwards the Markov chain, and so

Π ♭ W √ t ≈ Π ♭ D t .
This observation underlies a range of quantum walk speedup results which are mainly concerned with accelerating the Markov chain asymptotics, where one is interested in the limit regime lim t→∞ P t v = π and one wishes to approximate the quantum state |π . In these cases, the timescale for the classical Markov chain is for instance set by the inverse of the spectral gap 1 δ = 1 1-λ2 (for mixing tasks and Gibbs sampling, see [START_REF] Somma | Quantum simulations of classical annealing processes[END_REF][START_REF] Poulin | Sampling from the thermal quantum gibbs state and evaluating partition functions with a quantum computer[END_REF]), or by the sum of the inverses 1 1-λ k (for hitting tasks, see [START_REF] Szegedy | Quantum speed-up of Markov chain based algorithms[END_REF]), where {λ k = cos θ k } denotes the set of eigenvalues of P . For these purposes, the low order conclusions from the above expansion generally suffice to achieve a quantum walk speedup in generating |π .

The main issue with the above analysis is that it breaks down for t and eigenvalues θ such that tθ ≈ 1: g t (θ) and f t (θ) start to diverge from each other, thus preventing the quantum walk from simulating the full dynamics of the Markov chain. As the main contribution in the following section we will construct a more involved and fine-grained quantum walk scheme whose eigenvalue function closely approximates the Markov chain eigenvalue function g t (θ) for all values of t and θ, without losing the quadratic fast-forward.

Quantum Fast-Forwarding Algorithm

In this section we develop our main tool: a quantum walk algorithm for quantum simulating Markov chains quadratically faster than the original dynamics. Thereto we will make use of the concept of linear combinations of unitaries. We will use this technique to manipulate the eigenvalues of the quantum walk such that they better approximate the Markov chain eigenvalues.

LCU and Chebyshev Expansion

We can create some wiggle room on the implementation of the quantum walk Π ♭ W t , and therefore on its eigenvalue function, by implementing linear combinations of Π ♭ W t for different t. A similar approach has been used in for instance [START_REF] Childs | Hamiltonian simulation using linear combinations of unitary operations[END_REF][START_REF] Berry | Simulating hamiltonian dynamics with a truncated taylor series[END_REF] for Hamiltonian simulation and in [START_REF] Van Apeldoorn | Quantum SDP-solvers: better upper and lower bounds[END_REF] for optimizing quantum SDP solvers, where they call this technique linear combination of unitaries (LCU). We extract the below Lemma 2 from this existing work, and elaborate its details for completeness. Below the lemma we discuss how it can be used for our purpose.

The lemma shows how to implement a linear combination

τ l=0 q l Π ♭ W l ,
where we assume that q l ≥ 0 and q l = 1. To do so, we will again enlarge the state space from H V to H V×[τ ] , with [τ ] = {0, 1, 2, . . . , τ }. We will identify |0 = |♭ and call the span of states |j, ♭, ♭ ≡ |j, ♭♭ , j ∈ V, the flat subspace of H V× [τ ] . The projector Π ♭ will either denote the projector on the flat subspace of H V or H V×[τ ] , whichever it is will be clear from the context. The construction is very similar to the Watrous quantum walk scheme. It builds on a coin toss V q on H V×[τ ] , defined by the coefficients q l as

V q |ψ, ♭ = τ l=0 √ q l |ψ, l .
Then the controlled W-operator W ctrl = τ l=0 W l ⊗ |l l| is applied which, conditioned on the integer l in the last register, applies the operator W l :

W ctrl V q |ψ, ♭ = W ctrl τ l=0 √ q l |ψ, l = τ l=0 √ q l W l |ψ, l .
Finally, as in the Watrous QW, the operator V † q is applied, returning a state

V † q W ctrl V q |ψ, ♭ = τ l=0 q l W l |ψ, ♭ + |ψ ⊥ , (5)
where |ψ ⊥ is some quantum state perpendicular to the flat subspace. This leads to the following lemma, where we set

W τ = V † q W ctrl V q . Lemma 2 (LCU) For any |v, ♭♭ , it holds that Π ♭ W τ |v, ♭♭ = τ l=0 q l Π ♭ W l |v, ♭ ⊗ |♭ = τ l=0 q l T l (D) |v ⊗ |♭♭ .
Implementing the operator W τ requires O(τ ) QW steps.

Proof. From [START_REF] Krovi | Quantum walks can find a marked element on any graph[END_REF] we see that

Π ♭ V † q W ctrl V q |v, ♭♭ = τ l=0 q l Π ♭ W l |v, ♭ ⊗ |♭ .
Combined with Proposition 1, and by linearity, this proves the inequality. In for instance [START_REF] Nielsen | Quantum computation and quantum information[END_REF][START_REF] Berry | Black-box hamiltonian simulation and unitary implementation[END_REF] it is discussed that the operator W ctrl can be implemented in O(τ ) QW steps, and the local coin tosses V q and V † q require no QW steps.

This lemma shows that if we apply the operator W τ on |v, ♭♭ , and we perform a measurement {Π ♭ , I -Π ♭ }, then we retrieve the state

τ l=0 q l T l (D) |v ⊗ |♭♭ (up to normalization)
with a probability τ l=0 q l T l (D) |v 2 . The corresponding eigenvalue function is then

ft (θ) = τ l=0
q l cos(lθ).

In the following we will choose the coefficients q l so that ft ′ (θ) approximates the original eigenvalue function g t (θ) = cos t (θ) for t ′ ∈ O( √ t). For this purpose we can use the Chebyshev expansion of g t . Indeed, from for instance [START_REF] Gil | Numerical methods for special functions[END_REF] we know that

x t = t l=0 p l T l (x),
where p l represents the probability that |X t | = l for X t a t step random walk starting in the origin:

p l = P(|X t | = l) =            1 2 t-1 t t-l 2 l > 0, t = l mod 2, 1 2 t t t 2 l = 0, t = 0 mod 2, 0 elsewhere. ( 6
)
Again using the geometric definition of the Chebyshev polynomials, T t (cos(θ)) = cos(tθ), and setting x = cos(θ), this implies that g t can be exactly expanded into the eigenfunctions f t :

g t (θ) = cos t (θ) = t l=0 p l cos(lθ) = t l=0 p l f t (lθ). ( 7
)
Using the above lemma we can now choose q l = p l to exactly simulate the original dynamics.

The problem is that in this case τ = t, and implementing W τ therefore requires O(t) QW steps, giving no speedup with respect to the simple quantum simulation scheme. We can resolve this by noting that p l approaches a normal distribution with standard deviation Θ( √ t), so that we can approximate it exponentially well by its support on a O( √ t) interval, as we elaborate in the below lemma.

Lemma 3 Let ǫ > 0. If C ≥ 2 ln 2 ǫ then for all θ cos t (θ) - ⌈ √ Ct⌉ l=0 p l cos(lθ) ≤ ǫ. Proof. Let t ′ = ⌈ √ Ct⌉.
The proof comes down to bounding the quantity p >t ′ = t l=t ′ +1 p l . Indeed, by [START_REF] Aharonov | Quantum walks on graphs[END_REF] we can easily calculate that cos t (θ) -

t ′ l=0 p l cos(lθ) ≤ p >t ′ ,
so that it suffices to prove that p >t ′ ≤ ǫ. We can bound p >t ′ since it represents the probability that |X t | > t ′ where X t is a t step random walk X t . By Hoeffding's inequality we know that

p >t ′ ≤ 2 exp -t ′2 /(2t) . For t ′ = ⌈ √ Ct⌉ and C ≥ 2 ln 2 ǫ this shows that p >⌈ √ Ct⌉ ≤ ǫ, which proves the lemma.
This lemma shows that it is possible to pointwise approximate the original eigenvalue function cos t (θ), up to an error ǫ, using the truncated Chebyshev expansion

g t τ (θ) = τ l=0 p l cos(lθ) for τ ∈ O( √ t log 1 ǫ ).
We note that a similar approximation in combination with LCU was used for a different purpose in [START_REF] Berry | Exponential improvement in precision for simulating sparse hamiltonians[END_REF]. In the next section we combine this approximation lemma with the LCU lemma, leading to our quantum fast-forwarding scheme.

Quantum Fast-Forwarding Algorithm

Combining the above lemmas, we can propose our QFF algorithm. It builds on the operator W τ from Lemma 2, with coefficients q l derived from Lemma 3, so that

Π ♭ W τ |v, ♭♭ = 1 1 -p >τ τ l=0 p l Π ♭ W l |v, ♭♭ = 1 1 -p >τ τ l=0 p l T l (D) |v ⊗ |♭♭ , (8)
where the p l are defined in [START_REF] Ambainis | One-dimensional quantum walks[END_REF].

Algorithm 1 Quantum Fast-Forwarding QFF(|v , P, t, ǫ) Input: quantum state |v ∈ H V , reversible Markov chain P , t ∈ N, ǫ > 0 Do:

1: set ǫ ′ = D t |v ǫ/2 and τ = 2t ln(2/ǫ ′ ) 2: initialize the registers R 1 R 2 R 3 with the state |v, ♭♭ 3: apply the LCU operator W τ as in (8) on R 1 R 2 R 3 4: perform the measurement {Π ♭♭ , I -Π ♭♭ } 5: if outcome = "♭♭" then output "Fail" and stop Output: registers R 1 R 2 R 3
Theorem 2 (Quantum Fast-Forwarding) The QFF algorithm QFF(|v , P, t, ǫ) outputs a state ǫ-close to |D t v, ♭♭ with success probability at least (1 -ǫ) D t |v 2 . Otherwise it outputs "Fail". The algorithm uses a number of QW steps

τ ∈ O √ t log 1/2 1 ǫ D t |v . Proof. Let {(cos θ k , |v k ), 1 ≤ k ≤ |V|} be a complete orthonormal set of eigenpairs of D.
Then we can write |v = k α k |v k and the goal state

|D t v = k α k cos(θ k ) t |v k / D t |v .
From Lemma 2 we know that if we apply the operator W τ on |v, ♭♭ , and we perform a measurement {Π ♭ , I -Π ♭ }, then we retrieve the state

1 1 1-p>τ τ l=0 q l T l (D) |v 1 1 -p >τ τ l=0 q l T l (D) |v ⊗ |♭♭ = 1 τ l=0 q l T l (D) |v τ l=0 q l T l (D) |v ⊗ |♭♭
with a success probability then |ψ τ will be ǫ ′ -close to D t |v :

|ψ τ -D t |v = k τ l=0 q l cos(lθ) -cos t (θ k ) 2 • |α k | 2 ≤ ǫ ′2 k |α k | 2 = ǫ ′ .
Using standard manipulations we know that for any two nonzero vectors it holds that v/ vw/ w ≤ 2 v -w / w . As a consequence we can bound

|ψ |ψ - D t |v D t |v ≤ 2ǫ ′ D t |v = ǫ,
using the fact that we chose ǫ ′ = D t |v ǫ/2. We can now also bound the success probability using the reverse triangle inequality:

1 1 -p >τ τ l=0 p l T l (D) |v 2 ≥ τ l=0 p l T l (D) |v 2 ≥ ( D t |v -ǫ ′ ) 2 ≥ (1 -ǫ) D t |v 2 .
By Lemma 2 we know that implementing the operator W τ requires a number of QW steps

τ = √ 2t ln 1/2 4 ǫ D t |v ∈ O √ t log 1/2 1 ǫ D t |v .
This finalizes the proof.

This theorem establishes our algorithm for quantum fast-forwarding Markov chains. It winds back the quantum walk speedup of the Ambainis-Szegedy scheme on the Markov chain asymptotic behavior to the original problem of quantum simulating Markov chains for any fixed timestep, showing that we can achieve the same quadratic acceleration that is characteristic for this scheme. The success probability is proportional to D t |v 2 , so that D t |v -2 expected iterations are necessary for the scheme to succeed. In the next section we show how to quadratically improve this. We mention that the norm D t |v will be small when the Markov chain spreads out from a small set to a large set, e.g., going from a single node to the uniform distribution yields D t |v = N -1/2 . This reflects the fact that it is costly for the quantum algorithm to create a superposition over a large number of queried elements (see [START_REF] Ambainis | Symmetry-assisted adversaries for quantum state generation[END_REF] for a discussion and a more rigorous analysis of this phenomenon).

Amplitude Amplification

We can improve the success probability to a constant by replacing the final measurement in the algorithm with amplitude amplification, provided that we can reflect around the initial state |v, ♭♭ (≡ |v, ♭ , we will use the shorthand ♭ to denote ♭♭), i.e., implement the reflection operator

R v = 2 |v, ♭ v, ♭| -I.
Thereto we will use the following proposition by Brassard et al [START_REF] Brassard | Quantum amplitude amplification and estimation[END_REF], demonstrating how we can retrieve a component Π ♭ |ψ of some quantum state |ψ by performing reflections around |ψ and around the image of Π ♭ .

Proposition 2 (Amplitude amplification [START_REF] Brassard | Quantum amplitude amplification and estimation[END_REF]) This implementation of amplitude amplification requires a very good estimate of the initial success probability Π ♭ |ψ 2 to determine m. If m is chosen either too small or too large, then the guarantees on the success probability are lost, a problem often referred to as the "soufflé problem". A remedy is however proposed in [START_REF] Brassard | Quantum amplitude amplification and estimation[END_REF], in which iteratively different guesses for m are used. They show that this approach also yields a success probability ≥ 1/2, while still applying the operator (-R ψ R ♭ ) only O(1/ Π ♭ |ψ ) times. For clarity we will implicitly rely on this fact, and throughout assume that we can appropriately determine the parameter m.

Given
In our QFF algorithm we have |ψ = W τ |v, ♭ , and we wish to retrieve the component Π ♭ |ψ = Π ♭ W τ |v, ♭ . Amplitude amplification shows that we can do so with constant success probability by implementing the operator (-R ψ R ♭ ) for a number of times in Θ(1/ Π ♭ |ψ ). The reflection R ♭ = 2Π ♭ -I is considered an elementary operation on the basis states, which we can implement with a negligible cost. The following lemma shows that we can implement the reflection R ψ = 2 |ψ ψ| -I using O(τ ) QW steps.

Lemma 4

The operator R ψ can be implemented using O(τ ) QW steps and a reflection R v around the initial state |v, ♭ .

Proof. We can rewrite the reflection

R ψ = 2 |ψ ψ|-I = W τ R v W †
τ , so that we can implement the reflection by implementing the operators W τ , W † τ , and R v . To implement the operator

W † τ , we recall that W τ = V † q τ l=0 |l l| ⊗ (R ♭ U ) l V q and so W † τ = V † q τ l=0 |l l| ⊗ (U R ♭ ) l V q .
Here we also used the fact that U = V † SV with S = S † , as in (2), so that U † = U . We already discussed in Lemma 2 that a controlled operator τ l=0 |l l| ⊗ U R ♭ can be implemented in O(τ ) QW steps, so that both W τ and W † τ can be implemented in O(τ ) QW steps.

It follows that the total operator (-R ψ R ♭ ) can be implemented using O(τ ) QW steps, a reflection around the initial state |v, ♭ , and a number of elementary operations. In many cases the initial state will be an elementary basis state, so that the reflection R v will also be elementary, and the main cost boils down to O(τ R) QW steps. We can now propose the improved QFF algorithm, QFFg, in Algorithm 2. Theorem 3 proves its correctness and complexity. We note that this describes the Monte Carlo version of QFF. We can easily retrieve the Las Vegas version, as stated in Theorem 1 in the introduction, by repeating the below algorithm until it is successful. As mentioned at the end in previous section, we improve the expected number of QW steps for the QFF algorithm to succeed from Θ(

D t |v -2 √ t) to Θ( D t |v -1 √ t).
Algorithm 2 Quantum Fast-Forward with Reflections QFFg(|v , P, t, ǫ)

Input: quantum state |v ∈ H V , Markov chain P , t ∈ N, ǫ > 0 Do: 1: set ǫ ′ = D t |v ǫ/2 and τ = 2t ln(2/ǫ ′ ) 2: set m = ⌊π/(4θ)⌋, where 0 < θ ≤ π/2 s.t. sin θ = Π ♭ W τ |v 3: initialize registers R 1 R 2 R 3 with the state |v, ♭♭ 4: apply the LCU operator W τ on R 1 R 2 R 3 5: apply the operator (-R ψ R ♭ ) m = (-W τ R v W † τ R ♭ ) m
⊲ Amplitude Amplification 6: perform the measurement {Π ♭♭ , I -Π ♭♭ } 7: if outcome = "♭♭" then output "Fail" and stop

Output: registers R 1 R 2 R 3
Theorem 3 The QFFg algorithm QFFg(|v , P, t, ǫ) outputs a state ǫ-close to |D t v with success probability at least 1/2. Otherwise, it outputs "Fail". The algorithm uses Θ(1/ D t |v ) reflections around the initial state, and a number of QW steps

O(mτ ) ∈ O √ t D t |v log 1/2 1 ǫ D t |v .
Proof. The algorithm straightforwardly applies the amplitude amplification scheme on the state W τ |v, ♭ . From Proposition 2 we know that the scheme has a success probability ≥ max{1 -sin 2 θ, sin 2 θ} ≥ 1/2. The number of QW steps for implementing W τ and (-R ψ R ♭ ) m is O(τ ) respectively O(mτ ). We know that m ∈ O(1/ Π ♭ W τ |v, ♭ ), and from the proof of Theorem 2 we can bound

Π ♭ W τ |v, ♭ ≥ D t |v -ǫ ′ = (1 -ǫ/2) D t |v ∈ Θ( D t |v ) for all ǫ < 1/2.

Quantum Singular Value Transformation

After completion of this work, we were pointed to the recent work of Gilyén et al [START_REF] Gilyén | Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics[END_REF] on quantum singular value transformation. They develop a framework that generalizes and unifies the principles underlying a large number of quantum algorithms for problems such as Hamiltonian simulation, Gibbs sampling, and many more. In the following we note that an alternative derivation of our QFF algorithm and its properties can be constructed from this framework. Specifically, they consider a general projected unitary encoding of an operator A = Π U Π ′ , where Π , Π ′ are projectors and U is a unitary operator. We can see the quantum walk encoding D = Π ♭ U Π ♭ of the discriminant matrix of a Markov chain, as in Lemma 1, as a special case of such encoding. If A has a singular value decomposition A = W ΣV † , then they show that it is possible to transform the singular values of A. More precisely, given some degree-d polynomial p, they construct a quantum circuit that implements the operator W p(Σ)V † using the operators U and U † at most d times. They then cite a result from Sachdeva and Vishnoi [START_REF] Sachdeva | Faster algorithms via approximation theory[END_REF] showing that if p(Σ) = Σ d , then this polynomial can be efficiently approximated using a polynomial with degree O( √ d) (this result also follows from our Chebyshev truncation in Lemma 3). By applying their quantum singular value transformation on this approximating polynomial, we can retrieve our QFF algorithm.

Quantum Property Testing

In this section we show how QFF allows to speed up random walk algorithms for property testing on graphs. Specifically, we will consider property testers for the expansion and the clusterability of graphs. We leave it as an open question whether similar speedups can be found for other graph property testers, an interesting example of which is the recent random walk algorithm by [START_REF] Kumar | Fiding forbidden minors in sublinear time: a o(n 1/2+o(1) )-query one-sided tester for minor closed properties on bounded degree graphs[END_REF] for testing the occurrence of forbidden minors. In the first section we will discuss the expansion tester of Goldreich and Ron (GR), which they presented in later work [START_REF] Goldreich | On testing expansion in bounded-degree graphs[END_REF], and we prove how QFF allows to accelerate this tester very naturally. We compare this speedup to the preceding work by Ambainis, Childs and Liu [START_REF] Ambainis | Quantum property testing for bounded-degree graphs[END_REF], and discuss how they achieve a complementary speedup to ours. Then we discuss the more recent line of algorithms for testing graph clusterability, aimed at probing for instance the community structure of a given graph. We discuss how these testers make use of algorithms for classifying nodes in clusters, and show how QFF allows to accelerate these algorithms. Such node classification is of relevance beyond the setting of property testing, allowing for instance nearest-neighbor classification of nodes in a learning problem.

Classical Expansion Tester

To formalize the concept of a graph property tester, we must introduce the notion of oracle or query access to a graph as used throughout the literature on property testing. Query access to an N -node undirected graph with degree bound d means that we can query the graph with a string (v, i) ∈ [N ] × [d], upon which we receive either the i-th neighbor w ∈ [N ] of v, or a special symbol in case v has less than i neighbors. Clearly this model allows to perform a random walk over the graph. In addition it allows to generate a uniformly random node by simply generating a random number in [N ]. This differs from the more classical Markov chain setting where possibly we are only given a single node, and we must explore the graph in a completely local manner.

Given such query access to a graph, the task of a property tester is to determine whether the graph has a certain property or is far from any graph having that property. To formalize this, a distance measure between two N -node graphs G and G ′ is defined, equaling the number of edges that have to be added or removed from G to transform it into G ′ . With E and E ′ the edge sets of G resp. G ′ , this equals the size of the symmetric difference |E△E ′ |. We say that two N -node graphs G and G ′ with degree bound d are ǫ-far from each other if |E△E ′ | ≥ ǫN d. Given a graph and a parameter ǫ, a property tester should correctly distinguish between the graph having a certain property, and the graph being at least ǫ-far from any graph with that property (i.e., the distance between the graph and any graph with that property is ≥ ǫN d).

When given a graph that is neither, the algorithm can do whatever.

Goldreich and Ron [START_REF] Goldreich | On testing expansion in bounded-degree graphs[END_REF] studied a property tester for the expansion of a graph b . The b They actually studied a property tester for the spectral gap of a graph, for which currently there is no known sublinear algorithm. All follow-up work however considers the closely-related graph expansion.

expansion or vertex expansion of a graph G = (V, E) is defined by

min |S|≤|V|/2 |∂S c | |S| ,
where ∂S c denotes the outer boundary of S, i.e., the set of nodes in S c = V\S that have an edge going to S. For some given parameter Υ, an expansion tester should determine whether a given graph has expansion ≥ Υ, or whether it is at least ǫ-far from any such graph. GR, and the subsequent literature [START_REF] Czumaj | Testing expansion in bounded-degree graphs[END_REF][START_REF] Kale | An expansion tester for bounded degree graphs[END_REF][START_REF] Nachmias | Testing the expansion of a graph[END_REF][START_REF] Ambainis | Quantum property testing for bounded-degree graphs[END_REF], have relaxed this setting somewhat. They propose the following definition:

Definition 1 An algorithm is an (Υ, ǫ, µ)-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 ≥ Υ, then the algorithm outputs "accept" with probability at least 2/3,

• if the graph is ǫ-far from any graph having expansion ≥ cµΥ 2 , then the algorithm outputs "reject" with probability at least 2/3.

In the strict setting of property testing, the expression "≥ cµΥ 2 " in the second bullet should be replaced by "≥ Υ". Although unproven, the relaxation in this definition seems necessary to allow for efficient (sublinear) testing. GR [START_REF] Goldreich | Property testing in bounded degree graphs[END_REF] conjectured that the below Algorithm 3 is a (Υ, ǫ, µ) expansion tester. They also proved that any classical expansion tester must make at least Ω( √ N ) queries to the graph.

Algorithm 3 Graph Expansion Tester

Input: parameters N and d; query access to N -node graph G with degree bound d; expansion parameter Υ; accuracy parameter ǫ; running time parameter µ < 1/4 Do:

1: for T ∈ Θ(ǫ -1 ) times do 2:

select a uniformly random starting vertex s 3:

perform m ∈ Θ(N 1/2+µ ) independent random walks of length t ∈ Θ(d 2 Υ -2 log N ), starting in s 4:
count number of pairwise collisions between the endpoints of the m random walks 5:

if the count is greater than M ∈ Θ(N 2µ ), abort and output "reject"

Output: if no "reject", output "accept"

The intuition behind the algorithm is very clear. It builds on the use of a random walk P on the given graph, which starting from a node v jumps to any of its d v neighbors with a probability 1/(2d), and stays put otherwise:

P (u, v) =      1/(2d) (v, u) ∈ E 1 -d v /(2d) u = v 0 elsewhere. ( 9
)
This walk is lazy and symmetric, and hence converges to the uniform distribution. If the graph has vertex expansion Υ, then one can prove that the mixing time of this random walk is O(d 2 Υ -2 log N ). As a consequence, the probability distribution of the random walks in step 2 of the algorithm must be close to uniform. If p describes the probability distribution of the endpoint of a random walk starting from some fixed node, then the probability of a pairwise collision between two independent endpoints, i.e., the probability that the random walks end in the same node, is given by

p(j) 2 = p 2 .
This will be close to 1/N if p is close to uniform. If on the other hand the expansion of the graph is ≪ Υ, then random walks can get stuck in a small region, leading to an increase in the 2-norm or collision probability. It follows that the collision probability of a random walk forms a measure for the expansion of the graph. The key insight is then that, by a refinement of the birthday paradox, Θ(N 1/2+µ ) independent samples of the same random walk suffice to estimate the collision probability to within a multiplicative factor 1 + O(N -2µ ). As a consequence, it is possible to estimate the 2-norm of a t-step random walk on an N -node graph using Θ(N 1/2+µ tǫ -1 ) random walk steps. The conjecture that Algorithm 3 is an expansion tester was later resolved as the conclusion of a series of papers by Czumaj and Sohler [START_REF] Czumaj | Testing expansion in bounded-degree graphs[END_REF], Kale and Seshadhri [START_REF] Kale | An expansion tester for bounded degree graphs[END_REF] and Nachmias and Shapira [START_REF] Nachmias | Testing the expansion of a graph[END_REF], leading to the following theorem.

Theorem 4 ([39]) If d ≥ 3, then Algorithm 3 is a (Υ, ǫ, µ) expansion tester with runtime O(N 1/2+µ Υ -2 d 2 ǫ -1 log N ).
In the following section we show that we can use QFF to accelerate this tester very naturally by quantum simulating the random walks, and using quantum techniques to estimate the 2-norm.

Quantum Expansion Tester

It is possible to extend the classical query model to the quantum setting, a proper definition of which can be found in [START_REF] Montanaro | A survey of quantum property testing[END_REF][START_REF] Ambainis | Quantum property testing for bounded-degree graphs[END_REF]. For this work it suffices to know that (i) we can generate a uniformly random node as in the classical case, and (ii) we can implement a single step of the quantum walk operator as defined in (4) using O( √ d) queries to the graph, where d is the maximum degree.

To accelerate the classical tester we will quantum simulate the random walks, and then perform quantum amplitude estimation to estimate the 2-norm of the simulated random walks. Together with the aforementioned amplitude amplification scheme, the amplitude estimation scheme is described in the work by Brassard et al [START_REF] Brassard | Quantum amplitude amplification and estimation[END_REF]. It is captured by the following lemma. We note that in the original statement in [START_REF] Brassard | Quantum amplitude amplification and estimation[END_REF] the number of reflections scales as 1/δ for a success probability 1 -δ. We use standard tricks to improve this to log(1/δ).

Lemma 5 (Quantum Amplitude Estimation) Consider a quantum state |ψ and a general projector Π ♭ . Give some δ > 0, there exists a quantum algorithm that outputs an estimate a such that Π ♭ |ψ -a ≤ ǫ with probability at least 1 -δ, using O(log(1/δ)ǫ -1 ) reflections around |ψ and around the image of Π ♭ .

Proof. We can use the quantum amplitude estimation algorithm from [START_REF] Brassard | Quantum amplitude amplification and estimation[END_REF]Theorem 12] to output an ǫ ′ = ǫ/3-close estimate with success probability at least 5/6. This algorithm requires O(1/ǫ) reflections around |ψ and around the image of Π ♭ . We can boost the success probability to 1 -δ by running their algorithm T = ⌈18 ln δ -1 ⌉ times, which by Hoeffding's inequality implies that, with a probability at least 1 -δ, at least 2T /3 iterations have been successful. Therefore, with probability 1 -δ, it holds that (i) at least 2T /3 estimates lie in the interval [ Π ♭ |ψ -ǫ ′ , Π ♭ |ψ + ǫ ′ ], and therefore (ii) we can find a subset S of estimates, |S| ≥ 2T /3, all of which lie in a 2ǫ ′ -interval. This subset must overlap with the interval

[ Π ♭ |ψ -ǫ ′ , Π ♭ |ψ + ǫ ′ ].
If now we output any element of this subset S, we know that it lies in the interval [ Π ♭ |ψ -3ǫ ′ , Π ♭ |ψ + 3ǫ ′ ]. This proves that with probability 1 -δ we can output an estimate of Π ♭ |ψ with precision 3ǫ ′ = ǫ, using T runs of the quantum amplitude estimation algorithm in [START_REF] Brassard | Quantum amplitude amplification and estimation[END_REF], each of which requires O(1/ǫ) reflections around |ψ and around the image of Π ♭ . This proves the claimed statement.

We will use this amplitude estimation algorithm to estimate the 2-norm of a random walk. Thereto we recall the QFF scheme as discussed in Section 2.2.2. Note that the random walk [START_REF] Somma | Quantum simulations of classical annealing processes[END_REF] proposed in the GR tester is symmetric, so that we can simply replace the discriminant matrix D in the QFF algorithm by the random walk matrix P . Given a quantum state |s, ♭♭ , QFF applies an operator W τ so that

Π ♭ W τ |s, ♭♭ = 1 1 -p >τ τ l=0 p l T l (P ) |s ⊗ |♭♭ ≈ (P t |s ) ⊗ |♭♭ ,
as in [START_REF] Richter | Quantum speedup of classical mixing processes[END_REF], with the summation corresponding to the truncated Chebyshev expansion of P t . Implementing this operator requires O(τ ) QW steps and O(τ √ d) queries to the graph. If we set τ ∈ Θ t log(N ǫ -1 ) (replacing P t |s by its lower bound N -1/2 in Algorithm 2) then the 2-norm of 1 1-p>τ τ l=0 p l T l (P ) |v approximates the 2-norm of P t |v to precision O(ǫ). Applying quantum amplitude estimation on the state W τ |v, ♭♭ and projector Π ♭ will therefore allow to estimate the 2-norm of P t |v , as was our initial goal. This scheme is easily formalized in the below algorithm and theorem. Proof. We will prove the theorem for the algorithm parameter τ = 2t ln 8 √ N /ǫ . By this choice, and the fact that P t |s ≥ N -1/2 on any N -node graph, we can deduce from the proof of Theorem 2 that

Π ♭ W τ |s -P t |s ≤ ǫ/2.
Applying quantum amplitude estimation on Π ♭ W τ |s with a precision ǫ/2 therefore leads to an estimate of P t |s up to error ǫ. By Lemma 5 we can do so with a probability 1 -δ using O(ǫ -1 log δ -1 ) reflections around W τ |s . We can implement a single such reflection using 2τ QW steps, and a reflection around the initial state (which is a basis state and can hence be neglected).

We can compare this with the classical 2-norm tester proposed by Czumaj, Peng and Sohler [24, Lemma 3.2], building on the GR tester. For δ = 1/3 their tester requires O(t/ǫ) queries to the graph, whereas our algorithm only requires O( √ t/ǫ) queries. We can now use our quantum 2-norm tester to create a quantum tester for the graph expansion. The proof makes use of some details from the classical proof of Nachmias and Shapira [START_REF] Nachmias | Testing the expansion of a graph[END_REF].

Algorithm 5 Quantum Graph Expansion Tester

Input: parameters N and d; query access to N -node graph G with degree bound d; expansion parameter Υ; accuracy parameter ǫ; running time parameter µ < 1/4 Do:

1: set t ∈ O(d 2 Υ -2 log N ), M ∈ O(N -1/2 ), ǫ ′ ∈ O(N -1/2+µ ), δ ∈ O(ǫ) 2: for T ∈ O(ǫ -1 ) times do 3:
select a uniformly random starting node s if a > M + ǫ ′ , abort and output "reject"

Output: if no "reject", output "accept"

Theorem 6 (Quantum Graph Expansion Tester) If d ≥ 3 then Algorithm 5 is a (Υ, ǫ, µ) expansion tester. The runtime and number of queries of the algorithm are bounded by

O(N 1/2+µ d 3/2 Υ -1 ǫ -1 log(ǫ -1 ) log N ).
Proof. We will prove the theorem for the algorithm parameters

t = 16d 2 Υ -2 log N , M = N -1 (1 + N -1 ), ǫ ′ = N -1/2+µ /(16 √
2), δ = ǫ/300 and T = 90/ǫ. In each iteration the estimate a will be such that a -P t |s ≤ ǫ ′ with probability 1 -δ, and hence a 2 -P t |s 2 = (a -P t |s )(a + P t |s ) ≤ 2ǫ ′ .

Nachmias and Shapira [START_REF] Nachmias | Testing the expansion of a graph[END_REF] showed that if G has a conductance ≥ Υ, then for all nodes s it holds that

P t |s ≤ M = N -1 (1 + N -1 ).
Given such a graph, in each iteration the estimate a ≤ M + ǫ ′ with probability 1 -δ, so that the probability of a faulty rejection is at most δ per iteration. The total probability of a faulty rejection can then be bounded by T δ < 1/3.

In the negative case, [START_REF] Nachmias | Testing the expansion of a graph[END_REF] showed that there exists a constant c > 0 such that if G is ǫ-far from any graph with max degree d and conductance ≥ cµΥ 2 , then there exist at least ǫN/128 vertices s for which it holds that

P t |s ≥ N -1 (1 + 32 -1 N -2µ ).
Given such a graph, in each iteration the estimate a will now be such that a

≥ P t |s -ǫ ′ ≥ N -1 (1 + 32 -1 N -2µ ) -ǫ ′ with probability 1 -δ. To show that this quantity > M + ǫ ′ , we bound M = N -1 (1 + N -1 ) ≤ N -1/2 (1 + N -1/2 ) and N -1 (1 + 32 -1 N -2µ ) ≥ N -1/2 (1 - N -µ /(4 √ 2
)), which shows that

N -1 (1 + 32 -1 N -2µ ) -M ≥ N -1/2-µ /(4 √ 2).
This proves that indeed

N -1 (1 + 32 -1 N -2µ ) -ǫ ′ > M + ǫ ′ for ǫ ′ = N -1/2-µ /(16 √
2). As a consequence, a single iteration will correctly output a rejection with probability (1 -δ)ǫN/128. The total probability of correctly rejecting at least once is therefore lower bounded by T (1 -δ)ǫ/128 ≥ 2/3. This concludes the proof that Algorithm 5 is a (Υ, ǫ, µ) graph expansion tester. The required number of QW steps is given by T times the number required by the 2-norm tester, which by Theorem 5 is

O √ t ǫ ′ log 1 δ log 1/2 N ǫ ′ ∈ O dΥ -1 log 1/2 N N 1/2+µ log 1 ǫ log 1/2 N 1+µ .
We can implement a single QW step using O( √ d) graph queries, so that we find the claimed bound. We recall that the classical GR tester has a runtime

O(N 1/2+µ d 2 Υ -2 ǫ -1 log N ).
Up to the log(ǫ -1 )-factor we improve this runtime with a factor Υ -1 , which basically follows from the fact that we quadratically accelerate the random walk runtime to t ∈ Θ(Υ -1 ). There exist bounded-degree graphs for which Υ ∈ Ω(1/N ), so that in some cases we improve the runtime by a factor Υ -1 ∈ Θ(N ). Concerning the space complexity, we note that the classical GR tester must store and compare the endpoints of Ω(N 1/2 ) independent random walks. By direct inspection we see that our algorithm only requires O(log(N t log ǫ -1 )) ∈ polylog(N ) qubits to implement, exponentially improving the space complexity. This is due to the fact that our algorithm compares superpositions that encode the endpoint distribution of the random walks, rather than an explicit list of samples.

We can now compare this result to the preceding work by Ambainis, Childs and Liu [START_REF] Ambainis | Quantum property testing for bounded-degree graphs[END_REF]. They used a very different approach to speed up the GR expansion tester, using quantum walks only indirectly, which results in a runtime improvement of a different nature. In rough strokes they speed up the classical 2-norm tester by making use of Ambainis' quantum walk algorithm for element distinctness [START_REF] Ambainis | Quantum walk algorithm for element distinctness[END_REF] to count collisions between pairs of classical random walks more efficiently. This allows them to improve the runtime of the 2-norm tester to O(N 1/3+µ t), which provides a speedup complementary to the speedup of our 2-norm tester which in this context has a runtime O(N 1/2+µ √ t). Using this 2-norm tester in the above Algorithm 5 leads to a runtime

O(N 1/3+µ d 2 Υ -2 ǫ -1 ).
The space complexity of this approach is comparable to the GR tester: the algorithm for element distinctness over the √ N random walk endpoints requires to store N 1/3 elements. We leave it as future work to combine the Θ(N 1/6 ) gain in collision counting of [START_REF] Ambainis | Quantum property testing for bounded-degree graphs[END_REF] with our Θ(dΥ -1 ) gain in random walk runtime and our logarithmic space complexity.

We note that a property tester in the same spirit as the GR expansion tester was proposed by Batu et al [START_REF] Batu | Testing closeness of discrete distributions[END_REF] for testing the mixing time of general Markov chains on a graph. For the special case of symmetric Markov chains it seems feasible that we can speed up their algorithm using the same ideas, yielding a similar speedup on the random walk runtime.

Clusterability and Robust s-t Connectivity

We can similarly use QFF to speed up a more recent line of algorithms on testing the clusterability of a graph [START_REF] Czumaj | Testing cluster structure of graphs[END_REF][START_REF] Chiplunkar | Testing graph clusterability: Algorithms and lower bounds[END_REF]. In clusterability testing the goal is to test whether a graph can be appropriately clustered into k parts for some given k. The proposed algorithms build on a subroutine of independent interest, which allows to determine whether a pair of nodes lie in the same cluster or not. This leads to a robust notion of s-t connectivity, useful e.g. for classifying objects among a set of examples and relevant also outside of the setting of property testing. We show that QFF allows to speed up this subroutine, leading to a speedup on the clusterability testers that use this subroutine.

The observation underlying the clusterability testers in [START_REF] Czumaj | Testing cluster structure of graphs[END_REF][START_REF] Chiplunkar | Testing graph clusterability: Algorithms and lower bounds[END_REF] is that the GR technique of counting collision can also be used to estimate the inproduct of any two given distributions p and q, defined by p, q = j p(j)q(j).

Indeed, this quantity is equal to the collision probability between the two distributions. The estimate on the inproduct of the inproduct is then used to estimate the 2-distance p -q between a pair of random walks, which will be small if both random walks started in the same cluster, and large otherwise. This approach of estimating the distance between distributions was further developed in the work by Batu et al [START_REF] Batu | Testing closeness of discrete distributions[END_REF], Valiant [START_REF] Valiant | Testing symmetric properties of distributions[END_REF] and Chan et al [START_REF] Chan | Optimal algorithms for testing closeness of discrete distributions[END_REF]. We will focus our efforts on showing how QFF allows to speed up this routine of independent interest, following up with an informal discussion of how this leads to a speedup on the clusterability tester of Czumaj et al [START_REF] Czumaj | Testing cluster structure of graphs[END_REF].

2-distance Estimator

To estimate the 2-distance of a pair of random walks, we will combine QFF with the SWAP test: given two quantum states |ψ and |φ and an ancillary qubit in the state |0 , yielding the state |0 |ψ |φ , we apply the following operations:

|0 |ψ |φ H⊗I⊗I → |0 +|1 √ 2 |ψ |φ cS → 1 √ 2 |0 |ψ |φ + 1 √ 2 |1 |φ |ψ H⊗I⊗I → 1 2 |0 (|ψ |φ + |φ |ψ ) + 1 2 |1 (|ψ |φ -|φ |ψ ),
where we used the Hadamard gate

H = 1 √ 2 1 1 1 -1
, and the conditional swap operation cS swapping the second and third registers conditional on the first register being in the state |1 . We will call the combined unitary operation U SWAP = (H ⊗ I ⊗ I)cS(H ⊗ I ⊗ I). We can now either measure the first register, or apply quantum amplitude estimation to the projector

Π 1 = |1 1| ⊗ I ⊗ I, to estimate the quantity |ψ |φ -|φ |ψ 2 = 2(1 -| ψ|φ | 2 ).
This quantity will be small if |ψ and |φ are close and large otherwise, allowing to estimate the distance between the input states |ψ and |φ ′ . We can combine the SWAP test with our QFF algorithm, and the 2-norm estimator in previous section, to obtain a tester for the 2-distance. Due to the straightforward yet technical nature of the details of the tester, we defer its description to Appendix A.

Theorem 7 (Quantum 2-distance Estimator) With probability at least 1 -δ, Algorithm 6 outputs an estimate a such that

P t |u -P t |v 2 -a ≤ ǫ.
For a = max{ P t |u , P t |v } and a = min{ P t |u , P t |v }, the algorithm requires an expected number of QW steps bounded by

O √ t a ǫ + a 4 aǫ 2 log log N δ log 3/2 N ǫ .
For comparison, the classical estimator presented in Czumaj et al [START_REF] Czumaj | Testing cluster structure of graphs[END_REF]Theorem 3.1] requires a number of graph queries or random walk steps O t a ǫ log 1 δ . Chan et al [START_REF] Chan | Optimal algorithms for testing closeness of discrete distributions[END_REF] give an information theoretical proof that classically Ω(a/ǫ) samples are needed to estimate the 2-distance between a pair of distributions.

Classifying Nodes

Czumaj et al [START_REF] Czumaj | Testing cluster structure of graphs[END_REF] use their classical 2-distance estimator to propose a property tester for the clusterability of a graph. Following for instance Oveis Gharan and Trevisan [START_REF] Gharan | Partitioning into expanders[END_REF], they say that a graph G is (k, Φ in , Φ out )-clusterable if and only if there exists a partition V = S 1 ∪ • • • ∪ S h , h ≤ k, such that the clusters are well-connected internally, Φ(G[S j ]) ≥ Φ in , and poorlyconnected externally, Φ(S j ) ≤ Φ out . Here G[S j ] denotes the graph consisting of the nodes in S j and the edges between these nodes, the conductance Φ(S j ) is defined as

Φ(S j ) = |E(S j , S c j )| d|S j | , and the conductance Φ(G ′ ) of a graph G ′ = (V ′ , E ′ ) is Φ(G ′ ) = min T ⊂V ′ ,|T |≤|V ′ |/2 |E(T , V ′ \T )| d|T | .
It turns out that graph clusterability can be efficiently tested when the gap between Φ in and Φ out is sufficiently large -typically quadratic, Φ out ∈ O(Φ 2 in ).

Czumaj et al [START_REF] Czumaj | Testing cluster structure of graphs[END_REF] construct such a clusterability tester using a subroutine for classifying nodes, i.e., determining whether two nodes lie in the same cluster or not. As mentioned before, it is possible to classify nodes by comparing random walks starting from the nodes: the 2-distance between random walks starting from nodes of the same cluster will typically be smaller than the 2-distance between nodes from different clusters. This is formalized below in Lemma 6, which we extract from Czumaj et al [START_REF] Czumaj | Testing cluster structure of graphs[END_REF]Lemma 4.1 and 4.3]. Given an appriopriately clusterable graph, having a gap Φ out ∈ O(Φ 2 in / log N ), it gives bounds on the 2-distance between pairs of nodes coming from the same or different clusters. The lemma is confined to the internal nodes S ⊆ S of a cluster S, similar to most work on locally exploring graph clusters, see for instance the work of Spielman and Teng [START_REF] Spielman | Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems[END_REF]. Lemma 6 ([24]) Consider a (k, Φ in , Φ out )-clusterable graph with degree bound d, and let S and S ′ be clusters of such a partition. Assume that

Φ out ≤ cΦ
= ⌈c ′ k 4 Φ -2 in log N ⌉ it holds that • if two nodes u, v ∈ S or u, v ∈ S′ , then P t |u -P t |v 2 ≤ 1/(4N ).
• if two nodes u ∈ S and v ∈ S′ , then P t |u -P t |v 2 ≥ 1/N .

We can combine this lemma with our quantum 2-distance estimator to prove the below proposition. It speeds up the routine which lies at the basis of the property tester in [START_REF] Czumaj | Testing cluster structure of graphs[END_REF], which essentially solves a robust version of s-t connectivity. Arguably the latter is more relevant to e.g. social networks, where mere connectivity between two nodes is no longer deemed an interesting quantity, yet the community or cluster structure does hold important information.

Proposition 3 (Classifying Nodes)

• Under the clusterability conditions of Lemma 6, we can use the quantum 2-distance estimator to determine with probability at least 2/3 whether two internal nodes lie in the same cluster or not.

• There exists a subset Ṽ ⊆ V, | Ṽ| ≥ 9|V|/10, such that if in addition both nodes lie in Ṽ, then the algorithm requires O(N 1/2 k 4 Φ -1 in log 3/2 N ) expected QW steps. Proof. To prove the first bullet, it suffices to use Lemma 6 which states that if both lie in the same cluster, then P t |u -P t |v 2 ≤ 1/(4N ), whereas if both lie in different clusters, then P t |u -P t |v 2 ≥ 1/N . By Theorem 7 we can estimate P t |u -P t |v 2 to error ǫ = 1/N , which allows to distinguish both cases.

To prove the second bullet, let Ṽ denote a set of nodes u for which P t |u ∈ O(k/N ), which by [START_REF] Czumaj | Testing cluster structure of graphs[END_REF]Lemma 4.2] we know we can choose of size at least 9|V|/10. If both nodes lie in Ṽ, then in Theorem 7 we can set a ∈ O(k/N ), and a ∈ O(1/N ) since necessarily P t |u ≥ 1/N for any node u. In this case, the expected number of QW steps becomes O( √ tN log 3/2 N ). For t in Lemma 6, this proves the second bullet.

We can compare the runtime in the second bullet by the runtime when using classical collision counting, which requires a number of RW steps O(N 1/2 k 4 Φ -2 in ). Applying the element distinctness technique by Ambainis et al [START_REF] Ambainis | Quantum property testing for bounded-degree graphs[END_REF] requires a number of QW steps O(N 1/3 k 4 Φ -2 in ). Again we also find an improvement in space complexity with respect to these alternative approaches: our algorithm only requires polylog(N ) qubits, whereas the other approaches require poly(N ) classical or quantum bits.

Lemma 6, combined with a classifier as in Proposition 3, forms the basis of the graph clusterability tester proposed by [START_REF] Czumaj | Testing cluster structure of graphs[END_REF]. Since the tester is in the same vein as the GR expansion tester, we will not state it explicitly but merely summarize the idea. The algorithm selects a uniformly random set of Θ(k log k) nodes over which it constructs a similarity graph by adding an edge between any pair of nodes if their random walk probabilities are closer than some threshold. This similarity graph serves as a graph sketch, reminiscent of the recent surge of results on graph sketching and sparsification [START_REF] Batson | Spectral sparsification of graphs: theory and algorithms[END_REF]. They then prove that if the graph is appropriately clusterable in at most k components, then with high probability this small similarity graph will have at most k connected components, which they then check by brute force. Using the classical 2-distance estimator to estimate the distance between random walk distributions, this leads to a clusterability tester requiring O N 1/2 k 7 Φ -2 in ǫ -5 RW steps. We can improve this to O N 1/2 k 7 Φ -1 in ǫ -4 QW steps using Proposition 3. It seems feasible that using the element distinctness technique in [START_REF] Ambainis | Symmetry-assisted adversaries for quantum state generation[END_REF] an alternative speedup to O N 1/3 k 7 Φ -2 in ǫ -5 RW steps can be achieved.

Discussion and Open Questions

We introduced a new quantum walk tool called quantum fast-forwarding (QFF), allowing to quantum simulate classical reversible Markov chains with a quadratically improved time dependency. The main benefit of this tool is that it allows to effectively simulate the transient dynamics of the Markov chains. We can contrast this to many existing quantum walk algorithms which rely on a speedup of the Markov chain limit behavior. This new feature is crucial for the applications in graph property testing and node classification that we discuss. Indeed we show that QFF allows to speed up in a very natural way random walk algorithms for testing graph properties such as expansion and clusterability, both of which decisively depend on the transient dynamics of a random walk.

To finalize we mention some avenues for future work:

• Improving the QFF scheme: parameter dependence and irreversible Markov chains. QFF allows to create an ǫ-approximation of the state |D t v with constant success probability using a number of QW steps

O √ t D t |v log 1/2 1 ǫ D t |v
and O( D t |v -1 ) reflections around the initial state |v . It is easy to see that the individual t and ǫ dependency are optimal by looking at the random walk on Z. If we tolerate an ǫ error, then we can confine the probability distribution of a t-step random walk to the Θ t 1/2 log 1/2 ǫ -1 neighborhood of the initial state. Since the QW has the same locality constraints as the RW, it needs Ω t 1/2 log 1/2 ǫ -1 QW steps to spread out over this interval. A very similar argument also shows why in general QFF cannot create the state |P t v (rather than |D t v ) when P is irreversible. Indeed, consider the Markov chain on Z which simply moves to the right every step, P (i + 1, i) = 1 and P (i -1, i) = 0. This walk is clearly not reversible, as the direction of its motion reverses when running the time forward or backward. When starting in the origin, the walk will be on node t after t steps. A local QW requires Ω(t) steps to reach this point, so that no fast-forwarding is possible.

We leave improvements of the dependency on D t |v as an open question.

• Local Graph Clustering and Sparsification. Local graph clustering algorithms, as in [START_REF] Spielman | Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems[END_REF][START_REF] Andersen | Finding sparse cuts locally using evolving sets[END_REF], aim to explicitly construct a local cluster, rather than merely test whether appropriate clusters exist. They have a similar flavor to the graph expansion tester that we discussed, making use of random walks and other diffusive dynamics as a way of locally exploring a graph. It might be possible to use QFF or similar ideas as a way of speeding up these algorithms. Since these algorithms formed the root of a number of approaches towards graph sparsification and solving symmetric diagonally-dominant linear systems, this might lead to speedups on these highly relevant problems as well.

• Hamiltonian QFF. Following for instance Childs [START_REF] Childs | On the relationship between continuous-and discrete-time quantum walk[END_REF], we can associate a QW to a general Hermitian matrix, representing for instance a Hamiltonian rather than a Markov chain. We leave it as an open question whether this can lead to interesting applications in for instance imaginary time evolution [START_REF] Verstraete | Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems[END_REF] or an improved implementation of functions of a Hamiltonian [START_REF] Childs | Quantum algorithm for systems of linear equations with exponentially improved dependence on precision[END_REF].

A Quantum 2-distance Estimator: Algorithm and Proof

In this appendix we present the algorithm and proof underlying Theorem 7, which concerns the estimation of the distance between two random walk distributions p = P t |u and q = P t |v . To construct our algorithm, we rewrite p -q 2 = p 2 + q 2 -2 p q p|q , using the notation p|q = p, q /( p q ). As a consequence, we can retrieve an estimate by separately estimating p , q and p|q . Towards estimating p and q , we present at the end of this appendix a simple extension of the quantum 2-norm tester presented earlier in Section 3.2 that allows to estimate the 2-norm up to multiplicative error, instead of additive error. Towards estimating p|q , we first create approximations of |p = p/ p and |q = q/ q , on which we subsequently apply the SWAP test and amplitude estimation. A subtlety is that we cannot simply use our QFF algorithm to create |p and |q with high probability. Indeed, in order to apply amplitude estimation for the SWAP test we must reflect around these states, and it is not clear that we can reflect around the output of the QFF algorithm. Instead, we will apply the unitary amplitude amplification operator to the states W τ |u, ♭♭ and W τ |v, ♭♭ to unitarily rotate these states close to |p and |q , omitting the final measurement in Algorithm 2. This invertible operation will allow to reflect around the output states. Furthermore, instead of the amplitude amplification operator used in Section 2.2.2, we will make use of an enhanced operator by Yoder and Low [START_REF] Yoder | Fixed-point quantum search with an optimal number of queries[END_REF]. This operator, as described in the below lemma, is better suited for the case where we only have a lower bound on the success probability.

Lemma 7 (Fixed Point Amplitude Amplification [START_REF] Yoder | Fixed-point quantum search with an optimal number of queries[END_REF]) Consider a state |ψ and a projector Π ♭ such that Π ♭ |ψ = λ > 0. For any constant δ > 0, there exists a family of unitary transformations U L such that if L ≥ λ -1 log(2/δ) then

| ψ ♭ |U L |ψ | 2 ≥ 1 -δ 2 ,
where ψ ♭ = Π ♭ |ψ / Π ♭ |ψ . We can implement U L using O(L) reflections around |ψ and around the image of Π ♭ .

Using the appropriate operator U L , we can therefore retrieve approximations |ψ u = U L W τ |u, ♭♭ ≈ |p and |ψ v = U L W τ |v, ♭♭ ≈ |q . We can now apply the SWAP test to these states, combined with amplitude amplification, to retrieve an estimation of p|q . To see this, note that

Π 1 (U SWAP |0 |ψ u |ψ v ) = 1 2 |1 (|ψ u |ψ v -|ψ v |ψ u ).
As a consequence we can apply quantum amplitude estimation on the state U SWAP |0 |ψ u |ψ v with respect to the projector Π 1 to estimate the quantity

1 2 |ψ u |ψ v -|ψ v |ψ u 2 = 1 -| ψ u |ψ v | 2 ≈ 1 -| p|q | 2 .
Combined with the former estimates of p and q this leads to an estimate of the 2-distance we were looking for. We formalize this in the following algorithm and theorem. Proof. We prove the theorem for

µ = 1 26 min 1, 9ǫ 16 max(α, β) 2 , L = 1 λ log 2 ν , τ = √ 2t ln 1/2 4 λν ,
with λ = min(α, β)/(1+ν) and ν = µ 2 /11. We will denote p = P t |u , q = P t |v , |p = p/ p , |q = q/ q , a 2 = max( p , q ) and a = min( p , q ). The algorithm estimates the quantity p -q 2 = p 2 + q 2 -2 p q p|q by separately estimating p , q and p|q to error O(ǫ/a 2 ). After the first step, we retrieve with probability at least 1 -δ/4 estimates α and β such that This proves that the parameter

and µ ∈ Θ(min(1, ǫ/a 2 )). In step 3 we then create new estimates of p and q to multiplicative error µ. The combined success probability of both steps is (1 -δ/4) 2 ≥ 1 -δ/2.

Following Theorem 9 these steps require an expected number of QW steps in

O √ ta ǫ log log N δ log 1/2 N ǫ .
In the following steps of the algorithm we estimate p|q = p,q p q to additive error µ by combining QFF, amplitude amplification, the SWAP test and amplitude estimation. Thereto we first rewrite Combined with the first approximation part, we find estimates α, β and γ such that |α -p | ≤ µ p , |β -q | ≤ µ q and |γ -p|q | ≤ µ. This allows to prove the claimed error of the estimate α 2 + β 2 -2αβγ -p -q 2 ≤ µ(2 + µ)( p 2 + q 2 ) + 2 p q µ(2 + µ)( p|q + µ) + (1 + µ) 2 µ ≤ 3µ( p 2 + q 2 ) + 20µ p q ≤ 26µ max( p , q ) 2 ≤ ǫ, using the bound [START_REF] Wocjan | Speedup via quantum sampling[END_REF]. The total success probability can be bounded by (1 -δ/2)

2-norm Estimator to Multiplicative Error

In the above estimator for the 2-distance we wish to estimate P t |u to some multiplicative error ǫ, without having a bound on P t |u . We present such an estimator in the below algorithm and theorem. use Algorithm 4 to create estimate α of P t |u to error ǫ k = ǫ2 -k-2 , with probability 1 -δ ′ for δ ′ ∈ O(δ log -1 N ) Proof. We will prove the theorem for T = ⌈ 1 2 log N ⌉ and δ ′ = δ/T . We do so by showing that with probability at least 1 -δ the loop aborts such that the value of α forms an estimate of p to multiplicative error ǫ, where we denote p = P t |u . We first assume that every call to Algorithm 4 is successful, the probability of which we will bound afterwards. Let a k be the value of α in the k-th iteration, so that | p -a k | ≤ ǫ k . If the loop is stopped at the k-th iteration then a k ≥ (1 + ǫ)2 -k or equivalently ǫ k ≤ ǫ 1+ǫ a k . Combined with the fact that a k ≤ p + ǫ k this shows that ǫ k ≤ ǫ 1+ǫ ( p + ǫ k ) or equivalently ǫ k ≤ ǫ p , so that we find an estimate with multiplicative error ǫ.

If the first log p -1 calls to the 2-norm estimator are successful, then the algorithm stops and outputs a correct estimate. We can bound this number of calls by T = 1 2 log N using the fact that p ≥ N -1/2 . The probability that this happens, i.e., that none of the first log p -1 implementations of the 2-norm tester fails, is at least 1 -log p -1 δ ′ ≥ 1 -δ if we set δ ′ = δ/T . This proves the success probability of the algorithm.

To bound the runtime, we first note that the k-th iteration runs the 2-norm tester with error ǫ k = ǫ2 -k and success probability 1 -δ ′ , which by Theorem 5 requires a number of QW steps

O 2 k √ t ǫ log log N δ log 1/2 2 k N ǫ .
Now we bound the expected number of iterations. If the algorithm succeeds, then it aborts after log p -1 iterations. If this does not happen, then either it aborts earlier, resulting in a number of iterations smaller than log p -1 , or it aborts later. However, after log p -1 iterations, any successful call to the 2-norm tester will abort the algorithm, which happens per iteration with probability at least 1 -δ. In such case the expected number of iterations can be bounded by (1 -δ) -1 ≤ 2 under the assumption that δ ≤ 1/2. In any case we see that the expected number of iterations is O(log p -1 ). Now we can use the fact that This finalizes the proof.

  l T l (D) |v 2 . We will denote the state |ψ τ = τ l=0 q l T l (D) |v . By the approximation from Lemma 3 we know that if τ = 2t ln 2 ǫ ′

  an initial state |ψ and a projection operator Π ♭ , with Π ♭ |ψ = 0. Define the reflections R ψ = 2 |ψ ψ| -I and R ♭ = 2Π ♭ -I, and set m = ⌊π/(4θ)⌋ with θ ∈ (0, π/2] such that sin θ = Π ♭ |ψ . If we apply the operator (-R ψ R ♭ ) m times on the state |ψ , and we perform a measurement {Π ♭ , I -Π ♭ }, then we find back the state Π ♭ |ψ / Π ♭ |ψ with probability at least max{1 -sin 2 θ, sin 2 θ} ≥ 1/2.

4 :

 4 use Algorithm 4 to create estimate a of P t |s to precision ǫ ′ , with probability 1 -δ 5:

  2 in / log N, with c some constant dependent on d, k, |S|/N and |S ′ |/N . Then there exist subsets S ⊆ S, | S| ≥ |S|/2, and S′ ⊆ S ′ , | S′ | ≥ |S ′ |/2, and a universal constant c ′ , such that for t

Algorithm 7 1 :

 71 Quantum Multiplicative 2-norm Estimator Input: parameters N and d; query access to N -node graph G with degree bound d; starting vertex u; running time t; accuracy parameter ǫ; confidence parameter δ Do: for k = 1 . . . T ∈ O(log N ) do 2:

b k=0 2 k

 2 log 1/2 2 k ∈ O(2 b √ b) ∈ O( p -1 log 1/2 p ) for b ∈ O(log p -1) to bound the total expected number of QW steps by

  Algorithm 4 Quantum 2-norm Estimator Input: parameters N and d; query access to N -node graph G with degree bound d; starting vertex s; running time t; accuracy parameter ǫ; confidence parameter δ Do: Theorem 5 (Quantum 2-norm Estimator) With probability at least 1 -δ, Algorithm 4 outputs an estimate a such that P t |s -a ≤ ǫ. The algorithm requires a number of QW steps bounded by O

	√ t ǫ log 1 δ log 1/2 N ǫ .

1: set τ ∈ O( t log(N/ǫ)) 2: apply the QFF operator W τ on the quantum state |s, ♭♭ 3: use quantum amplitude estimation to create estimate a of Π ♭ W τ |s, ♭♭ to error ǫ/2 with probability 1 -δ Output: estimate a

  Algorithm 6 Quantum 2-distance Estimator Input: parameters N and d; query access to N -node graph G with degree bound d; starting vertices u and v; running time t; accuracy parameter ǫ; confidence parameter δ Do: 1: use Algorithm 7 to create estimates α and β of P t |u resp. P t |v to multiplicative error 1/4, with probability 1 -δ/4 2: set µ ∈ O(ǫ max(α, β) -2 ) 3: use Algorithm 7 to create new estimates α and β of P t |u resp. P t |v to multiplicative error µ, with probability 1 -δ/4 4: set L ∈ Ω(min(α, β) -1 log min(α, β) -1 ) and τ ∈ Ω( t ln(N/µ)) 5: apply W τ , U L and U SWAP to create the state |ψ = U SWAP |0 U L W τ |u, ♭♭ U L W τ |v, ♭♭ 6: use amplitude estimation to create an estimate γ of Π 1 |ψ to error µ, with probability 1 -δ/2 Output: estimatea = α 2 + β 2 -2αβ 1 -γ 2 /2Theorem 8 (Quantum 2-distance Estimator) With probability at least 1 -δ, Algorithm 6 outputs an estimate a such thatP t |u -P t |v 2 -a ≤ ǫ.With a = max{ P t |u , P t |v } and a = min{ P t |u , P t |v }, the algorithm requires an expected number of QW steps bounded by

	O	√ t	a ǫ	+	a 4 aǫ 2 log	log N δ	log 3/2 N ǫ	.

  p|q = 1 -|p |q -|q |p 2 2 , showing that we can use an estimate on |p |q -|q |p to estimate p|q . Indeed, it is easily seen from a function plot that if we create an estimate κ ∈ [0, √ 2] such that |p |q -|q |p -κ ≤ µ 2 , then the estimate √ 1 -κ 2 /2 will be µ-close:1 -κ 2 /2 -p|q ≤ µ.(11)We now create an estimate of |p |q -|q |p . Lemma 7 and Theorem 3, and our choice of L and τ , it holds thatU L W τ |u, ♭♭ -|p, ♭♭ ≤ (1 -ν 2 ) W τ |u, ♭♭ / W τ |u, ♭♭ -|p, ♭♭ + ν ≤ (1 -ν 2 )ν + ν ≤ 2ν, with ν = µ 2 /11, and similarly for U L W τ |v, ♭♭ . If we set |ψ u = U L W τ |u, ♭♭ and |ψ v = U L W τ |v, ♭♭ , then this implies that |ψ u |ψ v -|ψ v |ψ u -|p |q -|q |p ≤ 8ν(1 + 2ν). Now we can apply amplitude estimation, as in Lemma 5, to the state U SWAP |0 |ψ u |ψ v and projector Π 1 with success probability 1 -δ/2 and error ν. If successful this returns an estimate γ of |ψ u |ψ v -|ψ v |ψ u to error ν. Combined with the above inequality this shows that |p |q -|q |p -γ ≤ ν + 8ν(1 + 2ν) ≤ µ 2 . By (11) this leads to the promised bound √ 1 -γ 2 /2 -p|q ≤ µ. Implementing W τ , U L and U SWAP requires a number of QW steps O(τ ) + O(L), bounded by Applying amplitude estimation with success probability 1 -δ/2 and error ν ∈ Θ(ǫ 2 /a 4 ) requires O a 4 ǫ 2 log 1 δ reflections around the state U SWAP |0 |ψ u |ψ v We can implement each such reflection using the same number of QW steps required to implement the operators W τ , U L and U SWAP . This leads to a total number of QW steps bounded by

		O	√ t a	log	a ǫa	log 1/2 N a ǫ	.
	O	√ ta 4 aǫ 2 log	1 δ	log	a ǫa	log 1/2 N a ǫ	.

  2 ≥ 1 -δ, and the expected number of QW steps by

	O	√ t	a ǫ	+	a 4 aǫ 2 log	log N δ	log 3/2 N ǫ	.

  Theorem 9 (Quantum Multiplicative 2-norm Estimator) With probability at least 1δ, Algorithm 6 outputs an estimate α such that P t |u -α ≤ ǫ P t |u .

	The algorithm requires an expected number of QW steps bounded by
	O	√ t ǫ p	log	log N δ	log 1/2 N ǫ	.

3:

if α ≥ (1 + ǫ)2 -k , abort for-loop Output: α