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.

VL - 9 U4 - 264-289 UR - http://dl.acm.org/citation.cfm?id=2011787 CP - 3 ER - TY - JOUR T1 - The limitations of nice mutually unbiased bases JF - Journal of Algebraic Combinatorics Y1 - 2007 A1 - Michael Aschbacher A1 - Andrew M. Childs A1 - Pawel Wocjan AB - 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. VL - 25 U4 - 111 - 123 UR - http://arxiv.org/abs/quant-ph/0412066v1 CP - 2 J1 - J Algebr Comb U5 - 10.1007/s10801-006-0002-y ER - TY - JOUR T1 - Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem Y1 - 2006 A1 - Andrew M. Childs A1 - Aram W. Harrow A1 - Pawel Wocjan AB - 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. UR - http://arxiv.org/abs/quant-ph/0609110v1 J1 - Proc. 24th Symposium on Theoretical Aspects of Computer Science (STACS 2007) U5 - 10.1007/978-3-540-70918-3_51 ER - TY - JOUR T1 - On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems Y1 - 2005 A1 - Andrew M. Childs A1 - Pawel Wocjan AB - 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. UR - http://arxiv.org/abs/quant-ph/0510185v1 J1 - Quantum Information and Computation ER -