Permutational Quantum Computing (Jordan, 2009) is a natural quantum computational model that was conjectured to capture non-classical aspects of quantum computation. Contrary to the previous conjecture, we find a classical algorithm that efficiently approximates output distributions of the model up to polynomially small additive precision. We extend this algorithm to show that a large class of important quantum circuits - the Quantum Schur Sampling circuits - can be also efficiently simulated classically. The algorithm can be used to efficiently estimate non-trivial elements of irreducible representation matrices of the symmetric group on $n$ elements and might be also used to approximate transition amplitudes of the Ponzano-Regge model.

http://arxiv.org/abs/1801.04795http://arxiv.org/pdf/1801.04795.pdf

## 0 comments