Quantum Computation with Quantum Schur Circuits*

Many quantum algorithms can be given as reversible classical circuits between a pair of quantum Fourier transformations. Here we study quantum circuits where QFT is substituted by the quantum Schur transform. This is motivated by Permutational Quantum Computing, a restricted computational model believed to capture nonclassical features of quantum computing.

A problem supporting this belief was the efficient approximation of matrix elements of the Young orthogonal matrices. While solvable efficiently with PQC, there was no efficient classical algorithm for this task. We give such algorithm by showing that the relevant PQC computation is a quantum Schur circuit and using symmetries of the Schur transformation.

Efficient classical approximation of transition amplitudes however does not mean that the circuits can be also efficiently sampled. We hence prove that quantum Schur sampling circuits with sparse enough output can be sampled from efficiently classically. Numerical study on a small number of qubits shows that a significant fraction of PQC satisfy this condition, allowing for their efficient sampling.