Summary: Knot and link invariants naturally arise from any braided Hopf algebra. We consider the computational complexity of the invariants arising from an elementary family of finite-dimensional Hopf algebras: quantum doubles of finite groups [denoted \(\mathsf D(G)\), for a group \(G\)]. These induce a rich family of knot invariants and, additionally, are directly related to topological quantum computation.
Regarding algorithms for these invariants, we develop quantum circuits for the quantum Fourier transform over \(\mathsf D(G)\); in general, we show that when one can uniformly and efficiently carry out the quantum Fourier transform over the centralizers \(Z(g)\) of the elements of \(G\), one can efficiently carry out the quantum Fourier transform over \(\mathsf D(G)\). We apply these results to the symmetric groups to yield efficient circuits for the quantum Fourier transform over \(\mathsf D(S_n)\). With such a Fourier transform, it is straightforward to obtain additive approximation algorithms for the related link invariant.
As for hardness results, first we note that in contrast to those concerning the Jones polynomial – where the images of the braid group representations are dense in the unitary group – the images of the representations arising from \(\mathsf D(G)\) are finite. This important difference appears to be directly reflected in the complexity of these invariants. While additively approximating “dense” invariants is \(\mathsf{BQP}\)-complete and multiplicatively approximating them is \(\#\mathsf P\)-complete, we show that certain \(\mathsf D(G)\) invariants (such as \(\mathsf D(A_n)\) invariants) are \(\mathsf{BPP}\)-hard to additively approximate, \(\mathsf{SBP}\)-hard to multiplicatively approximate, and \(\#\mathsf P\)-hard to exactly evaluate. To show this, we prove that, for groups (such as \(A_n\)) which satisfy certain properties, the probability of success of any randomized computation can be approximated to within any \(\varepsilon\) by the plat closure.
Finally, we make partial progress on the question of simulating anyonic computation in groups uniformly as a function of the group size. In this direction, we provide efficient quantum circuits for the Clebsch-Gordan transform over \(\mathsf D(G)\) for “fluxon” irreps, i.e., irreps of \(\mathsf D(G)\) characterized by a conjugacy class of \(G\). For general irreps, i.e., those which are associated with a conjugacy class of \(G\) and an irrep of a centralizer, we present an efficient implementation under certain conditions, such as when there is an efficient Clebsch-Gordan transform over the centralizers (this could be a hard problem for some groups). We remark that this also provides a simulation of certain anyonic models of quantum computation, even in circumstances where the group may have size exponential in the size of the circuit.