Quantum Schur Sampling is Classically Tractable


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.
Submitted 15 Jan 2018 to Quantum Physics [quant-ph]
Published 16 Jan 2018