{"id":"arxiv/2608.28569","url":"https://arxiv.org/abs/2608.28569","tags":["quant-ph","math.RT"],"score":0,"title":"Quantum Fourier transform for the symmetric group","domain":"quant-ph","source":"arxiv","authors":["Carli Bruinsma","Dmitry Grinko","Maris Ozols"],"reviews":0,"subject":"quant-ph","summary":"Quantum Fourier transforms (QFT) for general groups were recognized to be fundamental already early in the field. A canonical example of non-abelian QFT for the symmetric group was outlined by Beals (1997). Later, a more detailed analysis of this algorithm was carried out by Kawano and Sekigawa (2016). In this paper, we revisit that construction. After a careful analysis, we revise their gate complexity to $\\widetilde{\\mathcal{O}}(n^{3.5})$ and circuit depth to $\\widetilde{\\mathcal{O}}(n^3)$. Moreover, we observe that their construction is not optimal in the choice of transversal elements,…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-08-28","reactions":{}}