



01293nas a2200133   4500008004100000245003600041210003600077260001500113300001200128490000700140520094200147100002401089856004601113       2010                        eng d00aPermutational Quantum Computing0 aPermutational Quantum Computing  c2010/05/01  a470-4970 v103 a<p>In topological quantum computation the geometric details of a particle trajectory are irrelevant; only the topology matters. Taking this one step further, we consider a model of computation that disregards even the topology of the particle trajectory, and computes by permuting particles. Whereas topological quantum computation requires anyons, permutational quantum computation can be performed with ordinary spin-1/2 particles, using a variant of the spin-network scheme of Marzuoli and Rasetti. We do not know whether permutational computation is universal. It may represent a new complexity class within BQP. Nevertheless, permutational quantum computers can in polynomial time approximate matrix elements of certain irreducible representations of the symmetric group and simulate certain processes in the Ponzano-Regge spin foam model of quantum gravity. No polynomial time classical algorithms for these problems are known.</p>1 aJordan, Stephen, P.  uhttp://dl.acm.org/citation.cfm?id=2011369