Quantum Schur Sampling Circuits can be Strongly Simulated

Permutational quantum computing (PQC) [Quantum Inf. Comput., 10, 470–497 (2010)] is a natural quantum computational model conjectured to capture nonclassical 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 also be efficiently classically approximated.

Figure 1

Permutational Quantum Computing. The “program” $\pi$ consists of a set of permutations executed between $$$U_{\mathsf{Sch}}$ and $U_{\mathsf{Sch}}^{†}$.