首页> 外文期刊>Algorithmica >A Polynomial Quantum Algorithm for Approximating the Jones Polynomial
【24h】

A Polynomial Quantum Algorithm for Approximating the Jones Polynomial

机译:逼近琼斯多项式的多项式量子算法

获取原文
获取原文并翻译 | 示例

摘要

The Jones polynomial, discovered in 1984, is an important knot invariant in topology. Among its many connections to various mathematical and physical areas, it is known (due to Witten) to be intimately connected to Topological Quantum Field Theory ( sfTQFT{sf{TQFT}} ). The works of Freedman, Kitaev, Larsen and Wang provide an efficient simulation of sfTQFT{sf{TQFT}} by a quantum computer, and vice versa. These results implicitly imply the existence of an efficient (namely, polynomial) quantum algorithm that provides a certain additive approximation of the Jones polynomial at the fifth root of unity, e 2π i/5, and moreover, that this problem is sfBQP{sf{BQP}} -complete. Unfortunately, this important algorithm was never explicitly formulated. Moreover, the results of Freedman et al. are heavily based on sfTQFT{sf{TQFT}} , which makes the algorithm essentially inaccessible to computer scientists. We provide an explicit and simple polynomial quantum algorithm to approximate the Jones polynomial of an n strands braid with m crossings at any primitive root of unity e 2π i/k , where the running time of the algorithm is polynomial in m, n and k. Our algorithm is based, rather than on sfTQFT{sf{TQFT}} , on well known mathematical results (specifically, the path model representation of the braid group and the uniqueness of the Markov trace for the Temperley-Lieb algebra). By the results of Freedman et al., our algorithm solves a sfBQP{sf{BQP}} complete problem.
机译:1984年发现的Jones多项式是拓扑中的一个重要结不变式。在与各种数学和物理领域的众多联系中,众所周知(由于维滕),它与拓扑量子场论(sfTQFT {sf {TQFT}})有密切的联系。 Freedman,Kitaev,Larsen和Wang的作品通过量子计算机提供了sfTQFT {sf {TQFT}}的高效仿真,反之亦然。这些结果暗含暗示了一种有效的(即多项式)量子算法的存在,该算法在单位5的根e 2πi / 5 上提供了琼斯多项式的某种加法近似,并且,此问题是sfBQP {sf {BQP}}-完成。不幸的是,这一重要算法从未明确提出。此外,Freedman等人的结果。很大程度上基于sfTQFT {sf {TQFT}},这使得该算法对于计算机科学家而言基本上不可访问。我们提供了一种简单明了的多项式量子算法,可以近似地计算n股辫子的Jones多项式在单位e 2πi / k 的任何本原根处有m个交叉,其中算法的运行时间是多项式在m,n和k中。我们的算法不是基于sfTQFT {sf {TQFT}},而是基于众所周知的数学结果(特别是辫子组的路径模型表示和Temperley-Lieb代数的Markov迹线的唯一性)。根据Freedman等人的结果,我们的算法解决了sfBQP {sf {BQP}}完全问题。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号