Contributed Talks 2c

Abstract: The quantum Schur transform has become a foundational quantum algorithm, yet even after two decades since the seminal 2004 paper by Bacon, Chuang, and Harrow (BCH), some aspects of the transform remain insufficiently understood. Moreover, an alternative approach proposed by Krovi in 2018 was recently found to be incomplete. In this submission, we present a corrected version of Krovi's algorithm along with a detailed treatment of the high-dimensional version of the BCH Schur transform. This high-dimensional focus makes the two versions of the transform practical for regimes where the local dimension $d$ is much larger than the number of qudits $n$, with corrected Krovi's algorithm scaling as $\widetilde{O}(n^{7/2})$ in gate and depth complexity, and BCH as $\widetilde{O}(\min(n^5,nd^4))$. Krovi's version of Schur transform crucially relies on the quantum Fourier transform for the symmetric group. To that end, we revisit a quantum Fourier transform algorithm by Kawano and Sekigawa. After a careful analysis, we correct their count of elementary one- and two-qubit gates and circuit depth up from $\tilde{\mathcal{O}}(n^3)$ to $\tilde{\mathcal{O}}(n^{7/2})$. This stems from our observation that Kawano and Sekigawa's analysis treats certain complicated multi-qubit operations as elementary. We also correct a mistake in how they label the basis vectors of a certain Hilbert space, simplify their algorithm by removing an unnecessary gate, and expand significantly on the implementation details of the algorithm. Our work addresses key gaps in the literature, strengthening the algorithmic foundations of a wide range of results that rely on Schur--Weyl duality and Quantum Fourier Transform over the symmetric group in quantum information theory and quantum computation.