<p>Consider an implicitly defined graph; for example, let <span class="math-container">$G$</span> be a finite group generated with <span class="math-container">$n$</span> generators as <span class="math-container">$\langle g_1,g_2,\ldots g_n\rangle$</span> and let <span class="math-container">$\Gamma$</span> be the Cayley graph of <span class="math-container">$G$</span> under these generators.</p>
<p>We can ask how long <span class="math-container">$m$</span> of a discrete-time random walk it takes along the Cayley graph, starting say from the identity <span class="math-container">$e$</span>, such that the distribution of the vertex so reached is within a total variation distance <span class="math-container">$\delta$</span> of less than <span class="math-container">$\epsilon$</span> from the stationary distribution <span class="math-container">$\pi$</span>.</p>
<p>Under appropriate promises, where in the polynomial hierarchy is it to determine <span class="math-container">$m$</span> given <span class="math-container">$G=\langle g_1,g_2,\ldots g_n\rangle$</span>?  For example if we concern ourselves with multiplicative error, is this amenable to Stockmeyer counting?  For additive error, is it even <em>in</em> the polynomial hierarchy?</p>
<p>This is related to the spectral properties of <span class="math-container">$\Gamma$</span>, in particular to the spectral gap of the adjacency matrix of <span class="math-container">$\Gamma$</span>. Under what conditions is even learning this gap in PH? My hidden motivation is when is it in BQP?</p>

CC BY-SA 4.0
2023-04-24T17:11:14.110Z
Why the promise? Even if the mixing time is poly(|G|), that's still at most exponential in n (assuming the generating set is not much larger than it needs to be) which can still be represented by poly(n) bitsize.
Joshua Grochow
CC BY-SA 4.0
2023-04-24T17:37:41.350Z
@JoshuaGrochow You're right!  I totally missed that point and guessed that we had to actually *do the $m$-length walk* to have any chance to verify, which is prohibitive if $m=O(\vert G\vert)$, but of course that might not actually be required.  Perhaps the more relevant promise is on the accuracy $\epsilon$.
Mark S
<graph-theory><quantum-computing><polynomial-hierarchy><markov-chains>
(Where) is determining the mixing time of an implicitly defined graph in the polynomial hierarchy?
Mark S
# (Where) is determining the mixing time of an implicitly defined graph in the polynomial hierarchy?

(Asked by: username_0 on 2023-04-24)

Consider an implicitly defined graph; for example, let $G$ be a finite group generated with $n$ generators as $\langle g\_1,g\_2,\ldots g\_n\rangle$ and let $\Gamma$ be the Cayley graph of $G$ under these generators.

We can ask how long $m$ of a discrete-time random walk it takes along the Cayley graph, starting say from the identity $e$, such that the distribution of the vertex so reached is within a total variation distance $\delta$ of less than $\epsilon$ from the stationary distribution $\pi$.

Under appropriate promises, where in the polynomial hierarchy is it to determine $m$ given $G=\langle g\_1,g\_2,\ldots g\_n\rangle$? For example if we concern ourselves with multiplicative error, is this amenable to Stockmeyer counting? For additive error, is it even *in* the polynomial hierarchy?

This is related to the spectral properties of $\Gamma$, in particular to the spectral gap of the adjacency matrix of $\Gamma$. Under what conditions is even learning this gap in PH? My hidden motivation is when is it in BQP?

**Tags:** graph-theory, quantum-computing, polynomial-hierarchy, markov-chains
> **Comments:**
> **username_1**: Why the promise? Even if the mixing time is poly(|G|), that's still at most exponential in n (assuming the generating set is not much larger than it needs to be) which can still be represented by poly(n) bitsize.  
> **username_0**: @JoshuaGrochow You're right!  I totally missed that point and guessed that we had to actually *do the $m$-length walk* to have any chance to verify, which is prohibitive if $m=O(\vert G\vert)$, but of course that might not actually be required.  Perhaps the more relevant promise is on the accuracy $\epsilon$.  

---

## 0 answers

