Is anti-symmetrization of mixed quantum states computationally cheap?

The task is to build one canonical pure state

The paper studies a specific computational task. The input is many independent and identically distributed copies of an unknown rank-r qudit state ρ, written in its spectral decomposition as ρ = Σ λi |φi⟩⟨φi|. The goal is to prepare a copy of the pure state proportional to Π_anti^r (|φ1⟩ ⊗ … ⊗ |φr⟩), where Π_anti^r is the projector onto the anti-symmetric subspace of (C^d)^{⊗r}. The authors call this output the anti-symmetric state over the support of ρ.

This is a purification-style task, but it differs from the random purification channel the paper contrasts it with. When the number of anti-symmetrized registers reaches the rank r of the mixed state, the procedure deterministically produces a unique pure state — the unique state in the anti-symmetric subspace of r copies of an r-dimensional space. Because that output is unique and identical across all rank-r states sharing the same support, the authors state it lets them circumvent no-go results about universal purification.

The cost is measured in copies of ρ, not in wall-clock time or qubits alone. The relevant eigenvalue scale is λmin, the minimum non-zero eigenvalue of ρ, which sets how rare the informative directions are among the copies.

A growth measurement adds one register at a time

Both algorithms rest on the same primitive. If the first k registers are already in the anti-symmetric subspace, the procedure measures the anti-symmetric subspace projector on the first k+1 registers. If the measurement accepts, the state now lies in the anti-symmetric subspace over k+1 registers. If it rejects, the key observation is that the first k registers still hold an anti-symmetric state, so the (k+1)-st register can simply be discarded and growth can continue with fresh copies.

The paper states that this measurement can be implemented with two controlled-SWAP operations using a ⌈log(k+1)⌉-qubit control register, a single multi-controlled-Z on ⌈log(k+1)⌉ qubits, and two layers of single-qubit gates on ⌈log(k+1)⌉ qubits. The authors also note it can be implemented in constant depth, in the class QNC^0_f, which they suggest may make it more practical for near-term quantum computers.

This is the mechanism behind the paper's cost claims: the algorithm avoids representation-theoretic transforms such as the Schur transform and instead uses simple controlled-SWAP operations, running in quadratic time in the number of copies.

The streaming version spends extra copies to save memory

The first algorithm is described as streaming-like: it only ever acts on one fresh copy of ρ at a time, and it keeps working memory low by discarding registers that fail the growth measurement. It uses at most O(r log d) qubits of working memory, requests a total of n = O(r log r / λmin) copies of ρ, and prepares the unique anti-symmetric state over the support of ρ with success probability 0.99.

The authors state that the analysis of this version reduces straightforwardly to bounding the success probability of a coupon collector. The extra log r factor in the copy count is the price of throwing away failed registers rather than keeping them.

This version is the one used for the cryptographic application, because its one-copy-at-a-time behavior matches the streaming model.

Re-using failed copies removes the log r factor

The second algorithm keeps the copies on which the growth measurement failed in a pool, and sometimes, instead of processing a fresh copy, re-applies the growth measurement to a register from that pool. The paper's stated reason this can help is that operators applied to states in the failure mode across different rounds do not commute, so a state rejected early can later be used to grow the anti-symmetric state after a different state is rejected.

The resulting guarantee is n = O(r/λmin) copies of ρ, again preparing the unique anti-symmetric state over the support of ρ with success probability 0.99. The formal theorem states the algorithm returns that state with probability at least 1 − (ε + exp(−Ω(n λmin))) provided n ≥ C r/λmin for a sufficiently large constant C > 0.

The analysis of this version is more involved and uses tools from the representation theory of the symmetric group, specifically Pieri's rule. The authors highlight a structural difference: the re-use version builds the largest representation-theoretically possible anti-symmetric state from the available n copies regardless of n, whereas the discarding version does so only for sufficiently large n. They state this feature is crucial for applying the re-use algorithm to Schur sampling routines.

Schur sampling improves in some n and d regimes

The paper applies anti-symmetrization with copy re-use to give alternative algorithms for weak and unitary Schur sampling. In weak Schur sampling, the task is to sample a partition λ from a distribution (p_λ) such that Σ_λ |p_λ − Tr[Π_λ ρ]| ≤ δ, where Π_λ projects onto the λ-isotypic component under a Schur transform. Unitary Schur sampling additionally requires outputting a state that approximately recovers the reduced state on the W_λ module.

The stated corollary is that weak and unitary Schur sampling to accuracy δ can be performed with Õ(n² d log(1/δ)) controlled-SWAP operations and T-count Õ(n² d log²(1/δ)). The authors compare this with prior approaches to constant-accuracy weak and unitary Schur sampling for general d, which they say had gate complexities of the form Õ(n^a d^b) with integers a ≥ 1 and b ≥ 0 satisfying a + b ≥ 4. Their procedure achieves a = 2 and b = 1, so a + b = 3, improving the overall complexity in some regimes of n and d.

The improvement is not universal. The paper explicitly notes that for d = 2, a unitary Schur sampling algorithm using Õ(n) random SWAP tests outperforms theirs. The comparison is therefore regime-dependent in both the number of copies n and the local dimension d.

Purity amplification keeps optimality with a simpler route

The paper also develops an anti-symmetrization-based procedure for purity amplification, the task introduced by Li et al. of taking n iid copies of a mixed qudit state ρ and outputting a state ρ′ close to achieving maximum overlap with the top eigenvector of ρ. The authors describe their procedure as a simplification of the optimal quantum purity amplification protocol of Li et al. while producing the same output state.

The stated corollary is optimal purity amplification to accuracy δ with Õ(n² d log(1/δ)) controlled-SWAP operations and T-count Õ(n² d log²(1/δ)). Prior work achieved purity amplification with overall gate complexity polynomial in n and log d using generalized quantum phase estimation. The paper is explicit that its dependence on the local dimension d is worse, but that if d is taken to be fixed, it achieves improved gate complexity with an arguably simpler implementation.

One scope condition matters here: because the purity amplification procedure builds on anti-symmetrization with copy re-use, the authors state it does not apply to the streaming version of the task.

The cryptographic reduction holds only for gapped low rank

The second application is a reduction from gapped mixed-state one-way state generators to pure-state one-way state generators. A one-way state generator is a keyed family of states φ_k such that learning the key k from copies of φ_k is hard, while verifying φ_k given k is computationally easy. For pure φ_k there are natural verification strategies, such as repeated SWAP tests or uncomputing the preparation circuit and measuring in the computational basis; for mixed φ_k these do not immediately determine whether an unknown state equals φ_k.

The paper's reduction uses the streaming anti-symmetrization procedure. If a 1/t-gapped rank-r one-way state generator exists, with each ρ_k having rank r and minimum eigenvalue at least 1/t, then the pure state proportional to Σ_σ sign(σ) P_σ (|ψ_{k,1}⟩ ⊗ … ⊗ |ψ_{k,r}⟩) can be prepared from polynomially many copies of ρ_k in poly(r, t, log d) time, except with negligible failure probability. An algorithm breaking the one-wayness of the resulting pure-state generator would then break the original mixed-state generator.

The reduction is described as almost tight among black-box reductions. The paper states that when r becomes sufficiently super-polynomial, growing faster than λ log λ, there is a quantum state separation between rank-r one-way state generators and efficiently verifiable one-way state generators, which can be lifted to a unitary oracle separation. The authors also note it remains open whether pure-state one-way state generators can be obtained from very high rank mixed-state one-way state generators using their efficient verification algorithm, or whether the two notions might actually be separate.

Memory, copy budget, and rank decide the choice

The paper's own comparison comes down to a trade-off between working memory and copy count. The streaming-like algorithm uses O(r log d) qubits of working memory but requests O(r log r / λmin) copies; the copy-re-use algorithm requests O(r/λmin) copies but needs a larger quantum memory to hold the pool of failed registers. The log r gap is the concrete cost of discarding failures.

The second decision axis is the downstream task. Schur sampling and purity amplification rely on the copy-re-use version, because building the largest representation-theoretically possible anti-symmetric state from the available n copies is what those routines need. The cryptographic reduction relies on the streaming version, because it must act on one fresh copy at a time. The purity amplification result therefore does not carry over to the streaming setting.

The third axis is the regime of n and d. The Schur sampling improvement over prior gate complexities holds in some regimes of n and d, but for d = 2 the Õ(n) random SWAP test approach outperforms it. For purity amplification, the dependence on d is worse than prior work, so the improved gate complexity applies when d is taken to be fixed. The most useful reading of this paper is not that anti-symmetrization is cheap in every setting, but that its cost is governed by r/λmin, its memory by r log d, and its advantage by whether the task needs copy re-use and whether d is small.

Sources used in this answer