QLunch: Vladyslav Visnevskyi
Speaker: Vladyslav Visnevskyi
Title: High-dimensional quantum Schur transforms
Abstract: The quantum Schur transform has become a foundational quantum algorithm, yet even after two decades since the seminal 2005 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 contain a crucial error.
In this paper, we present a corrected version of Krovi's algorithm along with a detailed treatment of the high-dimensional version of the BCH Schur transform.
Our two main contributions are as follows:
(i) We identify and correct a crucial error in the final step of Krovi's Schur transform algorithm, provide a complete and detailed quantum circuit for the whole algorithm, and show its gate and depth complexity to be $\widetilde{O}(n^{7/2})$.
(ii) We provide details missing from Harrow's thesis on how pre-processing can be used to adapt the BCH Schur transform to the high-dimensional ($d >> n$) regime, and show that this updated BCH algorithm has gate and depth complexity $\widetilde{O}(\min(n^5, nd^4))$, improving upon its original $\widetilde{O}(nd^4)$ scaling.
Taken together, these results significantly advance the current state of the art of high-dimensional Schur transforms, making them practical in regimes where the local dimension $d$ is much larger than the number of qudits $n$. This fills a key gap in the literature and strengthens the algorithmic foundations of a wide range of results in quantum information and quantum algorithms that rely on the Schur--Weyl duality.