Quantum Fourier Transforms and the Complexity of Link Invariants for Quantum Doubles of Finite Groups
Quantum Fourier Transforms and the Complexity of Link Invariants for Quantum Doubles of Finite Groups
复制标题
量子傅里叶变换和有限群量子双偶的链接不变量的复杂性
DOI：
10.1007/s00220-014-2285-5
复制
发表时间：
2012
影响因子：
2.4
通讯作者：
A. Russell
中科院分区：
文献类型：
--
作者：
H. Krovi;A. 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 [denoted D(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(G)}}$$\end{document}, 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 D(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(G)}}$$\end{document}; 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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(G)}}$$\end{document}. We apply these results to the symmetric groups to yield efficient circuits for the quantum Fourier transform over D(Sn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(S_n)}}$$\end{document}. 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 D(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(G)}}$$\end{document} are finite. This important difference appears to be directly reflected in the complexity of these invariants. While additively approximating “dense” invariants is BQP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{BQP}}}$$\end{document}-complete and multiplicatively approximating them is #P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\#\mathsf{P}}}$$\end{document}-complete, we show that certain D(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(G)}}$$\end{document} invariants (such as D(An)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(A_n)}}$$\end{document} invariants) are BPP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{BPP}}}$$\end{document}-hard to additively approximate, SBP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{SBP}}}$$\end{document}-hard to multiplicatively approximate, and #P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\#\mathsf{P}}}$$\end{document}-hard to exactly evaluate. To show this, we prove that, for groups (such as An) which satisfy certain properties, the probability of success of any randomized computation can be approximated to within any ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varepsilon}$$\end{document} 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 D(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(G)}}$$\end{document} for “fluxon” irreps, i.e., irreps of D(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(G)}}$$\end{document} characterized by a conjugacy class of G. For general irreps, i.e., those which are associated with a conjugacy class of Gand 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.
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 D(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(G)}}$$\end{document}, 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 D(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(G)}}$$\end{document}; 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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(G)}}$$\end{document}. We apply these results to the symmetric groups to yield efficient circuits for the quantum Fourier transform over D(Sn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(S_n)}}$$\end{document}. 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 D(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(G)}}$$\end{document} are finite. This important difference appears to be directly reflected in the complexity of these invariants. While additively approximating “dense” invariants is BQP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{BQP}}}$$\end{document}-complete and multiplicatively approximating them is #P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\#\mathsf{P}}}$$\end{document}-complete, we show that certain D(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(G)}}$$\end{document} invariants (such as D(An)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(A_n)}}$$\end{document} invariants) are BPP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{BPP}}}$$\end{document}-hard to additively approximate, SBP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{SBP}}}$$\end{document}-hard to multiplicatively approximate, and #P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\#\mathsf{P}}}$$\end{document}-hard to exactly evaluate. To show this, we prove that, for groups (such as An) which satisfy certain properties, the probability of success of any randomized computation can be approximated to within any ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varepsilon}$$\end{document} 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 D(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(G)}}$$\end{document} for “fluxon” irreps, i.e., irreps of D(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathsf{D}(G)}}$$\end{document} characterized by a conjugacy class of G. For general irreps, i.e., those which are associated with a conjugacy class of Gand 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.