Estimating Jones polynomials is a complete problem for one clean qubit
Estimating Jones polynomials is a complete problem for one clean qubit
复制标题
对于一个干净的量子位来说，估计琼斯多项式是一个完整的问题
DOI：
10.26421/qic8.8-9-1
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
S. Jordan
中科院分区：
文献类型：
--
作者：
P. Shor;S. Jordan
众所周知，计算辫子的平面闭合的琼斯多项式的某种近似是BQP-完全问题。也就是说，这个问题正好抓住了量子电路模型的力量[13，3，1]。一个干净的量子比特模型是一种量子计算模型，其中除了一个量子比特之外的所有量子比特都以最大混合态开始。一个干净的量子比特计算机被认为比标准的量子计算机要弱，但仍然能够解决一些经典的棘手问题[21]。在这里，我们表明，评估一定的近似琼斯多项式在第五个根的单位的辫子的跟踪封闭是一个完整的问题，一个干净的量子比特复杂性类。也就是说，一个干净的量子位计算机可以在链的数量和交叉的数量两者上以时间多项式近似这些琼斯多项式，并且模拟一个干净的量子位计算机的问题可以简化为近似编织物的迹线闭合的琼斯多项式。
It is known that evaluating a certain approximation to the Jones polynomial for the plat closure of a braid is a BQP-complete problem. That is, this problem exactly captures the power of the quantum circuit model[13, 3, 1]. The one clean qubit model is a model of quantum computation in which all but one qubit starts in the maximally mixed state. One clean qubit computers are believed to be strictly weaker than standard quantum computers, but still capable of solving some classically intractable problems [21]. Here we show that evaluating a certain approximation to the Jones polynomial at a fifth root of unity for the trace closure of a braid is a complete problem for the one clean qubit complexity class. That is, a one clean qubit computer can approximate these Jones polynomials in time polynomial in both the number of strands and number of crossings, and the problem of simulating a one clean qubit computer is reducible to approximating the Jones polynomial of the trace closure of a braid.