The BQP-hardness of approximating the Jones polynomial
The BQP-hardness of approximating the Jones polynomial
复制标题
近似琼斯多项式的 BQP 硬度
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
I. Arad
中科院分区：
文献类型：
--
作者：
D. Aharonov;I. Arad
Freedman等人（2002 Commun. Math.Phys.227605 -22）指出，对于常数k=5和k ≥ 7，在单位的k次方根处提供琼斯多项式的加法近似是BQP困难的。结合Aharonov等人（2005）和Freedman等人（2002 Commun.数学物理227 587-603），这可能是当今已知的最自然的BQP-完全问题，并激发了对该主题的进一步研究。在本文中，我们专注于普适性证明;我们将Freedman et al（2002）的结果扩展到随链和交叉数多项式增长的ks，从而将Jones多项式近似的BQP-困难性扩展到AJL算法适用的所有值（Aharonov et al 2005），证明对于所有这些值，问题都是BQP-完全的。作为一个附带的好处，我们得到了一个相当初级的证明弗里德曼等人的密度结果，没有提到先进的结果从李代数表示理论，使这一重要的结果，更广泛的受众在计算机科学研究界。我们利用两个一般引理，我们证明，桥引理和去耦引理，这提供了建立SU（n）中的子群密度的工具。这些工具似乎在证明量子普适性的更一般的背景下具有独立的兴趣。我们的结果也暗示了一个完全经典的陈述，即琼斯多项式的乘法近似，在完全相同的值，是#P-hard的，通过最近的结果由于Kuperberg（2009 arXiv：0908.0512）。自从这些结果以其初步形式首次发表以来（Aharonov和Arad 2006 arXiv：quant-ph/0605181），我们在这里提出的方法已被用于其他几种情况下（Aharonov和Arad 2007 arXiv：quant-ph/0702008; Peter和Stephen 2008 Quantum Inf. 8 681）。本文是Aharonov和Arad（2006）提出的结果的改进和扩展版本，并包括自那时以来的发展讨论。
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 kth 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 ks 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.