混合量子态的反对称化在计算上便宜吗？

任务目标是构造一个唯一的纯态

论文研究一个具体的计算任务。输入是未知秩 r qudit 态 ρ 的许多独立同分布副本，ρ 写成谱分解 ρ = Σ λi |φi⟩⟨φi|。目标是制备纯态 Π_anti^r (|φ1⟩ ⊗ … ⊗ |φr⟩) 的一份副本，其中 Π_anti^r 是 (C^d)^{⊗r} 反称子空间上的投影算符。作者把这一输出称为 ρ 支撑集上的反对称态。

这是一个纯化类任务，但与论文用来对照的随机纯化信道不同。当被反对称化的寄存器数目达到混合态的秩 r 时，该过程确定性地产生一个唯一纯态——即 r 维空间 r 份副本反称子空间中的唯一态。由于该输出唯一，且对所有具有相同支撑集的秩 r 态都相同，作者指出这使他们能够绕开关于通用纯化的不可能性结果。

成本以 ρ 的副本数衡量，而不是以墙钟时间或单独的量子比特数衡量。相关的特征值尺度是 λmin，即 ρ 的最小非零特征值，它决定了信息性方向在副本中有多稀有。

增长测量每次增加一个寄存器

两种算法都建立在同一个原语上。如果前 k 个寄存器已经处于反称子空间，该过程就在前 k+1 个寄存器上测量反称子空间投影算符。如果测量接受，态现在位于 k+1 个寄存器上的反称子空间。如果测量拒绝，关键观察是前 k 个寄存器仍持有反对称态，因此可以直接丢弃第 (k+1) 个寄存器，并用新副本继续增长。

论文指出，这一测量可以用两次受控 SWAP 实现，使用一个 ⌈log(k+1)⌉ 量子比特的控制寄存器、一个作用于 ⌈log(k+1)⌉ 量子比特的多控 Z，以及两层作用于 ⌈log(k+1)⌉ 量子比特的单量子比特门。作者还指出它可以在常数深度内实现，属于 QNC^0_f 类，他们认为这可能使其对近期量子计算机更实用。

这就是论文成本主张背后的机制：算法避开 Schur 变换这类表示论变换，改用简单的受控 SWAP 操作，运行时间在副本数上为二次。

流式版本用更多副本换取内存

第一个算法被描述为类流式：它一次只处理一份新的 ρ 副本，并通过丢弃增长测量失败的寄存器来保持低工作内存。它最多使用 O(r log d) 量子比特工作内存，总共请求 n = O(r log r / λmin) 份 ρ 副本，并以 0.99 的成功概率制备 ρ 支撑集上唯一的反对称态。

作者指出，这一版本的分析可以直接归结为对优惠券收集器成功概率的界定。副本数中多出的 log r 因子，就是丢弃失败寄存器而不是保留它们的代价。

这一版本被用于密码学应用，因为它一次处理一份副本的行为符合流式模型。

复用失败副本消除 log r 因子

第二个算法把增长测量失败的副本保留在一个池中，有时不处理新副本，而是对池中某个寄存器重新施加增长测量。论文给出的理由是，不同轮次中作用于失败模式态的算符彼此不对易，因此一个早期被拒绝的态，可能在另一个态被拒绝之后被用来增长反对称态。

由此得到的保证是 n = O(r/λmin) 份 ρ 副本，同样以 0.99 的成功概率制备 ρ 支撑集上唯一的反对称态。形式化定理指出，只要 n ≥ C r/λmin（C > 0 为足够大的常数），算法返回该态的概率至少为 1 − (ε + exp(−Ω(n λmin)))。

这一版本的分析更复杂，用到了对称群表示论工具，具体是 Pieri 规则。作者强调了一个结构性差异：复用版本无论 n 取何值，都能从可用的 n 份副本构造出表示论上可能的最大反对称态；而丢弃版本只在 n 足够大时才能做到。他们指出，这一特性对于把复用算法应用到 Schur 采样流程至关重要。

Schur 采样在部分 n 与 d 区间改进

论文把带副本复用的反对称化应用于给出弱 Schur 采样和酉 Schur 采样的替代算法。在弱 Schur 采样中，任务是从分布 (p_λ) 中采样一个划分 λ，使得 Σ_λ |p_λ − Tr[Π_λ ρ]| ≤ δ，其中 Π_λ 投影到 Schur 变换下的 λ-同型分量。酉 Schur 采样还要求输出一个态，近似恢复 W_λ 模上的约化态。

论文给出的推论是：以精度 δ 进行弱 Schur 采样和酉 Schur 采样，可以用 Õ(n² d log(1/δ)) 次受控 SWAP 操作和 Õ(n² d log²(1/δ)) 的 T-count 完成。作者将其与先前针对一般 d 的常数精度弱/酉 Schur 采样方法比较，称那些方法的门复杂度形如 Õ(n^a d^b)，其中整数 a ≥ 1、b ≥ 0 且 a + b ≥ 4。他们的过程达到 a = 2、b = 1，即 a + b = 3，因此在某些 n 与 d 区间改进了总体复杂度。

这一改进并非普遍成立。论文明确指出，当 d = 2 时，使用 Õ(n) 次随机 SWAP 测试的酉 Schur 采样算法优于他们的方法。因此这一比较在副本数 n 和局部维度 d 上都依赖于具体区间。

纯度放大以更简单路径保持最优性

论文还发展了一个基于反对称化的纯度放大过程。纯度放大是 Li 等人提出的任务：给定混合 qudit 态 ρ 的 n 份独立同分布副本，输出一个态 ρ′，使其接近与 ρ 最大特征向量达到最大重叠。作者把他们的过程描述为对 Li 等人最优量子纯度放大协议的简化，同时产生相同的输出态。

论文给出的推论是：以精度 δ 实现最优纯度放大，需要 Õ(n² d log(1/δ)) 次受控 SWAP 操作和 Õ(n² d log²(1/δ)) 的 T-count。先前工作使用广义量子相位估计实现纯度放大，总体门复杂度在 n 和 log d 上为多项式。论文明确表示，它对局部维度 d 的依赖更差，但如果把 d 视为固定，则它实现了改进的门复杂度，且实现可以说更简单。

这里有一个适用范围条件很重要：由于纯度放大过程建立在带副本复用的反对称化之上，作者指出它不适用于该任务的流式版本。

密码学归约只在有间隙低秩时成立

第二个应用是从有间隙混合态单向态生成器到纯态单向态生成器的归约。单向态生成器是一族带密钥的态 φ_k，从 φ_k 的副本中学习密钥 k 是困难的，而在给定 k 时验证 φ_k 是计算容易的。对于纯 φ_k，存在自然的验证策略，例如重复 SWAP 测试，或对未知态反计算制备电路并在计算基下测量；对于混合 φ_k，这些策略不能立即判定未知态是否等于 φ_k。

论文的归约使用流式反对称化过程。如果存在 1/t-有间隙的秩 r 单向态生成器，每个 ρ_k 的秩为 r 且最小特征值至少为 1/t，那么正比于 Σ_σ sign(σ) P_σ (|ψ_{k,1}⟩ ⊗ … ⊗ |ψ_{k,r}⟩) 的纯态可以在 poly(r, t, log d) 时间内从多项式多份 ρ_k 副本制备出来，失败概率可忽略。那么，任何能破坏所得纯态生成器单向性的算法，也就能破坏原来的混合态生成器。

该归约被描述为在黑盒归约中几乎紧的。论文指出，当 r 变得足够超多项式、增长快于 λ log λ 时，秩 r 单向态生成器与可高效验证的单向态生成器之间存在量子态分离，并可提升为酉预言机分离。作者还指出，能否利用高效验证算法从极高秩混合态单向态生成器得到纯态单向态生成器，或者这两种概念是否实际上彼此分离，仍是未解问题。

内存、副本预算与秩决定算法选择

论文自身的比较归结为工作内存与副本数之间的权衡。类流式算法使用 O(r log d) 量子比特工作内存，但请求 O(r log r / λmin) 份副本；带副本复用的算法请求 O(r/λmin) 份副本，但需要更大的量子内存来保存失败寄存器池。log r 的差距就是丢弃失败副本的具体代价。

第二个决策轴是下游任务。Schur 采样和纯度放大依赖带副本复用的版本，因为从可用 n 份副本构造表示论上可能的最大反对称态，正是这些流程所需要的。密码学归约依赖流式版本，因为它必须一次处理一份新副本。因此纯度放大结果不会延伸到流式设定。

第三个轴是 n 与 d 的区间。Schur 采样相对先前门复杂度的改进只在某些 n 与 d 区间成立，而当 d = 2 时，Õ(n) 次随机 SWAP 测试方法优于它。对于纯度放大，对 d 的依赖比先前工作更差，因此改进的门复杂度适用于把 d 视为固定的情形。读这篇论文最有用的方式不是认为反对称化在任何设定下都便宜，而是认识到它的成本由 r/λmin 决定，内存由 r log d 决定，优势则取决于任务是否需要副本复用以及 d 是否小。

本文引用的文献