7
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • $\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 '20 at 0:26
  • $\begingroup$ Ok, your edit makes it clearer, thanks. $\endgroup$ – Neal Young Aug 1 '20 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 '20 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 '20 at 12:51
  • $\begingroup$ Maybe Problem (2), minus the "estimating", is #P-complete? To show #P-hardness, given NTM M running in (poly) time p(n), and input x, consider a graph whose nodes are the configurations of M with size O(p(n)), with a directed edge from u to w if configuration u can transition in one step to configuration w. Assume WLOG that there is only one accepting configuration. Then the number of walks from the start configuration to that accepting configuration is the number of accepting computation paths of M on input x. Similarly you can easily show (2) is in #P... $\endgroup$ – Neal Young Aug 3 '20 at 15:05

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.