



00882nas a2200157   4500008004100000245004900041210004700090260001400137490000700151520044900158100002200607700002400629700001600653700001800669856003700687       2013                        eng d00aTesting quantum expanders is co-QMA-complete0 aTesting quantum expanders is coQMAcomplete  c2013/4/150 v873 a  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.
1 aBookatz, Adam, D.1 aJordan, Stephen, P.1 aLiu, Yi-Kai1 aWocjan, Pawel  uhttp://arxiv.org/abs/1210.0787v201162nas a2200133   4500008004100000245006200041210006200103260001400165490000700179520076300186100002400949700001800973856003700991       2009                        eng d00aEfficient quantum circuits for arbitrary sparse unitaries0 aEfficient quantum circuits for arbitrary sparse unitaries  c2009/12/10 v803 a  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.
1 aJordan, Stephen, P.1 aWocjan, Pawel  uhttp://arxiv.org/abs/0904.2211v201125nas a2200145   4500008004100000245006500041210006500106260001500171300001200186490000600198520068700204100002400891700001800915856004600933       2009                        eng d00aEstimating Jones and HOMFLY polynomials with One Clean Qubit0 aEstimating Jones and HOMFLY polynomials with One Clean Qubit  c2009/03/01  a264-2890 v93 a<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>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