Quantum Schur Sampling Circuits can be Strongly Simulated


Permutational Quantum Computing (PQC) [\emphQuantum~Info.~Comput., \textbf10, 470--497, (2010)] is a natural quantum computational model conjectured to capture non-classical aspects of quantum computation. An argument backing this conjecture was the observation that there was no efficient classical algorithm for estimation of matrix elements of the $S_n$ irreducible representation matrices in the Young's orthogonal form, which correspond to transition amplitudes of a broad class of PQC circuits. This problem can be solved with a PQC machine in polynomial time, but no efficient classical algorithm for the problem was previously known. Here we give a classical algorithm that efficiently approximates the transition amplitudes up to polynomial additive precision and hence solves this problem. We further extend our discussion to show that transition amplitudes of a broader class of quantum circuits -- the Quantum Schur Sampling circuits -- can be also efficiently estimated classically.
Submitted 15 Jan 2018 to Quantum Physics [quant-ph]
Published 16 Jan 2018
Updated 16 May 2018
Author comments: Precision error and additional slip-ups corrected. Title changed to avoid confusion