Hari Krovi, Alexander Russell
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 D(G). These arise directly from topological quantum computation. Regarding algorithms for these invariants, we develop quantum circuits for the quantum Fourier transform over 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 D(G). With this Fourier transform, it is straightforward to obtain additive approximation algorithms for link invariants. Next, we provide efficient quantum circuits for the Clebsch-Gordan transform over D(G) for fluxon irreps i.e., irreps depending on a conjugacy class. For other irreps, we present an efficient implementation under certain conditions such as when there is an efficient CG transform over the centralizers. We remark that this also provides a simulation of anyonic models of quantum computation, even in circumstances where the group may have size exponential in the size of the circuit. As for hardness results, first we note that in contrast to those such as the Jones polynomial, where the image of the braid group representations is dense in the unitary group, the image of the representations arising from D(G) is finite. This important difference appears to be directly reflected in the complexity of these invariants. In contrast to "dense" invariants, we show that some D(G) invariants are BPP hard to additively approximate, SBP hard to multiplicatively approximate, and #P hard to exactly evaluate. To show this, we prove that the probability of success of any randomized computation can be approximated to within any \epsilon by the plat closure.
View original:
http://arxiv.org/abs/1210.1550
No comments:
Post a Comment