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:2310.01613

The mixed Schur transform: efficient quantum circuit and applications

Nguyen, Quynh T.

Published Oct 2, 2023• 0 citations
arXivHTMLPDF

Abstract

The Schur transform, which block-diagonalizes the tensor representation $U^{\otimes n}$ of the unitary group $\mathbf{U}_d$ on $n$ qudits, is an important primitive in quantum information and theoretical physics. We give a generalization of its quantum circuit implementation due to Bacon, Chuang, and Harrow (SODA 2007) to the case of mixed tensor $U^{\otimes n} \otimes \bar{U}^{\otimes m}$, where $\bar{U}$ is the dual representation. This representation is the symmetry of unitary-equivariant channels, which find various applications in quantum majority vote, multiport-based teleportation, asymmetric state cloning, black-box unitary transformations, etc. The "mixed" Schur transform contains several natural extensions of the representation theory used in the Schur transform, in which the main ingredient is a duality between the mixed tensor representations and the walled Brauer algebra. Another element is an efficient implementation of a "dual" Clebsch-Gordan transform for $\bar{U}$. The overall circuit has complexity $\widetilde{O} ((n+m)d^4)$. Finally, we show how the mixed Schur transform enables efficient implementation of unitary-equivariant channels in various settings and discuss other potential applications, including an extension of permutational quantum computing that includes partial transposes.

DOI
10.48550/arxiv.2310.01613

Related papers

Mixed Schur-Weyl duality in quantum information

Dmitry Grinko

This thesis explores the interplay between representation theory and quantum information. Specifically, we focus on mixed Schur–Weyl duality, which considers the action of the unitary group on mixed tensors. This setting naturally arises in quantum information tasks involving unitary-equivariant channels, such as port-based teleportation, quantum majority vote, and universal transposition of unitary operators. A key contribution of this thesis is an explicit derivation of the action of the generators of the partially transposed permutation matrix algebra—the commutant of the mixed unitary action—in the Gelfand–Tsetlin basis. As another key result of this thesis, we develop efficient quantum circuits for the mixed quantum Schur transform, a novel primitive in quantum information. The key ingredient of our construction is new efficient circuits for the dual Clebsch–Gordan transform of the unitary group. A significant application of our findings is the construction of efficient quantum algorithms for port-based teleportation, a variant of quantum teleportation that eliminates the need for corrective operations. Another application is a symmetry reduction of semidefinite optimisation problems with unitary equivariance symmetry. Finally, we study the extendibility of quantum states possessing unitary, mixed unitary, or orthogonal symmetry on the complete graph. We obtain analytically the exact maximum values for projections onto the maximally entangled state and the antisymmetric state for each of the three symmetry classes. This thesis demonstrates the usefulness of mixed Schur–Weyl duality in quantum information and computing. We expect that our tools will help address other problems in other areas of quantum information processing, such as communication, cryptography, and simulation.

•Jan 1, 2025•0 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

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

Gelfand-Tsetlin basis for partially transposed permutations, with applications to quantum information

Dmitry Grinko, Adam Burchardt, Māris Ozols

We study representation theory of the partially transposed permutation matrix algebra, a matrix representation of the diagrammatic walled Brauer algebra. This algebra plays a prominent role in mixed Schur-Weyl duality that appears in various contexts in quantum information. Our main technical result is an explicit formula for the action of the walled Brauer algebra generators in the Gelfand-Tsetlin basis. It generalizes the well-known Gelfand-Tsetlin basis for the symmetric group (also known as Young's orthogonal form or Young-Yamanouchi basis). We provide two applications of our result to quantum information. First, we show how to simplify semidefinite optimization problems over unitary-equivariant quantum channels by performing a symmetry reduction. Second, we derive an efficient quantum circuit for implementing the optimal port-based quantum teleportation protocol, exponentially improving the known trivial construction. As a consequence, this also exponentially improves the known lower bound for the amount of entanglement needed to implement unitaries non-locally. Both applications require a generalization of quantum Schur transform to tensors of mixed unitary symmetry. We develop an efficient quantum circuit for this mixed quantum Schur transform and provide a matrix product state representation of its basis vectors. For constant local dimension, this yields an efficient classical algorithm for computing any entry of the mixed quantum Schur transform unitary.

arXiv:2310.02252•Oct 3, 2023•1 citation

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

A practical quantum algorithm for the Schur transform

William M. Kirby, Frederick W. Strauch

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.

arXiv:1709.07119•Quantum Information and Computation•Aug 1, 2018•16 citations
The Schur transform, which block-diagonalizes the tensor representation U⊗nU^{\otimes n}U⊗n of the unitary group Ud\mathbf{U}_dUd​ on nnn qudits, is an important primitive in quantum information and theoretical physics. We give a generalization of its quantum circuit implementation due to Bacon, Chuang, and Harrow (SODA 2007) to the case of mixed tensor U⊗n⊗Uˉ⊗mU^{\otimes n} \otimes \bar{U}^{\otimes m}U⊗n⊗Uˉ⊗m, where Uˉ\bar{U}Uˉ is the dual representation. This representation is the symmetry of unitary-equivariant channels, which find various applications in quantum majority vote, multiport-based teleportation, asymmetric state cloning, black-box unitary transformations, etc. The "mixed" Schur transform contains several natural extensions of the representation theory used in the Schur transform, in which the main ingredient is a duality between the mixed tensor representations and the walled Brauer algebra. Another element is an efficient implementation of a "dual" Clebsch-Gordan transform for Uˉ\bar{U}Uˉ. The overall circuit has complexity O~((n+m)d4)\widetilde{O} ((n+m)d^4)O((n+m)d4). Finally, we show how the mixed Schur transform enables efficient implementation of unitary-equivariant channels in various settings and discuss other potential applications, including an extension of permutational quantum computing that includes partial transposes.
This thesis explores the interplay between representation theory and quantum information. Specifically, we focus on mixed Schur–Weyl duality, which considers the action of the unitary group on mixed tensors. This setting naturally arises in quantum information tasks involving unitary-equivariant channels, such as port-based teleportation, quantum majority vote, and universal transposition of unitary operators. A key contribution of this thesis is an explicit derivation of the action of the generators of the partially transposed permutation matrix algebra—the commutant of the mixed unitary action—in the Gelfand–Tsetlin basis. As another key result of this thesis, we develop efficient quantum circuits for the mixed quantum Schur transform, a novel primitive in quantum information. The key ingredient of our construction is new efficient circuits for the dual Clebsch–Gordan transform of the unitary group. A significant application of our findings is the construction of efficient quantum algorithms for port-based teleportation, a variant of quantum teleportation that eliminates the need for corrective operations. Another application is a symmetry reduction of semidefinite optimisation problems with unitary equivariance symmetry. Finally, we study the extendibility of quantum states possessing unitary, mixed unitary, or orthogonal symmetry on the complete graph. We obtain analytically the exact maximum values for projections onto the maximally entangled state and the antisymmetric state for each of the three symmetry classes. This thesis demonstrates the usefulness of mixed Schur–Weyl duality in quantum information and computing. We expect that our tools will help address other problems in other areas of quantum information processing, such as communication, cryptography, and simulation.
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 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 study representation theory of the partially transposed permutation matrix algebra, a matrix representation of the diagrammatic walled Brauer algebra. This algebra plays a prominent role in mixed Schur-Weyl duality that appears in various contexts in quantum information. Our main technical result is an explicit formula for the action of the walled Brauer algebra generators in the Gelfand-Tsetlin basis. It generalizes the well-known Gelfand-Tsetlin basis for the symmetric group (also known as Young's orthogonal form or Young-Yamanouchi basis). We provide two applications of our result to quantum information. First, we show how to simplify semidefinite optimization problems over unitary-equivariant quantum channels by performing a symmetry reduction. Second, we derive an efficient quantum circuit for implementing the optimal port-based quantum teleportation protocol, exponentially improving the known trivial construction. As a consequence, this also exponentially improves the known lower bound for the amount of entanglement needed to implement unitaries non-locally. Both applications require a generalization of quantum Schur transform to tensors of mixed unitary symmetry. We develop an efficient quantum circuit for this mixed quantum Schur transform and provide a matrix product state representation of its basis vectors. For constant local dimension, this yields an efficient classical algorithm for computing any entry of the mixed quantum Schur transform unitary.
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.
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.