Classical algorithm for quantum SU(2) Schur sampling

Abstract

Many quantum algorithms can be represented in a form of a classical circuit positioned between quantum Fourier transformations. Motivated by the search for new quantum algorithms, we turn to circuits where the latter transformation is replaced by the SU(2) quantum Schur transform - a global transformation which maps the computational basis to a basis defined by angular momenta. We show that the output distributions of these circuits can be approximately classically sampled in polynomial time if they are sufficiently close to being sparse, thus isolating a regime in which they could lead to algorithms with exponential computational advantages. Our paper is primarily motivated by a conjecture that underpinned the hardness of permutational quantum computing, a restricted quantum computational model that has the above circuit structure in one of its computationally interesting regimes. The conjecture stated that approximating transition amplitudes of permutational quantum computing model to inverse-polynomial precision on a classical computer is computationally hard in this case. We disprove the extended version of this conjecture - even in the case when the hardness of approximation originated from a difficulty of finding the large elements in the output probability distributions. Finally, we present some evidence that output of the above permutational quantum computing circuits could be efficiently approximately sampled from on a classical computer.