Anti-symmetrization is cheap and useful

Abstract

We consider the computational task of anti-symmetrization of an unknown mixed quantum state: Given iid copies of a rank-$r$ qudit state $\rho ={\sum }_{i=1}^r{\lambda }_i|{\phi }_i⟩⟨{\phi }_i|$, prepare a copy of the state proportional to ${\Pi }_{\mathrm{anti}}^r(|{\phi }_1⟩\otimes \dots \otimes |{\phi }_r⟩)$, with ${\Pi }_{\mathrm{anti}}^r$ the anti-symmetric subspace projector. We first give a simple algorithm for anti-symmetrization that uses $\tilde{O}(r/{\lambda }_{\min })$ copies of $\rho$, where ${\lambda }_{\min }$ is the minimum non-zero eigenvalue of $\rho$. This algorithm works even in the streaming setting with small working memory, and it uses only simple quantum operations like controlled-SWAPs and constantly many layers of single-qubit gates. As an application of this streaming anti-symmetrization procedure, we give a reduction from gapped mixed-state one-way state generators to pure-state one-way state generators. Then, using tools from Schur-Weyl duality, we give and analyze a second (non-streaming) anti-symmetrization procedure that uses $O(r/{\lambda }_{\min })$ copies of $\rho$, which then serves as a building block in new algorithms for weak Schur sampling and unitary Schur sampling, outperforming existing approaches in some regimes of number of copies $n$ and local dimension $d$, as well as in an algorithm for optimal purity amplification for qudit states.

35 pages