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

Anti-symmetrization is cheap and useful

Adam Bene Watts, John Bostanci, Matthias C. Caro, Daniel Grier, Sihan Liu, Gaurav Mahajan

quant-phSubmitted Oct 5, 2026• Announced Oct 6, 2026• 1 citation
arXivHTMLPDF

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.

No sign of AI-generated textAI use disclosedUnclear novelty
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

Related papers

Unitary Schur Sampling of Qudits via Random SWAP Tests: Hunt for Antisymmetry

Shrigyan Brahmachari, David Jakab, Henry D. Pfister +1 more

Schur sampling is a fundamental primitive for extracting permutation-invariant information from many-body quantum systems and has broad applications in quantum information science. Circuit-based implementations typically rely on coherent representation-theoretic operations such as Clebsch-Gordan transforms, generalized phase estimation, or quantum Fourier transforms over the symmetric group. We show that unitary Schur sampling of arbitrary permutation-invariant mixed states on $n$ $d$-dimensional qudits can instead be implemented using only pairwise SWAP tests, namely, two-qudit projective measurements onto the symmetric and antisymmetric subspaces. Our protocol achieves error $ε$ in diamond distance using $O(n\min\{n,d\}^{3}\log^2(n/ε))$ random SWAP tests. The central idea is to repeatedly identify and extract the largest antisymmetric subsystem. This turns unitary Schur sampling into a search for antisymmetry and gives the algorithm a natural interpretation as a stochastic traversal of a Young diagram. The protocol preserves the $\mathrm{SU}(d)$-irrep state while preparing a canonical pure state in the multiplicity subsystem. As an application, we consider quantum purity amplification (QPA), in which multiple noisy copies of a pure quantum state are combined to produce a state of higher purity. We show that the optimal purified state can be obtained by retaining a single designated output qudit and discarding the rest.

quant-pharXiv:2610.02103•Oct 2, 2026•2 citations

A memory and gate efficient algorithm for unitary mixed Schur sampling

Enrique Cervero-Martín, Laura Mančinska, Elias Theil

We formalize the task of unitary Schur sampling -- an extension of weak Schur sampling -- which is the process of measuring the Young label and the unitary group register of an input $m$ qudit state. Intuitively, this task is equivalent to applying the Schur transform, projecting onto the isotypic subspaces of the unitary and symmetric groups indexed by the Young labels, and discarding of the permutation register. As such unitary Schur sampling is the natural task in processes such as quantum state tomography or spectrum estimation. We generalize this task to unitary mixed Schur sampling to account for the recently introduced mixed Schur-Weyl transform. We provide a streaming algorithm which achieves an exponential reduction in the memory complexity and a polynomial reduction in the gate complexity over naïve algorithms for the task of unitary (mixed) Schur sampling. Further, we show that if the input state has limited rank, the gate and memory complexities of our streaming algorithm as well as the algorithms for the full Schur and mixed Schur transforms are further reduced. Our work generalizes and improves on the results in arXiv2309.11947.

arXiv:2410.15793•Oct 21, 2024•9 citations

Optimal cloning of mixed states

Marco Fanizza, Dmitry Grinko, Thilo Scharnhorst +1 more

We consider the problem of approximate cloning of quantum states: given $n$ copies of an unknown state $ρ\in \mathbb{C}^{d \times d}$, prepare an $(n+k)$-copy state with high fidelity to $ρ^{\otimes (n+k)}$. Werner's pure state cloner is the optimal channel for the pure state case, and shows that $n = Θ(kd/\varepsilon)$ copies are necessary and sufficient to clone $k$ additional copies of an unknown pure state to fidelity $1-\varepsilon$. The random purification channel gives a straightforward extension of Werner's cloner to mixed state inputs: given $n$ copies of a mixed state, randomly purify your input, apply Werner's channel in the larger Hilbert space, and then trace out the auxiliary registers. This gives a mixed state cloner using $n = O(krd/\varepsilon)$ copies to clone rank-$r$ states. Can one do any better? We show that the answer is no: one must use $n = Ω(krd/\varepsilon)$ copies. We prove our lower bound by studying the special case of projector cloning, in which the input state $ρ$ is promised to be of the form $P/r$, where $P$ is a rank-$r$ orthogonal projector. As a further application of our techniques, we consider the closely related problem of approximate transposition of quantum states, where one seeks to convert $ρ^{\otimes n}$ to a $k$-copy state with high fidelity to $(ρ^T)^{\otimes k}$. Here, we again show $n = Θ(krd/\varepsilon)$ copies are necessary and sufficient for this task.

quant-pharXiv:2608.27298•Aug 28, 2026•5 citations

Classification and implementation of unitary-equivariant and permutation-invariant quantum channels

Laura Mančinska, Elias Theil

Many quantum information tasks use inputs of the form $ρ^{\otimes m}$, which naturally induce permutation and unitary symmetries. We classify all quantum channels that respect both symmetries - i.e. unitary-equivariant and permutation-invariant quantum channels from $(\mathbb{C}^{d})^{\otimes m}$ to $(\mathbb{C}^{d})^{\otimes n}$ - via their extremal points. Operationally, each extremal quantum channel factors as unitary Schur sampling $\rightarrow$ an irrep-level unitary-equivariant quantum channel $\rightarrow$ the 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.

arXiv:2510.08154•Oct 9, 2025•6 citations

Streaming quantum state purification

Andrew M. Childs, Honghao Fu, Debbie Leung +3 more

Quantum state purification is the task of recovering a nearly pure copy of an unknown pure quantum state using multiple noisy copies of the state. This basic task has applications to quantum communication over noisy channels and quantum computation with imperfect devices, but has only been studied previously for the case of qubits. We derive an efficient purification procedure based on the swap test for qudits of any dimension, starting with any initial error parameter. Treating the initial error parameter and the dimension as constants, we show that our procedure has sample complexity asymptotically optimal in the final error parameter. Our protocol has a simple recursive structure that can be applied when the states are provided one at a time in a streaming fashion, requiring only a small quantum memory to implement.

arXiv:2309.16387•Quantum•Jan 21, 2025•28 citations

Nonasymptotic bounds for quantum purity amplification

Thilo Scharnhorst, Jack Spilecki, John Wright

In quantum purity amplification, one is given $n$ copies of a noisy quantum state $ρ\in \mathbb{C}^{d \times d}$ and asked to prepare $k$ copies of its principal eigenstate $|v_d\rangle$. Several prior works have derived information-theoretically optimal algorithms for this problem, but the bounds they prove are only shown in the asymptotic regime as the number of samples $n$ tends to infinity. In this paper, we establish the following nonasymptotic guarantee: if $ρ$'s eigenvalues are sorted $p_1 \leq \cdots \leq p_d$ and $p_{d-1} < p_d$, then \begin{equation*} n = O\Big(k + \frac{k}δ \cdot \frac{1-p_d}{(p_d-p_{d-1})^2}\Big) \end{equation*} copies suffice to output a state with fidelity at least $1-δ$ with $|v_d^{\otimes k}\rangle$. Our bound holds for arbitrary spectra, and is independent of the dimension $d$. In the case of depolarizing noise, our finite-sample guarantee matches the optimal asymptotic scaling. Our proof is based on the combinatorics of random Young diagrams.

quant-pharXiv:2605.27262•May 27, 2026•2 citations
We consider the computational task of anti-symmetrization of an unknown mixed quantum state: Given iid copies of a rank-rrr qudit state ρ=∑i=1rλi∣φi⟩ ⁣⟨φi∣ρ=\sum_{i=1}^r λ_i |\varphi_i\rangle\!\langle\varphi_i|ρ=∑i=1r​λi​∣φi​⟩⟨φi​∣, prepare a copy of the state proportional to Πantir(∣φ1⟩⊗…⊗∣φr⟩)Π_{\mathrm{anti}}^r (|\varphi_1\rangle\otimes \ldots\otimes|\varphi_r\rangle)Πantir​(∣φ1​⟩⊗…⊗∣φr​⟩), with ΠantirΠ_{\mathrm{anti}}^rΠantir​ the anti-symmetric subspace projector. We first give a simple algorithm for anti-symmetrization that uses O~(r/λmin⁡)\widetilde{O}(r / λ_{\min})O(r/λmin​) copies of ρρρ, where λmin⁡λ_{\min}λ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⁡)O(r / λ_{\min})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 nnn and local dimension ddd, as well as in an algorithm for optimal purity amplification for qudit states.
The paper studies how to convert copies of an unknown rank-rrr 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 kkk to k+1k+1k+1 registers. Crucially, rejection preserves antisymmetry on the original kkk registers. A streaming algorithm discards rejected registers and succeeds with probability 0.990.990.99 using O(rlog⁡r/λmin⁡)O(r\log r/\lambda_{\min})O(rlogr/λmin​) copies and O(rlog⁡d)O(r\log d)O(rlogd) qubits of memory, where λmin⁡\lambda_{\min}λ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/λmin⁡)O(r/\lambda_{\min})O(r/λ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 O~(n2dlog⁡(1/δ))\widetilde O(n^2d\log(1/\delta))O(n2dlog(1/δ)) controlled-SWAP operations and O~(n2dlog⁡2(1/δ))\widetilde O(n^2d\log^2(1/\delta))O(n2dlog2(1/δ)) TTT 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.
Schur sampling is a fundamental primitive for extracting permutation-invariant information from many-body quantum systems and has broad applications in quantum information science. Circuit-based implementations typically rely on coherent representation-theoretic operations such as Clebsch-Gordan transforms, generalized phase estimation, or quantum Fourier transforms over the symmetric group. We show that unitary Schur sampling of arbitrary permutation-invariant mixed states on nnn ddd-dimensional qudits can instead be implemented using only pairwise SWAP tests, namely, two-qudit projective measurements onto the symmetric and antisymmetric subspaces. Our protocol achieves error εεε in diamond distance using O(nmin⁡{n,d}3log⁡2(n/ε))O(n\min\{n,d\}^{3}\log^2(n/ε))O(nmin{n,d}3log2(n/ε)) random SWAP tests. The central idea is to repeatedly identify and extract the largest antisymmetric subsystem. This turns unitary Schur sampling into a search for antisymmetry and gives the algorithm a natural interpretation as a stochastic traversal of a Young diagram. The protocol preserves the SU(d)\mathrm{SU}(d)SU(d)-irrep state while preparing a canonical pure state in the multiplicity subsystem. As an application, we consider quantum purity amplification (QPA), in which multiple noisy copies of a pure quantum state are combined to produce a state of higher purity. We show that the optimal purified state can be obtained by retaining a single designated output qudit and discarding the rest.
We formalize the task of unitary Schur sampling -- an extension of weak Schur sampling -- which is the process of measuring the Young label and the unitary group register of an input mmm qudit state. Intuitively, this task is equivalent to applying the Schur transform, projecting onto the isotypic subspaces of the unitary and symmetric groups indexed by the Young labels, and discarding of the permutation register. As such unitary Schur sampling is the natural task in processes such as quantum state tomography or spectrum estimation. We generalize this task to unitary mixed Schur sampling to account for the recently introduced mixed Schur-Weyl transform. We provide a streaming algorithm which achieves an exponential reduction in the memory complexity and a polynomial reduction in the gate complexity over naïve algorithms for the task of unitary (mixed) Schur sampling. Further, we show that if the input state has limited rank, the gate and memory complexities of our streaming algorithm as well as the algorithms for the full Schur and mixed Schur transforms are further reduced. Our work generalizes and improves on the results in arXiv2309.11947.
We consider the problem of approximate cloning of quantum states: given nnn copies of an unknown state ρ∈Cd×dρ\in \mathbb{C}^{d \times d}ρ∈Cd×d, prepare an (n+k)(n+k)(n+k)-copy state with high fidelity to ρ⊗(n+k)ρ^{\otimes (n+k)}ρ⊗(n+k). Werner's pure state cloner is the optimal channel for the pure state case, and shows that n=Θ(kd/ε)n = Θ(kd/\varepsilon)n=Θ(kd/ε) copies are necessary and sufficient to clone kkk additional copies of an unknown pure state to fidelity 1−ε1-\varepsilon1−ε. The random purification channel gives a straightforward extension of Werner's cloner to mixed state inputs: given nnn copies of a mixed state, randomly purify your input, apply Werner's channel in the larger Hilbert space, and then trace out the auxiliary registers. This gives a mixed state cloner using n=O(krd/ε)n = O(krd/\varepsilon)n=O(krd/ε) copies to clone rank-rrr states. Can one do any better? We show that the answer is no: one must use n=Ω(krd/ε)n = Ω(krd/\varepsilon)n=Ω(krd/ε) copies. We prove our lower bound by studying the special case of projector cloning, in which the input state ρρρ is promised to be of the form P/rP/rP/r, where PPP is a rank-rrr orthogonal projector. As a further application of our techniques, we consider the closely related problem of approximate transposition of quantum states, where one seeks to convert ρ⊗nρ^{\otimes n}ρ⊗n to a kkk-copy state with high fidelity to (ρT)⊗k(ρ^T)^{\otimes k}(ρT)⊗k. Here, we again show n=Θ(krd/ε)n = Θ(krd/\varepsilon)n=Θ(krd/ε) copies are necessary and sufficient for this task.
Many quantum information tasks use inputs of the form ρ⊗mρ^{\otimes m}ρ⊗m, which naturally induce permutation and unitary symmetries. We classify all quantum channels that respect both symmetries - i.e. unitary-equivariant and permutation-invariant quantum channels from (Cd)⊗m(\mathbb{C}^{d})^{\otimes m}(Cd)⊗m to (Cd)⊗n(\mathbb{C}^{d})^{\otimes n}(Cd)⊗n - via their extremal points. Operationally, each extremal quantum channel factors as unitary Schur sampling →\rightarrow→ an irrep-level unitary-equivariant quantum channel →\rightarrow→ the 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,nm,nm,n. Further, for symmetric cloning we present, to our knowledge, the first efficient (polynomial-time) algorithm with explicit memory and gate bounds.
Quantum state purification is the task of recovering a nearly pure copy of an unknown pure quantum state using multiple noisy copies of the state. This basic task has applications to quantum communication over noisy channels and quantum computation with imperfect devices, but has only been studied previously for the case of qubits. We derive an efficient purification procedure based on the swap test for qudits of any dimension, starting with any initial error parameter. Treating the initial error parameter and the dimension as constants, we show that our procedure has sample complexity asymptotically optimal in the final error parameter. Our protocol has a simple recursive structure that can be applied when the states are provided one at a time in a streaming fashion, requiring only a small quantum memory to implement.
In quantum purity amplification, one is given nnn copies of a noisy quantum state ρ∈Cd×dρ\in \mathbb{C}^{d \times d}ρ∈Cd×d and asked to prepare kkk copies of its principal eigenstate ∣vd⟩|v_d\rangle∣vd​⟩. Several prior works have derived information-theoretically optimal algorithms for this problem, but the bounds they prove are only shown in the asymptotic regime as the number of samples nnn tends to infinity. In this paper, we establish the following nonasymptotic guarantee: if ρρρ's eigenvalues are sorted p1≤⋯≤pdp_1 \leq \cdots \leq p_dp1​≤⋯≤pd​ and pd−1<pdp_{d-1} < p_dpd−1​<pd​, then \begin{equation*} n = O\Big(k + \frac{k}δ \cdot \frac{1-p_d}{(p_d-p_{d-1})^2}\Big) \end{equation*} copies suffice to output a state with fidelity at least 1−δ1-δ1−δ with ∣vd⊗k⟩|v_d^{\otimes k}\rangle∣vd⊗k​⟩. Our bound holds for arbitrary spectra, and is independent of the dimension ddd. In the case of depolarizing noise, our finite-sample guarantee matches the optimal asymptotic scaling. Our proof is based on the combinatorics of random Young diagrams.