Reviewing the appendix of Quantum Money from Knots by Farhi, Gosset, Hassidim, Lutomirski, and Shor, the authors provide a *finite,* *doubly-stochastic* Markov chain, where transitions act on grid diagrams.

Thus, the limiting distribution of their chain applied (classically) to a given grid diagram representing the unknot is uniform, and one of the states would be a canonical $2\times 2$ unknot.

In order to keep the Markov chain finite, they have a security parameter $\bar{D}$ and declare that two grid diagrams $G_1$ and $G_2$ don't represent the same knot/link if all sequence of moves from $G_1$ to $G_2$ require transitioning to a grid of size $d\gt 2\bar{D}$.

As I understand their quantum verification protocol, given a superposition of grid diagrams $\tilde{G}$, all with the same Alexander polynomial, their quantum-computer enabled merchant randomly apply $O(\textrm{poly}\:\bar{D})$ cyclic permutations, transpositions, stabilizations, and destabilizations to each state, if she can, to generate a "new" superposition of grid diagrams $G$. The verification succeeds only if $\tilde{G}=G$; by the no-cloning theorem, such superpositions cannot be easily forged.

In order to show the chain is doubly-stochastic, they note that cyclic permutations are invertable. Transpositions that are allowed are invertable, and similarly stabilizations and destabilizations. Stabilizations *increase* the grid number $d$, whereas destabilizations *decrease* the grid number $d$. For reasons similar to Theo's comment, a stabilization move is more likely to be done than a destabilization move; however, because of the way they uniformly choose their moves, any move that increases $d$ to more than $2\bar{D}$ won't be done. Thus, they (or rather their quantum verification algorithm) simply walks along the space of all grid diagrams equivalent to $G$ that are less than or equal to $2\bar{D}\times 2\bar{D}$ in size.

Thinking classically, and, rather than applying the quantum algorithm to a superposition of states, only applying their same Markov chain to a single grid diagram $G$ of grid number $\bar{D}$ which represents the unknot, the stable distribution will be uniform over every grid diagram equivalent to $G$ having a grid number less than or equal to $2\bar{D}$.

(They also require a weighting index $i$ of the grid diagram, because they would like the grid dimension $d$ in their superposition of grid diagrams to be centered around $\bar{D}$. Thus, they let $i$ be appropriately normally distributed, and their stable distribution is uniform over *pairs* $(G,i)$.)

Farhi, Gosset, Hassidim, Lutomirski, and Shor note that, for most knots, the security of their quantum money depends on the mixing time of their Markov chain being *polynomial* in $\bar{D}$. I think Lackenby's A polynomial upper bound on Reidemeister moves results, mentioned in the comments, suggest that the unknot in particular *would* mix in polynomial time. Accordingly, if the given knot is the unknot, it may take an exponentially long time to walk along this space (the hitting time may be exponential), but a $2\times 2$ grid diagram representing the unknot should eventually be reached.

doestake an exponential number of moves in general. Moreover, I would guess that if you only make random moves, it's highly unlikely you will ever find a route to the unknot -- it seems more likely that you would be endlessly lost in diagram space. $\endgroup$ – Ryan Budney Oct 9 '11 at 1:12unknottingType I / Type II moves over "knotting" Type I / Type II? That is, given a knot diagram with a list of potential Reidemeister moves, if one favor unknotting moves that reduce the crossing number over knotting moves that increase the crossing number, then one may have a non-zero probability of unknotting eventually. $\endgroup$ – Mark S Nov 18 '17 at 14:497more comments