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.

  • $\begingroup$ 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. $\endgroup$ – Neal Young Aug 1 at 0:26
  • $\begingroup$ 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. $\endgroup$ – Mark S Aug 1 at 2:04
  • $\begingroup$ Ok, your edit makes it clearer, thanks. $\endgroup$ – Neal Young Aug 1 at 13:16
  • $\begingroup$ 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. $\endgroup$ – isaacg Aug 3 at 5:27
  • $\begingroup$ 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." $\endgroup$ – Mark S Aug 3 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.