# What is the complexity of estimating the number of paths between two vertices of a large graph?

Consider an $$N\times N$$ adjacency matrix $$A$$ of some large, $$b$$-sparse undirected graph $$G$$. The $$(i,j)$$ entry of $$A^m$$ counts the number of $$m$$-length paths between vertex $$i$$ and vertex $$j$$.

We let $$A$$ be strongly explicit. For example, the number of vertices $$N$$ is large, e.g. exponential in $$m$$, $$b$$. We have an efficient algorithm to $$A_{ij}$$ - e.g. given vertices $$i,j$$ we can efficiently determine whether they are adjacent, and for all vertices $$i$$ we can efficiently generate all other $$b$$ vertices adjacent to $$i$$. For example we can generalize Cayley graphs of the 15-puzzle ($$b=4$$ and $$N=6.5e10$$), or the Rubik's cube ($$b=18$$ and $$N=4.3e19$$). Each $$m$$-length word corresponds to an $$m$$-length walk on the Cayley graph.

In a series of papers, Janzing and Wocjan investigated quantum algorithms to estimate various powers of $$A$$. For example, they rescaled $$A$$ and simulated $$U=e^{-iAt}$$, and executed a quantum phase estimation on $$U\vert \psi\rangle$$ to perform an $$A$$-measurement on qubits prepared in various simple states $$\vert\psi\rangle$$. The phase estimation algorithm gives enough eigenvalues $$\lambda$$ of the spectral decomposition of $$A$$ with probabilities given by the decomposition of $$\vert\psi\rangle$$ into $$A$$-eigenstates, to estimate $$\langle\psi\vert A^m\vert\psi\rangle$$. Given three vertices $$i,j,k$$, they were then able to control errors in the Hamiltonian simulation and in the phase estimation, and showed:

1. Estimating the number of $$m$$-length walks that start at $$i$$ and end back at $$i$$ is in (promise) $$\mathsf{BQP}$$;
2. Estimating the number of $$m$$-length walks that start at $$i$$ and end at $$j$$ is in $$\mathsf{BQP}$$;
3. Estimating a difference in the number of $$m$$-length walks that start at $$i$$ and end at $$i$$, versus those that start at $$i$$ and end at $$j$$, is $$\mathsf{BQP\:Complete}$$; and
4. Estimating a difference in the number of paths from $$i$$ to $$j$$, versus a number of paths from $$i$$ to $$k$$, is likewise $$\mathsf{BQP\:Complete}$$.

Their proofs that the last two problems are $$\mathsf{BQP\:hard}$$ are quite clever (although I don't understand them fully). But they emphasize that quantum computers show their power for interference when asking for a difference in the number of paths. This I believe is similar to the context of Regan's comment on GLL.

But as to my question:

Can the first two problems be bounded any lower than $$\mathsf{BQP}$$? For example, are they amenable to Stockmeyer approximation? Or even better, is there any other $$\mathsf{NP}$$ certificate that can be used to estimate $$\langle i\vert A^m\vert j\rangle$$ for various $$i,j$$?

If $$m$$ is much greater than the mixing time, then each of the four questions might be straightforward to bound. The last two should approach $$0$$ as $$m$$ increases, I think.

• Can you clarify the exact input (and its encoding size) for the problem(s) you ask about? As it stands, I think that, e.g., Question 1 is about the following problem: Given a directed graph $G$, a vertex $v$, and an integer $m$, what is the number of length-$m$ walks in $G$ that start and end at $v$? But this can't be the problem you have in mind, as it is clearly in P, and from your other statements I think the problem you have in mind should not be (clearly) in P. – Neal Young Aug 1 at 0:26
• Thanks, I think of $A$ as quite big, exponential in the number of qubits. However, $A$ has to be described strongly explicitly for Janzing and Wocjan's algorithm - there has to be an efficient procedure to give all of the (up to $b$) neighbors of any vertex for the Hamiltonian simulation to succeed. – Mark S Aug 1 at 2:04
• Ok, your edit makes it clearer, thanks. – Neal Young Aug 1 at 13:16
• By the way, (3) and (4) don't necessarily approach 0 as m increases, except as a ratio to m. For instance, if the graph is a triangle, (3) alternates between 1 and -1 forever. – isaacg Aug 3 at 5:27
• Thanks! I think you're right. Janzing and Wocjan also considered a continuous (classical) walk from $i$ to $i$ and from $i$ to $j$. They state "For increasing $m$, the difference $(A^m)_{ii} − (A^m)_{ij}$ is therefore directly linked to the decay of probability differences, i.e., to mixing properties of the random walk." – Mark S Aug 3 at 12:51