An efficient high dimensional quantum Schur transform

Abstract

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^{\otimes n}$ of a vector space $V$ of dimension $d$. Bacon, Chuang and Harrow \cite{BCH07} gave a quantum algorithm for this transform that is polynomial in $n$, $d$ and $\log {\epsilon }^{-1}$, where $\epsilon$ is the precision. In a footnote in Harrow's thesis \cite{H05}, a brief description of how to make the algorithm of \cite{BCH07} 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 {\epsilon }^{-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 \cite{BCH07}. A novel feature of our algorithm is that we construct the quantum Fourier transform over the so called \emph{permutation modules}, which could have other applications.

21 pages

References in corpus (7)

• Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms
• The Spectra of Density Operators and the Kronecker Coefficients of the Symmetric Group
• A numerical algorithm for the explicit calculation of SU(N) and SL(N,C) Clebsch-Gordan coefficients
• Decoherence, Control, and Symmetry in Quantum Computers
• Universal super-replication of unitary gates
• Quantum Schur Sampling Circuits can be Strongly Simulated
• Universal and distorsion-free entanglement concentration of multiqubit quantum states in the W class

Cited by in corpus (31)

• Theory for Equivariant Quantum Neural Networks
• Beyond the swap test: optimal estimation of quantum state overlap
• Speeding up Learning Quantum States through Group Equivariant Convolutional Quantum Ansätze
• Unsupervised classification of quantum data
• Optimal Universal Quantum Error Correction via Bounded Reference Frames
• Symmetry breaking/symmetry preserving circuits and symmetry restoration on quantum computers: A quantum many-body perspective
• Reversing Unknown Qubit-Unitary Operation, Deterministically and Exactly
• Filtering states with total spin on a quantum computer
• Ultimate limits for quickest quantum change-point detection
• Non-Unitary Quantum Machine Learning
• Many-body interference in bosonic dynamics
• Designs from Local Random Quantum Circuits with SU(d) Symmetry
• Universal construction of decoders from encoding black boxes
• Toward Super-polynomial Quantum Speedup of Equivariant Quantum Algorithms with SU($d$) Symmetry
• SnCQA: A hardware-efficient equivariant quantum convolutional circuit architecture
• A Classical Algorithm for Quantum $\text{SU}(2)$ Schur Sampling
• Cycle Index Polynomials and Generalized Quantum Separability Tests
• Entanglement theory with limited computational resources
• All you need is spin: SU(2) equivariant variational quantum circuits based on spin networks
• Universal algorithms for quantum data learning
• Learning from physics experiments, with quantum computers: Applications in muon spectroscopy
• Unification of Finite Symmetries in Simulation of Many-body Systems on Quantum Computers
• Universal adjointation of isometry operations using conversion of quantum supermaps
• Time-Efficient Quantum Entropy Estimator via Samplizer
• A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire
• Quantum eigenstate broadcasting assisted by a coherent link
• Measuring quantum relative entropy with finite-size effect
• Representation matching for delegated quantum computing
• Performance Guarantees for Quantum Neural Estimation of Entropies
• Testing identity of collections of quantum states: sample complexity analysis
• Compression of quantum shallow-circuit states