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:
- Estimating the number of $m$-length walks that start at $i$ and end back at $i$ is in (promise) $\mathsf{BQP}$;
- Estimating the number of $m$-length walks that start at $i$ and end at $j$ is in $\mathsf{BQP}$;
- 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
- 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.
