The Jones and HOMFLY polynomials are link invariants with close connections to quantum computing. It was recently shown that finding a certain approximation to the Jones polynomial of the trace closure of a braid at the fifth root of unity is a complete problem for the one clean qubit complexity class. This is the class of problems solvable in polynomial time on a quantum computer acting on an initial state in which one qubit is pure and the rest are maximally mixed. Here we generalize this result by showing that one clean qubit computers can efficiently approximate the Jones and single-variable HOMFLY polynomials of the trace closure of a braid at any root of unity.

1 aJordan, Stephen, P.1 aWocjan, Pawel uhttp://dl.acm.org/citation.cfm?id=201178701144nas a2200157 4500008004100000245005200041210004800093260001400141300001400155490000700169520070100176100002400877700002300901700001800924856004400942 2007 eng d00aThe limitations of nice mutually unbiased bases0 alimitations of nice mutually unbiased bases c2006/7/11 a111 - 1230 v253 a Mutually unbiased bases of a Hilbert space can be constructed by partitioning a unitary error basis. We consider this construction when the unitary error basis is a nice error basis. We show that the number of resulting mutually unbiased bases can be at most one plus the smallest prime power contained in the dimension, and therefore that this construction cannot improve upon previous approaches. We prove this by establishing a correspondence between nice mutually unbiased bases and abelian subgroups of the index group of a nice error basis and then bounding the number of such subgroups. This bound also has implications for the construction of certain combinatorial objects called nets. 1 aAschbacher, Michael1 aChilds, Andrew, M.1 aWocjan, Pawel uhttp://arxiv.org/abs/quant-ph/0412066v101297nas a2200133 4500008004100000245009900041210006900140260001500209520083300224100002301057700002101080700001801101856004401119 2006 eng d00aWeak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem 0 aWeak FourierSchur sampling the hidden subgroup problem and the q c2006/09/143 a Schur duality decomposes many copies of a quantum state into subspaces labeled by partitions, a decomposition with applications throughout quantum information theory. Here we consider applying Schur duality to the problem of distinguishing coset states in the standard approach to the hidden subgroup problem. We observe that simply measuring the partition (a procedure we call weak Schur sampling) provides very little information about the hidden subgroup. Furthermore, we show that under quite general assumptions, even a combination of weak Fourier sampling and weak Schur sampling fails to identify the hidden subgroup. We also prove tight bounds on how many coset states are required to solve the hidden subgroup problem by weak Schur sampling, and we relate this question to a quantum version of the collision problem. 1 aChilds, Andrew, M.1 aHarrow, Aram, W.1 aWocjan, Pawel uhttp://arxiv.org/abs/quant-ph/0609110v101105nas a2200121 4500008004100000245009900041210006900140260001500209520067400224100002300898700001800921856004400939 2005 eng d00aOn the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems 0 aquantum hardness of solving isomorphism problems as nonabelian h c2005/10/253 a We consider an approach to deciding isomorphism of rigid n-vertex graphs (and related isomorphism problems) by solving a nonabelian hidden shift problem on a quantum computer using the standard method. Such an approach is arguably more natural than viewing the problem as a hidden subgroup problem. We prove that the hidden shift approach to rigid graph isomorphism is hard in two senses. First, we prove that Omega(n) copies of the hidden shift states are necessary to solve the problem (whereas O(n log n) copies are sufficient). Second, we prove that if one is restricted to single-register measurements, an exponential number of hidden shift states are required. 1 aChilds, Andrew, M.1 aWocjan, Pawel uhttp://arxiv.org/abs/quant-ph/0510185v1