13
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Ryan Budney Jan 6 '18 at 3:29
  • 1
    $\begingroup$ This question seems tailor-made for Greg Kuperberg. He is active on MO, but you could try e-mailing him directly. $\endgroup$ – HJRW Jan 6 '18 at 11:50
  • $\begingroup$ @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. $\endgroup$ – Mark S Jan 6 '18 at 15:12
6
$\begingroup$

Thanks to HJRW2 for the flattering invitation here, and I will give an answer, but it might be not all that deep. In fact I haven't been on MO much lately; maybe I should visit it more.

I don't see any basis to say that Lackenby's result proves the mixing property of the quantum mixing proposal. There are many graphs where the diameter is better understood than the mixing time. Lackenby's methods are based on Dynnikov monotonicity for grid diagrams, and for that reason and others there isn't any statement about getting from here to there with random moves.

The picture is even worse for other knot types, since the exponent in Lackenby's polynomial bound depends on the knot type.

Nonetheless you can fairly say that it lends some credence to the mixing time question, at least for the unknot. Lackenby's bounds are spectacular, but no one thinks that they are sharp. Moreover no one knows how to make examples of the unknotting problem that look hard, i.e., nothing like the RSA factoring challenges with money at stake. An algorithm with a rigorous bound on running time is hard, but that's not the same thing. The graph isomorphism problem was in the same state of deadlock before Babai's algorithm.

On the other hand the quantum money from knots protocol would need more credibility than just the mixing time proposal for people to trust it. It's perfectly respectable as a provocative proposal, but I don't know that it's convicing, at least not yet. There is another quantum money proposal due to Aaronson and Christiano that could be more convincing; on the other hand it's less glamorous in that it uses linear algebra over finite fields rather than knot theory.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.