<p>Consider an <span class="math-container">$N\times N$</span> adjacency matrix <span class="math-container">$A$</span> of some large, <span class="math-container">$b$</span>-sparse undirected graph <span class="math-container">$G$</span>.  The <span class="math-container">$(i,j)$</span> entry of <span class="math-container">$A^m$</span> counts the number of <span class="math-container">$m$</span>-length paths between vertex <span class="math-container">$i$</span> and vertex <span class="math-container">$j$</span>.</p>
<p>We let <span class="math-container">$A$</span> be strongly explicit.  For example, the number of vertices <span class="math-container">$N$</span> is large, e.g. exponential in <span class="math-container">$m$</span>, <span class="math-container">$b$</span>.  We have an efficient algorithm to <span class="math-container">$A_{ij}$</span> - e.g. given vertices <span class="math-container">$i,j$</span> we can efficiently determine whether they are adjacent, and for all vertices <span class="math-container">$i$</span> we can efficiently generate all other <span class="math-container">$b$</span> vertices adjacent to <span class="math-container">$i$</span>.  For example we can generalize Cayley graphs of the 15-puzzle (<span class="math-container">$b=4$</span> and <span class="math-container">$N=6.5e10$</span>), or the Rubik's cube (<span class="math-container">$b=18$</span> and <span class="math-container">$N=4.3e19$</span>).  Each <span class="math-container">$m$</span>-length word corresponds to an <span class="math-container">$m$</span>-length walk on the Cayley graph.</p>
<p>In a <a href="https://theoryofcomputing.org/articles/v003a004/v003a004.pdf" rel="nofollow noreferrer">series</a> <a href="https://arxiv.org/abs/quant-ph/0610235" rel="nofollow noreferrer">of</a> <a href="https://arxiv.org/abs/0705.1180" rel="nofollow noreferrer">papers</a>, Janzing and Wocjan investigated quantum algorithms to estimate various powers of <span class="math-container">$A$</span>.  For example, they rescaled <span class="math-container">$A$</span> and simulated <span class="math-container">$U=e^{-iAt}$</span>, and executed a quantum phase estimation on <span class="math-container">$U\vert \psi\rangle$</span> to perform an <span class="math-container">$A$</span>-measurement on qubits prepared in various simple states <span class="math-container">$\vert\psi\rangle$</span>. The phase estimation algorithm gives enough eigenvalues <span class="math-container">$\lambda$</span> of the spectral decomposition of <span class="math-container">$A$</span> with probabilities given by the decomposition of <span class="math-container">$\vert\psi\rangle$</span> into <span class="math-container">$A$</span>-eigenstates, to estimate <span class="math-container">$\langle\psi\vert A^m\vert\psi\rangle$</span>. Given three vertices <span class="math-container">$i,j,k$</span>, they were then able to control errors in the Hamiltonian simulation and in the phase estimation, and showed:</p>
<ol>
<li>Estimating the number of <span class="math-container">$m$</span>-length walks that start at <span class="math-container">$i$</span> and end back at <span class="math-container">$i$</span> is in (promise) <span class="math-container">$\mathsf{BQP}$</span>;</li>
<li>Estimating the number of <span class="math-container">$m$</span>-length walks that start at <span class="math-container">$i$</span> and end at <span class="math-container">$j$</span> is in <span class="math-container">$\mathsf{BQP}$</span>;</li>
<li>Estimating a <em>difference</em> in the number of <span class="math-container">$m$</span>-length walks that start at <span class="math-container">$i$</span> and end at <span class="math-container">$i$</span>, versus those that start at <span class="math-container">$i$</span> and end at <span class="math-container">$j$</span>, is <span class="math-container">$\mathsf{BQP\:Complete}$</span>; and</li>
<li>Estimating a difference in the number of paths from <span class="math-container">$i$</span> to <span class="math-container">$j$</span>, versus a number of paths from <span class="math-container">$i$</span> to <span class="math-container">$k$</span>, is likewise <span class="math-container">$\mathsf{BQP\:Complete}$</span>.</li>
</ol>
<p>Their proofs that the last two problems are <span class="math-container">$\mathsf{BQP\:hard}$</span> are quite clever (although I don't understand them fully).  But they emphasize that quantum computers show their power for <em>interference</em> when asking for a difference in the number of paths.  This I believe is similar to the context of <a href="https://rjlipton.wordpress.com/2009/08/27/stockmeyers-approximate-counting-method/#comment-1208" rel="nofollow noreferrer">Regan's comment</a> on GLL.</p>
<p>But as to my question:</p>
<blockquote>
<p>Can the first two problems be bounded any lower than <span class="math-container">$\mathsf{BQP}$</span>?  For example, are they amenable to Stockmeyer approximation?  Or even better, is there any other <span class="math-container">$\mathsf{NP}$</span> certificate that can be used to estimate <span class="math-container">$\langle i\vert A^m\vert j\rangle$</span> for various <span class="math-container">$i,j$</span>?</p>
</blockquote>
<p>If <span class="math-container">$m$</span> is much greater than the mixing time, then each of the four questions might be straightforward to bound.  The last two should approach <span class="math-container">$0$</span> as <span class="math-container">$m$</span> increases, I think.</p>

CC BY-SA 4.0
2020-08-01T00:26:52.707Z
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
CC BY-SA 4.0
2020-08-01T13:16:28.330Z
Ok, your edit makes it clearer, thanks.
Neal Young
CC BY-SA 4.0
2020-08-03T05:27:51.033Z
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
CC BY-SA 4.0
2020-08-03T12:51:54.163Z
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
CC BY-SA 4.0
2020-08-03T15:05:58.670Z
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...
Neal Young
CC BY-SA 4.0
2020-08-03T19:24:26.160Z
@MarkS how do you measure the input size for, e.g., Problem (2)?  Is it polynomial in $\Theta(b + \log (m + N))$?
Neal Young
CC BY-SA 4.0
2020-08-03T20:04:49.963Z
@NealYoung Janzing and Wocjan call an instance of Problem 1 a tuple $(A,b,m,j,\epsilon,g)$, with $g$ the estimate, and $b$ the operator norm of $A$ (here I just equated it with the degree/sparseness of the graph).  The algo is polynomial in $\log N$, and they bound $(A^m)_{jj}$ up to $\epsilon b^m$.  That is, their quantum algorithm gets an estimate $g$ of $(A^m)_{jj}$ to accuracy $\pm\epsilon b^m$. They actually work on general matrices with entries $A_{ij}\in\{-1,0,1\}$. (They note that what I call the second problem should have an adjustment of $b$ in ways that I don't understand yet.)
Mark S
CC BY-SA 4.0
2020-08-03T21:12:11.360Z
Rephrase problem (2) as "given a random configuration $\pi$ of the Rubik's cube, how many different words of length $m$ are there in $\langle U,D,L,R,F,B,U^2,D^2,\cdots\rangle$ to go from the solved position to $\pi$?"  The number of words grows as $18^m$.
Mark S
CC BY-SA 4.0
2020-08-04T00:49:39.270Z
Your (2) as originally formulated is equivalent to approximating (in some way) the permanent (or any other #P-complete function).  For more on that see e.g. https://pdfs.semanticscholar.org/5525/1a5187d50924fba542186ea0a276348e0cc4.pdf and http://www.cs.umd.edu/~jkatz/complexity/f05/lecture9.pdf .  If you rephrase (2) as suggested (so that A is fixed), I'd guess you can compute the number of words/walks exactly in time polynomial in log(m), unless you count the bit complexity of arithmetic, in which case just writing down the answer exactly would require $\Theta(m)$ bits, as you point out.
Neal Young
CC BY-SA 4.0
2020-08-04T15:27:59.983Z
Suppose that $A$ is the adjacency matrix of the Rubik's cube under the half-turn metric.  If $m$ is greater than the mixing time, then for almost all pairs of vertices $(i,j)$, I think we have $(A^m)_{ij}=\frac{18^m}{\vert G\vert}$, representing the idea that no two vertices are disfavored after the cube has been scrambled sufficiently.  If we could exactly count $(A^m)_{ij}$ for any $i,j,m$, then we could test how close it is to the above, and hence know whether $m$ is greater than the mixing time.  It was a monumental effort to determine that the *diameter* of $\vert G\vert$ is $20$.
Mark S
<quantum-computing><random-walks>
What is the complexity of estimating the number of paths between two vertices of a large graph?
Mark S
# What is the complexity of estimating the number of paths between two vertices of a large graph?

(Asked by: username_0 on 2020-07-27)

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](https://theoryofcomputing.org/articles/v003a004/v003a004.pdf) [of](https://arxiv.org/abs/quant-ph/0610235) [papers](https://arxiv.org/abs/0705.1180), 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](https://rjlipton.wordpress.com/2009/08/27/stockmeyers-approximate-counting-method/#comment-1208) 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.

**Tags:** quantum-computing, random-walks
> **Comments:**
> **username_1**: 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.  
> **username_1**: Ok, your edit makes it clearer, thanks.  
> **username_2**: 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.  
> **username_0**: 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."  
> **username_1**: 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...  
> **username_1**: @MarkS how do you measure the input size for, e.g., Problem (2)?  Is it polynomial in $\Theta(b + \log (m + N))$?  
> **username_0**: @NealYoung Janzing and Wocjan call an instance of Problem 1 a tuple $(A,b,m,j,\epsilon,g)$, with $g$ the estimate, and $b$ the operator norm of $A$ (here I just equated it with the degree/sparseness of the graph).  The algo is polynomial in $\log N$, and they bound $(A^m)_{jj}$ up to $\epsilon b^m$.  That is, their quantum algorithm gets an estimate $g$ of $(A^m)_{jj}$ to accuracy $\pm\epsilon b^m$. They actually work on general matrices with entries $A_{ij}\in\{-1,0,1\}$. (They note that what I call the second problem should have an adjustment of $b$ in ways that I don't understand yet.)  
> **username_0**: Rephrase problem (2) as "given a random configuration $\pi$ of the Rubik's cube, how many different words of length $m$ are there in $\langle U,D,L,R,F,B,U^2,D^2,\cdots\rangle$ to go from the solved position to $\pi$?"  The number of words grows as $18^m$.  
> **username_1**: Your (2) as originally formulated is equivalent to approximating (in some way) the permanent (or any other #P-complete function).  For more on that see e.g. https://pdfs.semanticscholar.org/5525/1a5187d50924fba542186ea0a276348e0cc4.pdf and http://www.cs.umd.edu/~jkatz/complexity/f05/lecture9.pdf .  If you rephrase (2) as suggested (so that A is fixed), I'd guess you can compute the number of words/walks exactly in time polynomial in log(m), unless you count the bit complexity of arithmetic, in which case just writing down the answer exactly would require $\Theta(m)$ bits, as you point out.  
> **username_0**: Suppose that $A$ is the adjacency matrix of the Rubik's cube under the half-turn metric.  If $m$ is greater than the mixing time, then for almost all pairs of vertices $(i,j)$, I think we have $(A^m)_{ij}=\frac{18^m}{\vert G\vert}$, representing the idea that no two vertices are disfavored after the cube has been scrambled sufficiently.  If we could exactly count $(A^m)_{ij}$ for any $i,j,m$, then we could test how close it is to the above, and hence know whether $m$ is greater than the mixing time.  It was a monumental effort to determine that the *diameter* of $\vert G\vert$ is $20$.  

---

## 0 answers

