Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups

DOI10.1007/S00220-014-2285-5MaRDI QIDQ2258015zbMATH OpenOpenAlexFDO

Authors Hari Krovi, Alexander Russell

Publication date 2 March 2015

Published in Communications in Mathematical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.1550

Mathematics Subject Classification ID

Hopf algebras and their applications (16T05) Numerical methods for discrete and fast Fourier transforms (65T50) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: 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), for a group G). 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). We apply these results to the symmetric groups to yield efficient circuits for the quantum Fourier transform over D(S_n). With such a Fourier transform, it is straightforward to obtain additive approximation algorithms for the related link invariant. Additionally, we show that certain D(G) invariants (such as D(A_n) invariants) are BPP-hard to additively approximate, SBP-hard to multiplicatively approximate, and #P-hard to exactly evaluate. 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) for "fluxon" irreps, i.e., irreps of 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. 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.

Recommendations

• The Jones polynomial: quantum algorithms and applications in quantum complexity theory
• Quantum Computation of Universal Link Invariants
• A polynomial quantum algorithm for approximating the Jones polynomial
• A polynomial quantum algorithm for approximating the Jones polynomial
• Unitary representations of the Artin braid groups and quantum algorithms for colored Jones polynomials and the Witten-Reshetikhin invariant

Cites work

• A modular functor which is universal for quantum computation
• A polynomial quantum algorithm for approximating the Jones polynomial
• A Property of Finite Simple Non-Abelian Groups
• A quantum groups primer
• Approximate Counting and Quantum Computation
• Braid group representations from twisted quantum doubles of finite groups.
• EXTRASPECIAL 2-GROUPS AND IMAGES OF BRAID GROUP REPRESENTATIONS
• Fault-tolerant quantum computation by anyons
• Homomorphs of Knot Groups
• How hard is it to approximate the Jones polynomial?
• scientific article; zbMATH DE number 3552764 (Why is no real title available?)
• scientific article; zbMATH DE number 706259 (Why is no real title available?)
• scientific article; zbMATH DE number 1559521 (Why is no real title available?)
• scientific article; zbMATH DE number 1406140 (Why is no real title available?)
• scientific article; zbMATH DE number 3212917 (Why is no real title available?)
• scientific article; zbMATH DE number 3021610 (Why is no real title available?)
• Introduction to topological quantum computation
• Localization of unitary braid group representations
• Mathematical Foundations of Computer Science 2003
• Non-uniform automata over groups
• On metaplectic modular categories and their applications
• On the Stable Equivalence of Plat Representations of Knots and Links
• Quantum computation with Turaev-Viro codes
• Quantum computing, postselection, and probabilistic polynomial-time
• Quantum double finite group algebras and link polynomials
• Quantum double finite group algebras and their representations
• Quantum geometry and quantum algorithms
• Quasi Hopf algebras, group cohomology and orbifold models
• Simulation of topological field theories by quantum computers
• Studying links via closed braids. I: A finiteness theorem
• The BQP-hardness of approximating the Jones polynomial
• The Jones polynomial: quantum algorithms and applications in quantum complexity theory
• Topological quantum computation
• Two paradigms for topological quantum computation

Cited in

(6)

• Computational complexity and 3-manifolds and zombies
• Coloring invariants of knots and links are often intractable
• On metaplectic modular categories and their applications
• Quantum Fourier transform over symmetric groups -- improved result
• Fourier transform and the Verlinde formula for the quantum double of a finite group
• An algorithm for Tambara-Yamagami quantum invariants of 3-manifolds, parameterized by the first Betti number

This page was built for publication: Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2258015)