%0 Journal Article %J Physical Review A %D 2013 %T Testing quantum expanders is co-QMA-complete %A Adam D. Bookatz %A Stephen P. Jordan %A Yi-Kai Liu %A Pawel Wocjan %X A quantum expander is a unital quantum channel that is rapidly mixing, has only a few Kraus operators, and can be implemented efficiently on a quantum computer. We consider the problem of estimating the mixing time (i.e., the spectral gap) of a quantum expander. We show that this problem is co-QMA-complete. This has applications to testing randomized constructions of quantum expanders, and studying thermalization of open quantum systems. %B Physical Review A %V 87 %8 2013/4/15 %G eng %U http://arxiv.org/abs/1210.0787v2 %N 4 %! Phys. Rev. A %R 10.1103/PhysRevA.87.042317 %0 Journal Article %J Physical Review A %D 2009 %T Efficient quantum circuits for arbitrary sparse unitaries %A Stephen P. Jordan %A Pawel Wocjan %X Arbitrary exponentially large unitaries cannot be implemented efficiently by quantum circuits. However, we show that quantum circuits can efficiently implement any unitary provided it has at most polynomially many nonzero entries in any row or column, and these entries are efficiently computable. One can formulate a model of computation based on the composition of sparse unitaries which includes the quantum Turing machine model, the quantum circuit model, anyonic models, permutational quantum computation, and discrete time quantum walks as special cases. Thus we obtain a simple unified proof that these models are all contained in BQP. Furthermore our general method for implementing sparse unitaries simplifies several existing quantum algorithms. %B Physical Review A %V 80 %8 2009/12/1 %G eng %U http://arxiv.org/abs/0904.2211v2 %N 6 %! Phys. Rev. A %R 10.1103/PhysRevA.80.062301 %0 Journal Article %J Quantum Information and Computation %D 2009 %T Estimating Jones and HOMFLY polynomials with One Clean Qubit %A Stephen P. Jordan %A Pawel Wocjan %X

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.

%B Quantum Information and Computation %V 9 %P 264-289 %8 2009/03/01 %G eng %U http://dl.acm.org/citation.cfm?id=2011787 %N 3 %0 Journal Article %J Journal of Algebraic Combinatorics %D 2007 %T The limitations of nice mutually unbiased bases %A Michael Aschbacher %A Andrew M. Childs %A Pawel Wocjan %X 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. %B Journal of Algebraic Combinatorics %V 25 %P 111 - 123 %8 2006/7/11 %G eng %U http://arxiv.org/abs/quant-ph/0412066v1 %N 2 %! J Algebr Comb %R 10.1007/s10801-006-0002-y %0 Journal Article %D 2006 %T Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem %A Andrew M. Childs %A Aram W. Harrow %A Pawel Wocjan %X 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. %8 2006/09/14 %G eng %U http://arxiv.org/abs/quant-ph/0609110v1 %! Proc. 24th Symposium on Theoretical Aspects of Computer Science (STACS 2007) %R 10.1007/978-3-540-70918-3_51 %0 Journal Article %D 2005 %T On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems %A Andrew M. Childs %A Pawel Wocjan %X 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. %8 2005/10/25 %G eng %U http://arxiv.org/abs/quant-ph/0510185v1 %! Quantum Information and Computation