arXiv:2610.06737
Anti-symmetrization is cheap and useful
Adam Bene Watts, John Bostanci, Matthias C. Caro, Daniel Grier, Sihan Liu, Gaurav Mahajan
Abstract
We consider the computational task of anti-symmetrization of an unknown mixed quantum state: Given iid copies of a rank-$r$ qudit state $ρ=\sum_{i=1}^r λ_i |\varphi_i\rangle\!\langle\varphi_i|$, prepare a copy of the state proportional to $Π_{\mathrm{anti}}^r (|\varphi_1\rangle\otimes \ldots\otimes|\varphi_r\rangle)$, with $Π_{\mathrm{anti}}^r$ the anti-symmetric subspace projector. We first give a simple algorithm for anti-symmetrization that uses $\widetilde{O}(r / λ_{\min})$ copies of $ρ$, where $λ_{\min}$ is the minimum non-zero eigenvalue of $ρ$. 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 / λ_{\min})$ copies of $ρ$, 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.
AI Summary
The paper studies how to convert copies of an unknown rank-$r$ qudit state $\rho$ into the unique pure antisymmetric state on its support. This output preserves support information but discards the nonzero eigenvalues; it is not a purification of $\rho$. The basic operation attempts to extend an antisymmetric state from $k$ to $k+1$ registers. Crucially, rejection preserves antisymmetry on the original $k$ registers. A streaming algorithm discards rejected registers and succeeds with probability $0.99$ using $O(r\log r/\lambda_{\min})$ copies and $O(r\log d)$ qubits of memory, where $\lambda_{\min}$ is the smallest nonzero eigenvalue. Its analysis uses coupon-collector bounds. A second algorithm retains and retests rejected registers, reducing the copy requirement to $O(r/\lambda_{\min})$. Its analysis uses Schur–Weyl duality and Pieri’s rule to show that it extracts a largest allowed antisymmetric subsystem. Repeated extraction gives weak and unitary Schur sampling and implements the previously optimal qudit purity-amplification channel, with $\widetilde O(n^2d\log(1/\delta))$ controlled-SWAP operations and $\widetilde O(n^2d\log^2(1/\delta))$ $T$ gates. Streaming antisymmetrization also yields a reduction from mixed-state one-way state generators with inverse-polynomial minimum nonzero eigenvalue to pure-state generators. The Schur-sampling improvements apply only in some parameter regimes; purity amplification has worse dimension dependence than prior methods and is not streaming. Optimal antisymmetrization sample complexity and memory–sample tradeoffs remain open, as does removing the cryptographic spectral-gap assumption. The paper notes closely related concurrent work sharing the growth routine and Schur-sampling connection.
Our proofs were completed before~[ref] appeared on the arXiv, but (as we acknowledge below) they were developed with the help of AI
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 35 pages