



@article {1402,
	title = {Testing quantum expanders is co-QMA-complete},
	journal = {Physical Review A},
	volume = {87},
	year = {2013},
	month = {2013/4/15},
	abstract = {  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.
},
	doi = {10.1103/PhysRevA.87.042317},
	url = {http://arxiv.org/abs/1210.0787v2},
	author = {Adam D. Bookatz and Stephen P. Jordan and Yi-Kai Liu and Pawel Wocjan}
}
@article {1386,
	title = {Efficient quantum circuits for arbitrary sparse unitaries},
	journal = {Physical Review A},
	volume = {80},
	year = {2009},
	month = {2009/12/1},
	abstract = {  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.
},
	doi = {10.1103/PhysRevA.80.062301},
	url = {http://arxiv.org/abs/0904.2211v2},
	author = {Stephen P. Jordan and Pawel Wocjan}
}
@article {1384,
	title = {Estimating Jones and HOMFLY polynomials with One Clean Qubit},
	journal = {Quantum Information and Computation},
	volume = {9},
	year = {2009},
	month = {2009/03/01},
	pages = {264-289},
	abstract = {<p>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.</p>},
	url = {http://dl.acm.org/citation.cfm?id=2011787},
	author = {Stephen P. Jordan and Pawel Wocjan}
}
@article {1214,
	title = {The limitations of nice mutually unbiased bases},
	journal = {Journal of Algebraic Combinatorics},
	volume = {25},
	year = {2007},
	month = {2006/7/11},
	pages = {111 - 123},
	abstract = {  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.
},
	doi = {10.1007/s10801-006-0002-y},
	url = {http://arxiv.org/abs/quant-ph/0412066v1},
	author = {Michael Aschbacher and Andrew M. Childs and Pawel Wocjan}
}
@article {1241,
	title = {Weak Fourier-Schur sampling, the hidden subgroup problem, and the  quantum collision problem
},
	year = {2006},
	month = {2006/09/14},
	abstract = {  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.
},
	doi = {10.1007/978-3-540-70918-3_51},
	url = {http://arxiv.org/abs/quant-ph/0609110v1},
	author = {Andrew M. Childs and Aram W. Harrow and Pawel Wocjan}
}
@article {1216,
	title = {On the quantum hardness of solving isomorphism problems as nonabelian  hidden shift problems
},
	year = {2005},
	month = {2005/10/25},
	abstract = {  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.
},
	url = {http://arxiv.org/abs/quant-ph/0510185v1},
	author = {Andrew M. Childs and Pawel Wocjan}
}
