There is a famous paper by Childs, et al, in which it is shown that a quantum algorithm can find the name of the exit node for a certain graph in a way that is exponentially faster than any classical algorithm. This speedup assumes an oracle that tells you which nodes are connected to a given node, as well as a labelling of the nodes that prevents the exit name being deduced without navigating the graph.

In the paper, a random labelling of the nodes is used. However, this will presumably prevent the efficient implementation of an oracle.

Is there any cases for which an efficient oracle is known, that allows for the exponential speedup?


1 Answer 1


I often wonder if the welded trees considered in the Childs et al. paper have any applicability to questions in algorithmic knot theory such as knot identification/knot canonization. For example, I envision labeling vertices of the welded tree with specific knot diagrams/grid diagrams, and labeling edges with various Reidemeister moves that go from one diagram to another.

Cleve et al + Reidemeister

Walking along the tree may be somewhat akin to trying to untangle/untie a complicated knot.

For example, one could identify the $\mathrm{ENTRANCE}$ node with a given knot diagram, and the target $\mathrm{EXIT}$ node with some canonical labeling of the given knot. Each edge corresponds to a Reidemeister move.

  • Walking from the left $\mathrm{ENTRANCE}$ to the middle glued region might correspond to performing Reidemeister Type I/II moves that increase the number of crossings, up to an a-priori given maximum crossing number;
  • Walking within the middle corresponds to Type III moves that don't change the crossing number but rather just do over/under slides; and
  • Walking from the middle to the $\mathrm{EXIT}$ node corresponds to performing Type I/II moves that decrease the crossing number.

I think it's the case that a classical walk to simplify a knot by initially making it more complicated with Type I/II moves often gets stuck doing such Type III moves prior to being able to simplify. Perhaps the quantum walk considered by Childs et al. is more likely to find a simpler canonical knot diagram exponentially faster than a classical walk.

The oracle would be instantiated by labeling a knot diagram/grid diagram (corresponding to the basis states of the Hamiltonian), and providing a list of Reidemeister moves available to such a labeling (corresponding to the off-diagonal elements of the Hamiltonian). Certainly these are classically computable in polynomial time - given a knot diagram, one can enumerate all of the available Reidemeister moves.

As opposed to the tree considered by Childs et al., such a Reidemeister graph is not of degree $2$, nor is it even regular, but I sense that the graph is sufficiently sparse that much of the exponential speedup would carry through.

  • $\begingroup$ As far as I can tell, It's not the sparsity but rather the symmetry of the graph that is crucial for the exponential speedup. This might give a problem here. $\endgroup$
    – smapers
    Jan 8, 2021 at 11:48
  • $\begingroup$ Can you explain further? The glued region does not appear symmetrical? $\endgroup$ Jan 8, 2021 at 13:03
  • $\begingroup$ It is symmetric in that a quantum walk starting from the origin will always be in a linear combination of "column states" (uniform superposition over the set of nodes at a fixed distance from the entrance). This effectively reduces the dynamics to that of a quantum walk on a line (see III.C in their paper). $\endgroup$
    – smapers
    Jan 8, 2021 at 13:52
  • $\begingroup$ I think I see your point. Do we know how much of that can that be relaxed and still achieve a quantum super-polynomial speedup? A classical walker along the Reidemeister graph would "know" how close she is to the middle, simply by "knowing" the crossing number of the diagram she's on. But to me it's not clear if she knows how to leverage that to perform the simplifying moves to walk more to the right. $\endgroup$ Jan 8, 2021 at 14:21
  • 1
    $\begingroup$ Nonetheless you are leading me to believe that there's a lot missing in my formalization of the problem. $\endgroup$ Jan 8, 2021 at 17:00

Your Answer

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

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