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.

Author comments: Precision error and additional slip-ups corrected. Title changed to avoid confusionhttp://arxiv.org/abs/1801.04795

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

https://arxiv-vanity.com/papers/1801.04795

## 0 comments