Algorithms

Abstract: Many quantum information tasks use inputs of the form $\rho^{\otimes m}$, which naturally induce permutation and unitary symmetries. We classify all channels that respect both symmetries—unitary-equivariant and permutation-invariant maps from $(\mathbb{C}^{d})^{\otimes m}$ to $(\mathbb{C}^{d})^{\otimes n}$— via their extremal points. Operationally, each extremal channel factors as \emph{unitary Schur sampling} $\rightarrow$ an \emph{irrep-level unitary-equivariant channel} $\rightarrow$ the \emph{adjoint unitary Schur sampling}. We give a streaming implementation ansatz that uses an efficient streaming implementation of unitary Schur sampling together with a resource-state primitive, and we apply it to state symmetrization, symmetric cloning, and purity amplification. In these applications we obtain polynomial-time algorithms with exponential memory improvements in $m,n$. Further, for symmetric cloning we present, to our knowledge, the first efficient (polynomial-time) algorithm with explicit memory and gate bounds.

Abstract: The quantum Schur transform has become a foundational quantum algorithm, yet even after two decades since the seminal 2004 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 be incomplete. In this submission, we present a corrected version of Krovi's algorithm along with a detailed treatment of the high-dimensional version of the BCH Schur transform. This high-dimensional focus makes the two versions of the transform practical for regimes where the local dimension $d$ is much larger than the number of qudits $n$, with corrected Krovi's algorithm scaling as $\widetilde{O}(n^{7/2})$ in gate and depth complexity, and BCH as $\widetilde{O}(\min(n^5,nd^4))$. Krovi's version of Schur transform crucially relies on the quantum Fourier transform for the symmetric group. To that end, we revisit a quantum Fourier transform algorithm by Kawano and Sekigawa. After a careful analysis, we correct their count of elementary one- and two-qubit gates and circuit depth up from $\tilde{\mathcal{O}}(n^3)$ to $\tilde{\mathcal{O}}(n^{7/2})$. This stems from our observation that Kawano and Sekigawa's analysis treats certain complicated multi-qubit operations as elementary. We also correct a mistake in how they label the basis vectors of a certain Hilbert space, simplify their algorithm by removing an unnecessary gate, and expand significantly on the implementation details of the algorithm. Our work addresses key gaps in the literature, strengthening the algorithmic foundations of a wide range of results that rely on Schur--Weyl duality and Quantum Fourier Transform over the symmetric group in quantum information theory and quantum computation.

Abstract: We present efficient quantum circuits that implement high-dimensional unitary irreducible representations (irreps) of SU(n), where n>=2 is constant. For dimension N and error eps, the number of quantum gates in our circuits is polynomial in log(N) and log(1/eps). Our construction relies on the Jordan-Schwinger representation, which allows us to realize irreps of SU(n) in the Hilbert space of n quantum harmonic oscillators. Together with a recent efficient quantum Hermite transform, which allows us to map the computational basis states to the eigenstates of the quantum harmonic oscillator, this allows us to implement these irreps efficiently. Our quantum circuits can be used to construct explicit Ramanujan quantum expanders, a longstanding open problem. They can also be used to fast-forward the evolution of certain quantum systems.