



01327nas a2200157   4500008004100000245009200041210006900133260001400202490000700216520082400223100001901047700002401066700001901090700002301109856003701132       2010                        eng d00aApproximating Turaev-Viro 3-manifold invariants is universal for quantum  computation
0 aApproximating TuraevViro 3manifold invariants is universal for q  c2010/10/80 v823 a  The Turaev-Viro invariants are scalar topological invariants of compact,
orientable 3-manifolds. We give a quantum algorithm for additively
approximating Turaev-Viro invariants of a manifold presented by a Heegaard
splitting. The algorithm is motivated by the relationship between topological
quantum computers and (2+1)-D topological quantum field theories. Its accuracy
is shown to be nontrivial, as the same algorithm, after efficient classical
preprocessing, can solve any problem efficiently decidable by a quantum
computer. Thus approximating certain Turaev-Viro invariants of manifolds
presented by Heegaard splittings is a universal problem for quantum
computation. This establishes a novel relation between the task of
distinguishing non-homeomorphic 3-manifolds and the power of a general quantum
computer.
1 aAlagic, Gorjan1 aJordan, Stephen, P.1 aKoenig, Robert1 aReichardt, Ben, W.  uhttp://arxiv.org/abs/1003.0923v100984nas a2200145   4500008004100000245009600041210006900137260001500206520048900221100002300710700002300733700001900756700001900775856004400794       2007                        eng d00aEvery NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a  quantum computer
0 aEvery NAND formula of size N can be evaluated in time N 12o1 on   c2007/03/023 a  For every NAND formula of size N, there is a bounded-error N^{1/2+o(1)}-time
quantum algorithm, based on a coined quantum walk, that evaluates this formula
on a black-box input. Balanced, or ``approximately balanced,'' NAND formulas
can be evaluated in O(sqrt{N}) queries, which is optimal. It follows that the
(2-o(1))-th power of the quantum query complexity is a lower bound on the
formula size, almost solving in the positive an open problem posed by Laplante,
Lee and Szegedy.
1 aChilds, Andrew, M.1 aReichardt, Ben, W.1 aSpalek, Robert1 aZhang, Shengyu  uhttp://arxiv.org/abs/quant-ph/0703015v3