Officials in Rubik's cube tournaments have used two different ways of scrambling a cube. Presently, they break a cube apart and reassemble the cubies in a random order $\pi\in G$ of the Rubik's cube group $G$. Previously, they would apply a random sequence $g$ of Singmaster moves $\langle U,D, F, B, L, R\rangle$.
However, the length $t$ of the word $g$ - the number of random moves needed in order to fully scramble the cube such that each of the $\Vert G\Vert=43,252,003,274,489,856,000$ permutations is roughly equally likely to occur - is presently unknown, but must be at least $20$. This length $t$ can be called the mixing time of a random walk on the Cayley graph of the Rubik's cube group generated by the Singmaster moves $\langle U,D, F, B, L, R\rangle$.
Would a quantum computer have any advantages to determining the mixing time $t$ of the Rubik's cube group?
I think we can have some clever sequence of Hadamard moves to create a register $\vert A \rangle$ as a uniform superposition over all $\Vert G\Vert$ such configurations; thus applying any sequence of Singmaster moves to $\vert A \rangle$ doesn't change $\vert A \rangle$.
If we have a guess $t'$ as to what the mixing time $t$ is, we can also create another register $\vert B \rangle$ as a uniform superposition of all Singmaster words of length $t'$, and conditionally apply each such word to a solved state $\vert A'\rangle$, to hopefully get a state $\vert B\rangle \vert A\rangle$ such that, if we measure $\vert A \rangle$, each of the $\Vert G \Vert$ configurations are equally likely to be measured. If $t'\lt t$, then we won't have walked along the Cayley graph of $G$ for long enough, and if we were to measure $\vert A \rangle$, configurations that are "closer" to the solved state would be more likely. Some clever Fourier-like transform on $\vert B \rangle$ might be able to measure how uniformly distributed $\vert A \rangle$ is.
To me this feels like something a quantum computer may be good at. For example, if $\vert A \rangle$ hasn't been uniformly mixed by all of the words in $\vert B\rangle$, then some configurations are more likely than others, e.g. $\vert A \rangle$ is more "constant"; whereas if $\vert A \rangle$ has been fully mixed by all of the walks, then $\vert A \rangle$ is more "balanced". But my inuition about both quantum algorithms and Markov chains is not strong enough to get very far.
Contrast this question with the quantum knot verification problem.
In the quantum knot verification, a merchant is given a quantum coin as a state $\vert K \rangle$ of all knots that have a particular invariant. In order to verify the quantum coin, she applies a Markov chain $M$ to transition $\vert K \rangle$ to itself (if it's a valid coin.) She must apply this Markov chain and measure the result at least $t$ times, but otherwise she has no way to construct $\vert K \rangle$ on her own (lest she could forge the coin.) So if she's given a valid coin, she's given a state that she can't produce on her own, along with a Markov chain as a matrix $M$, and she presumably knows the mixing time $t$; she's required to test that $\vert K \rangle$ is valid.
In the present question, it's probably pretty easy to generate $\vert RC \rangle$ of all Rubik's cube permutations. The quantum circuit corresponding to the Markov chain, call it $S$, of Singmaster moves, is also probably pretty easy to build. However, the mixing time $t$ is unknown, and is the one thing to be determined.