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?

  • 1
    $\begingroup$ 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. $\endgroup$ Apr 24, 2023 at 17:11
  • $\begingroup$ @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$. $\endgroup$
    – Mark S
    Apr 24, 2023 at 17:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.