# Does Lackenby's polynomial bound on knot moves imply polynomial mixing in "Quantum Money From Knots?"

In the 2010 paper Quantum Money from Knots Farhi, Gosset, Hassidim, Lutomirski, and Shor give a doubly stochastic Markov chain acting on grid diagrams. Transitions in the Markov chain are permutations of the configuration space of grid diagrams, given by random Cromwell moves. They imply that the security of their quantum money system is dependent on the rapid polynomial-time mixing of their Markov chain. They comment that, at least at the time it was written, even for the unknot it wasn't known if there were two equivalent grid diagrams requiring a superpolynomial number of moves to go from one to the other.

In the 2013 paper A polynomial upper bound on Reidemeister moves Lackenby shows that the number of Reidemeister moves needed to untangle a diagram of the unknot with $c$ crossings is, at most, $(236c)^{11}$. From other comments, it appears that Lackenby has extended the above to show that arbitrary knots can be converted to one another with a polynomial number of Reidemeister moves.

Is Lackenby's result strong enough to show, or lend credence to, Farhi, Gosset, Hassidim, Lutomirski, and Shor's conjectured polynomial-time mixing?

I envision Lackenby's result as putting a polynomial upper bound on the diameter/God's number of the graph of Reidemeister moves - similar to the graph of Cromwell moves that can be randomly walked with Farhi, Gosset, Hassidim, Lutomirski, and Shor's Markov chain.

EDIT January 6, 2018

To give more detail, states in the version Farhi, Gosset, Hassidim, Lutomirski, and Shor's Markov chain ("the Markov chain") that I am picturing consist of grid diagrams $G$ reachable from a starting diagram $\tilde{G}$ of dimension $\bar{D}$, that do not increase the dimension beyond some maximum $\alpha$. (In their paper, $\alpha$ was set to $2\bar{D}$; however, for the purposes of the question I think we must require $\alpha$ to be polynomial in $\bar{D})$.

The Markov chain as described in the paper further includes a weighting parameter $i$; the limiting distribution of the Markov chain is uniform over pairs $(G,i)$. However, for the purposes of the question, I think $i$ is not needed, and the limiting distribution need merely be uniform over all grid diagrams $G$ reachable from $\tilde{G}$ that don't increase the dimension by more than $\alpha$. Of course, most grid diagrams $G$ will likely be of dimension $\alpha$, because as shown below the Markov chain is more likely to randomly tie a knot than to untie it.

In more detail, transitions may be decided from the following parameters.

• Let $j$ be a integer drawn uniformly from $2$ to $8$ - this is used to decide which Cromwell move to apply, Cromwell moves being one of left/right/up/down cyclic permutations if $2\le j\le 5$, horizontal/vertical transpositions if $6\le j\le 7$, or stabilizations/destabilizations if $j=8$.

• Let $x$, $y$ be integers drawn uniformly from $1$ to $\alpha-1$ - these are used when $6\le j\le 8$ to decide which row/column in the grid diagram to apply transpositions or stabilizations/destablizations, if possible. If the vertex does not allow such a move, then no transition occurs, and the Markov chain simply does a self-loop. Stabilizations increase the grid dimension and require a marker at $(x,y)$. Destabilizations reduce the grid dimension and require an absence of a marker at $(x,y)$ and a presence of a marker at $(x+1,y+1)$, $(x+1,y)$, and $(x,y+1)$. Thus, following the Markov chain, it's easier to randomly tie a knot than to untie the knot.

• Let $k$ be an integer drawn uniformly from $0$ to $3$. This is used to rotate the grid diagram (by $90k$ degrees clockwise) prior to applying the stabilization/destabilization, and rotate it again (by $90k$ degrees counterclockwise) after the stabilization/destabilization.

The authors argue that because each transition can be a permutation of the grid space, the Markov chain is doubly stochastic, hence the limiting distribution will be uniformly distributed.

Thus, given an initial grid diagram $\tilde{G}$ of dimension $\bar{D}$, repeatedly choose random tuples $(j,x,y,k)$ a polynomial number of times, applying the above transitions. Knowing the Lackenby bound, will the distribution be uniform over all grid diagrams equivalent to $\tilde{G}$ of dimension $\le \alpha$, or could there still be some bottleneck? How about if $\tilde{G}$ were known to be of a particular knot type, say the unknot?

• Could you clarify your last paragraph? What is the "diameter" of the graph of Reidemeister moves? Is the graph of Reidemeister moves the graph whose vertices are isotopy-classes of regular planar diagrams and edges Reidemeister moves? Commented Jan 6, 2018 at 3:29
• This question seems tailor-made for Greg Kuperberg. He is active on MO, but you could try e-mailing him directly.
– HJRW
Commented Jan 6, 2018 at 11:50
• @RyanBudney, yes, that's where I was going. Given a knot $K$, the graph I was thinking of had vertices being isotopy classes of $K$ with at most $c$ crossings, and edges one of the Reidemeister moves. The diameter of the graph is the greatest distance between any two vertices. I think Lackenby's results show that the diameter grows polynomially in $c$. Nachmias and Peres have a construction of random graphs showing typically the diameter and the mixing time are polynomially related, but I'm not sure. Commented Jan 6, 2018 at 15:12