  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.
