2006/05/31 by Dorit Aharonov, Itai Arad · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Advanced Combinatorial Mathematics #Algebraic structures and combinatorial models #Combinatorics #Discrete mathematics #Freedman #Jones polynomial #Knot theory #Law #Lemma (botany) #Mathematics #Multiplicative function #Physics #Quantum Computing Algorithms and Architecture #Quantum mechanics #Universality (dynamical systems) #cs.CC #quant-ph
paper · pdf · doi:10.1088/1367-2630/13/3/035019
published as New J. Phys. 13 (2011) 035019 · 36 pages, 8 figures. A much improved and revised version, updated to Feb 2011, which includes discussions and implications of related results published after the original 2006 version of this paper
arxiv created 2011/02/19 · openalex publication_date 2011/03/23 · arxiv updated 2011/03/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
A celebrated important result due to Freedman et al (2002 Commun. Math. Phys. 227 605–22) states that providing additive approximations of the Jones polynomial at the k th root of unity, for constant k =5 and k ⩾7, is BQP-hard. Together with the algorithmic results of Aharonov et al (2005) and Freedman et al (2002 Commun. Math. Phys. 227 587–603), this gives perhaps the most natural BQP-complete problem known today and motivates further study of the topic. In this paper, we focus on the universality proof; we extend the result of Freedman et al (2002) to k s that grow polynomially with the number of strands and crossings in the link, thus extending the BQP-hardness of Jones polynomial approximations to all values to which the AJL algorithm applies (Aharonov et al 2005), proving that for all those values, the problems are BQP-complete. As a side benefit, we derive a fairly elementary proof of the Freedman et al density result, without referring to advanced results from Lie algebra representation theory, making this important result accessible to a wider audience in the computer science research community. We make use of two general lemmas we prove, the bridge lemma and the decoupling lemma , which provide tools for establishing the density of subgroups in SU( n ). Those tools seem to be of independent interest in more general contexts of proving the quantum universality. Our result also implies a completely classical statement, that the multiplicative approximations of the Jones polynomial, at exactly the same values, are #P-hard, via a recent result due to Kuperberg (2009 arXiv:0908.0512). Since the first publication of those results in their preliminary form (Aharonov and Arad 2006 arXiv:quant-ph/0605181), the methods we present here have been used in several other contexts (Aharonov and Arad 2007 arXiv:quant-ph/0702008; Peter and Stephen 2008 Quantum Inf. Comput. 8 681). The present paper is an improved and extended version of the results presented by Aharonov and Arad (2006) and includes discussions of the developments since then.