Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1709.07119 · Quantum Information and Computation

A practical quantum algorithm for the Schur transform

William M. Kirby, Frederick W. Strauch

Published Aug 1, 2018• 16 citations
arXivHTMLPDF

Abstract

We describe an efficient quantum algorithm for the quantum Schur transform. The Schur transform is an operation on a quantum computer that maps the standard computational basis to a basis composed of irreducible representations of the unitary and symmetric groups. We simplify and extend the algorithm of Bacon, Chuang, and Harrow, and provide a new practical construction as well as sharp theoretical and practical analyses. Our algorithm decomposes the Schur transform on n qubits into O(n^4\log(\frac{n}{\eps})) operators in the Clifford+T fault-tolerant gate set and uses exactly 2\lfloor\log_2(n)\rfloor-1 ancillary qubits. We extend our qubit algorithm to decompose the Schur transform on n qudits of dimension d into O(d^{1+p}n^{3d}\log^p(\frac{d n}{\eps})) primitive operators from any universal gate set, for p~3.97.

DOI
10.26421/qic18.9-10-1

Related papers

Generalised Coupling and An Elementary Algorithm for the Quantum Schur Transform

Adam Wills, Sergii Strelchuk

The quantum Schur transform is a fundamental building block that maps the computational basis to a coupled basis consisting of irreducible representations of the unitary and symmetric groups. Equivalently, it may be regarded as a change of basis from the computational basis to a simultaneous spin eigenbasis of Permutational Quantum Computing (PQC) [Quantum Inf. Comput., 10, 470-497 (2010)]. By adopting the latter perspective, we present a transparent algorithm for implementing the qubit quantum Schur transform which uses $O(\log(n))$ ancillas and can be decomposed into a sequence of $O(n^3\log(n)\log(\frac{n}ε))$ Clifford + T gates, where $ε$ is the accuracy of the algorithm in terms of the trace norm. We discuss the necessity for some applications of implementing this operation as a unitary rather than an isometry, as is often presented. By studying the associated Schur states, which consist of qubits coupled via Clebsch-Gordan coefficients, we introduce the notion of generally coupled quantum states. We present six conditions, which in different combinations ensure the efficient preparation of these states on a quantum computer or their classical simulability (in the sense of computational tractability). It is shown that Wigner 6-j symbols and SU(N) Clebsch-Gordan coefficients naturally fit our framework. Finally, we investigate unitary transformations which preserve the class of computationally tractable states.

arXiv:2305.04069•May 6, 2023•0 citations

An efficient high dimensional quantum Schur transform

Hari Krovi

The Schur transform is a unitary operator that block diagonalizes the action of the symmetric and unitary groups on an n fold tensor product V ⊗ n of a vector space V of dimension d . Bacon, Chuang and Harrow [5] gave a quantum algorithm for this transform that is polynomial in n , d and log ⁡ ϵ − 1 , where ϵ is the precision. In a footnote in Harrow's thesis [18], a brief description of how to make the algorithm of [5] polynomial in log ⁡ d is given using the unitary group representation theory (however, this has not been explained in detail anywhere). In this article, we present a quantum algorithm for the Schur transform that is polynomial in n , log ⁡ d and log ⁡ ϵ − 1 using a different approach. Specifically, we build this transform using the representation theory of the symmetric group and in this sense our technique can be considered a ''dual" algorithm to [5]. A novel feature of our algorithm is that we construct the quantum Fourier transform over the so called permutation modules , which could have other applications.

arXiv:1804.00055•Quantum•Feb 14, 2019•42 citations

The quantum Schur and Clebsch-Gordan transforms: I. efficient qudit circuits

Dave Bacon, Isaac L. Chuang, Aram W. Harrow

We present an efficient family of quantum circuits for a fundamental primitive in quantum information theory, the Schur transform. The Schur transform on n d-dimensional quantum systems is a transform between a standard computational basis to a labelling related to the representation theory of the symmetric and unitary groups. If we desire to implement the Schur transform to an accuracy of e-1, then our circuit construction uses a number of gates which is polynomial in n, d and log(e-1). The key tool in our construction is a poly(d, log n, log(e-1)) algorithm for the ud Clebsch-Gordan transform. Our efficient circuit construction renders numerous protocols in quantum information theory computationally tractable and yields a new possible approach to quantum algorithms which is distinct from the standard paradigm of the quantum Fourier transform.

Symposium on Discrete Algorithms•Jan 7, 2007•19 citations

Weak Schur sampling with logarithmic quantum memory

Enrique Cervero-Martí­n, Laura Mančinska

The quantum Schur transform maps the computational basis of a system of $n$ qudits onto a \textit{Schur basis}, which spans the minimal invariant subspaces of the representations of the unitary and the symmetric groups acting on the state space of $n$ $d$-level systems. We introduce a new algorithm for the task of weak Schur sampling. Our algorithm efficiently determines both the Young label which indexes the irreducible representations and the multiplicity label of the symmetric group. There are two major advantages of our algorithm for weak Schur sampling when compared to existing approaches which proceed via quantum Schur transform algorithm or Generalized Phase Estimation algorithm. First, our algorihtm is suitable for streaming applications and second it is exponentially more efficient in its memory usage. We show that an instance of our weak Schur sampling algorithm on $n$ qubits to accuracy $ε$ requires only $O(\log_2n)$ qubits of memory and $O(n^3\log_2(\frac{n}ε))$ gates from the Clifford+T set. Further, we show that our weak Schur sampling algorithm on $n$ qudits decomposes into $O\big(dn^{2d}\log_2^p\big(\frac{n^{2d}}ε\big)\big)$ gates from an arbitrary fault-tolerant qudit universal set, for $p\approx 4$, and requires a memory of $O(\log_dn)$ qudits to implement.

arXiv:2309.11947•Sep 21, 2023•0 citations

The Quantum Schur Transform: I. Efficient Qudit Circuits

Dave Bacon, Isaac L. Chuang, Aram W. Harrow

We present an efficient family of quantum circuits for a fundamental primitive in quantum information theory, the Schur transform. The Schur transform on n d-dimensional quantum systems is a transform between a standard computational basis to a labelling related to the representation theory of the symmetric and unitary groups. If we desire to implement the Schur transform to an accuracy of epsilon, then our circuit construction uses a number of gates which is polynomial in n, d and log(1/epsilon). The important insights we use to perform this construction are the selection of the appropriate subgroup adapted basis and the Wigner-Eckart theorem. Our efficient circuit construction renders numerous protocols in quantum information theory computationally tractable and is an important new efficient quantum circuit family which goes significantly beyond the standard paradigm of the quantum Fourier transform.

arXiv:quant-ph/0601001•Dec 30, 2005•23 citations

Efficient Quantum Fourier Transforms For Semisimple Algebras

Ben Foxman, Barak Nehoran, Yongshan Ding

The quantum Fourier transform (QFT) is a fundamental primitive in quantum computation and quantum information. In this work, we extend the framework for the QFT from finite groups to finite-dimensional semisimple algebras, and give efficient QFTs for the partition algebra $P_n(d)$, Brauer algebra $B_n(d)$, and walled Brauer algebra $B_{r,s}(d)$. These algebras play important roles in generalized Schur-Weyl duality, statistical physics and many-body systems, and have recently found several applications in quantum algorithms. Unlike the group case, the Fourier transform over a semisimple algebra can be non-unitary. Nevertheless, we show that when the parameter $d$ is sufficiently large, the Fourier transform is well approximated by a unitary operator. Furthermore, we show that for each of the algebras $A$ from above, such an approximate Fourier transform can be implemented efficiently: we give a quantum algorithm with gate complexity $\mathrm{poly}(n,\log d,\log(1/\varepsilon))$ for approximating the Fourier transform to error $(d^{-1/2} + \varepsilon) \cdot \mathrm{poly}(|A|)$. Along the way, we establish several properties of the Fourier basis of semisimple algebras that may be of independent interest.

quant-pharXiv:2605.05337•May 8, 2026•0 citations
We describe an efficient quantum algorithm for the quantum Schur transform. The Schur transform is an operation on a quantum computer that maps the standard computational basis to a basis composed of irreducible representations of the unitary and symmetric groups. We simplify and extend the algorithm of Bacon, Chuang, and Harrow, and provide a new practical construction as well as sharp theoretical and practical analyses. Our algorithm decomposes the Schur transform on n qubits into O(n^4\log(\frac{n}{\eps})) operators in the Clifford+T fault-tolerant gate set and uses exactly 2\lfloor\log_2(n)\rfloor-1 ancillary qubits. We extend our qubit algorithm to decompose the Schur transform on n qudits of dimension d into O(d^{1+p}n^{3d}\log^p(\frac{d n}{\eps})) primitive operators from any universal gate set, for p~3.97.
The quantum Schur transform is a fundamental building block that maps the computational basis to a coupled basis consisting of irreducible representations of the unitary and symmetric groups. Equivalently, it may be regarded as a change of basis from the computational basis to a simultaneous spin eigenbasis of Permutational Quantum Computing (PQC) [Quantum Inf. Comput., 10, 470-497 (2010)]. By adopting the latter perspective, we present a transparent algorithm for implementing the qubit quantum Schur transform which uses O(log⁡(n))O(\log(n))O(log(n)) ancillas and can be decomposed into a sequence of O(n3log⁡(n)log⁡(nε))O(n^3\log(n)\log(\frac{n}ε))O(n3log(n)log(εn​)) Clifford + T gates, where εεε is the accuracy of the algorithm in terms of the trace norm. We discuss the necessity for some applications of implementing this operation as a unitary rather than an isometry, as is often presented. By studying the associated Schur states, which consist of qubits coupled via Clebsch-Gordan coefficients, we introduce the notion of generally coupled quantum states. We present six conditions, which in different combinations ensure the efficient preparation of these states on a quantum computer or their classical simulability (in the sense of computational tractability). It is shown that Wigner 6-j symbols and SU(N) Clebsch-Gordan coefficients naturally fit our framework. Finally, we investigate unitary transformations which preserve the class of computationally tractable states.
The Schur transform is a unitary operator that block diagonalizes the action of the symmetric and unitary groups on an n fold tensor product V ⊗ n of a vector space V of dimension d . Bacon, Chuang and Harrow [5] gave a quantum algorithm for this transform that is polynomial in n , d and log ⁡ ϵ − 1 , where ϵ is the precision. In a footnote in Harrow's thesis [18], a brief description of how to make the algorithm of [5] polynomial in log ⁡ d is given using the unitary group representation theory (however, this has not been explained in detail anywhere). In this article, we present a quantum algorithm for the Schur transform that is polynomial in n , log ⁡ d and log ⁡ ϵ − 1 using a different approach. Specifically, we build this transform using the representation theory of the symmetric group and in this sense our technique can be considered a ''dual" algorithm to [5]. A novel feature of our algorithm is that we construct the quantum Fourier transform over the so called permutation modules , which could have other applications.
We present an efficient family of quantum circuits for a fundamental primitive in quantum information theory, the Schur transform. The Schur transform on n d-dimensional quantum systems is a transform between a standard computational basis to a labelling related to the representation theory of the symmetric and unitary groups. If we desire to implement the Schur transform to an accuracy of e-1, then our circuit construction uses a number of gates which is polynomial in n, d and log(e-1). The key tool in our construction is a poly(d, log n, log(e-1)) algorithm for the ud Clebsch-Gordan transform. Our efficient circuit construction renders numerous protocols in quantum information theory computationally tractable and yields a new possible approach to quantum algorithms which is distinct from the standard paradigm of the quantum Fourier transform.
The quantum Schur transform maps the computational basis of a system of nnn qudits onto a \textit{Schur basis}, which spans the minimal invariant subspaces of the representations of the unitary and the symmetric groups acting on the state space of nnn ddd-level systems. We introduce a new algorithm for the task of weak Schur sampling. Our algorithm efficiently determines both the Young label which indexes the irreducible representations and the multiplicity label of the symmetric group. There are two major advantages of our algorithm for weak Schur sampling when compared to existing approaches which proceed via quantum Schur transform algorithm or Generalized Phase Estimation algorithm. First, our algorihtm is suitable for streaming applications and second it is exponentially more efficient in its memory usage. We show that an instance of our weak Schur sampling algorithm on nnn qubits to accuracy εεε requires only O(log⁡2n)O(\log_2n)O(log2​n) qubits of memory and O(n3log⁡2(nε))O(n^3\log_2(\frac{n}ε))O(n3log2​(εn​)) gates from the Clifford+T set. Further, we show that our weak Schur sampling algorithm on nnn qudits decomposes into O(dn2dlog⁡2p(n2dε))O\big(dn^{2d}\log_2^p\big(\frac{n^{2d}}ε\big)\big)O(dn2dlog2p​(εn2d​)) gates from an arbitrary fault-tolerant qudit universal set, for p≈4p\approx 4p≈4, and requires a memory of O(log⁡dn)O(\log_dn)O(logd​n) qudits to implement.
We present an efficient family of quantum circuits for a fundamental primitive in quantum information theory, the Schur transform. The Schur transform on n d-dimensional quantum systems is a transform between a standard computational basis to a labelling related to the representation theory of the symmetric and unitary groups. If we desire to implement the Schur transform to an accuracy of epsilon, then our circuit construction uses a number of gates which is polynomial in n, d and log(1/epsilon). The important insights we use to perform this construction are the selection of the appropriate subgroup adapted basis and the Wigner-Eckart theorem. Our efficient circuit construction renders numerous protocols in quantum information theory computationally tractable and is an important new efficient quantum circuit family which goes significantly beyond the standard paradigm of the quantum Fourier transform.
The quantum Fourier transform (QFT) is a fundamental primitive in quantum computation and quantum information. In this work, we extend the framework for the QFT from finite groups to finite-dimensional semisimple algebras, and give efficient QFTs for the partition algebra Pn(d)P_n(d)Pn​(d), Brauer algebra Bn(d)B_n(d)Bn​(d), and walled Brauer algebra Br,s(d)B_{r,s}(d)Br,s​(d). These algebras play important roles in generalized Schur-Weyl duality, statistical physics and many-body systems, and have recently found several applications in quantum algorithms. Unlike the group case, the Fourier transform over a semisimple algebra can be non-unitary. Nevertheless, we show that when the parameter ddd is sufficiently large, the Fourier transform is well approximated by a unitary operator. Furthermore, we show that for each of the algebras AAA from above, such an approximate Fourier transform can be implemented efficiently: we give a quantum algorithm with gate complexity poly(n,log⁡d,log⁡(1/ε))\mathrm{poly}(n,\log d,\log(1/\varepsilon))poly(n,logd,log(1/ε)) for approximating the Fourier transform to error (d−1/2+ε)⋅poly(∣A∣)(d^{-1/2} + \varepsilon) \cdot \mathrm{poly}(|A|)(d−1/2+ε)⋅poly(∣A∣). Along the way, we establish several properties of the Fourier basis of semisimple algebras that may be of independent interest.