A Caltech Library Service

Permutational quantum computing

Jordan, Stephen P. (2010) Permutational quantum computing. Quantum Information and Computation, 10 (5-6). pp. 470-497. ISSN 1533-7146.

[img] PDF - Published Version
Restricted to Repository administrators only
See Usage Policy.


Use this Persistent URL to link to this item:


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 approximate certain transition amplitudes from the Ponzano-Regge spin foam model of quantum gravity. No polynomial time classical algorithms for these problems are known.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2010 Rinton Press. Received June 18, 2009. Revised January 31, 2010. Communicated by: S Braunstein & R Laflamme. In doing the work reported in this paper, I have benefitted from conversations with numerous people. I especially thank Laurent Freidel, Gorjan Alagic, and Liang Kong. I gratefully acknowledge support from the Sherman Fairchild foundation and the National Science Foundation under grant PHY-0803371, as well as the hospitality of the Perimeter Institute.
Funding AgencyGrant Number
Sherman Fairchild foundationUNSPECIFIED
Issue or Number:5-6
Record Number:CaltechAUTHORS:20100526-101647200
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:18452
Deposited By: Tony Diaz
Deposited On:20 Jun 2010 19:25
Last Modified:03 Oct 2019 01:42

Repository Staff Only: item control page