Permutational Quantum Computing

Abstract

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.

25 pages, 8 figures

References in corpus (7)

• Universal computation by quantum walk
• Leo V: A Companion of a Companion of the Milky Way Galaxy
• Quantum Computation Beyond the Circuit Model
• Efficient quantum circuits for arbitrary sparse unitaries
• Scalable Superconducting Architecture for Adiabatic Quantum Computation
• Computation with Unitaries and One Pure Qubit
• Fast quantum algorithms for approximating some irreducible representations of groups

Cited by in corpus (4)

• Contextuality in Measurement-based Quantum Computation
• Quantum gradient descent for linear systems and least squares
• Commuting quantum circuits: efficient classical simulations versus hardness results
• The Computational Complexity of Ball Permutations