Learning Sparse Quantum States

技术摘要：学习稀疏量子态

问题陈述
本文探讨了针对 $k$-稀疏量子态的量子态层析（Quantum State Tomography）问题。虽然经典分布学习算法在处理 $k$-稀疏分布时可以实现对支持集大小 $k$ 的高效缩放，但标准的量子态层析算法通常随完整的希尔伯特空间维度（$2^n$）或密度矩阵的秩进行缩放，而忽略了状态在固定基底（特别是计算基）下是否具有稀疏结构。作者旨在弥合这一差距，开发出其样本复杂度和时间复杂度能近线性地随稀疏度 $k$（以及混合态的秩 $r$）缩放，而非随指数维度 $2^n$ 缩放的算法。

方法论
本文提出了一个学习稀疏态的统一方法，其过程从相位态（Phase States）进展到一般纯态，最后到混合态。

1. 学习稀疏相位态：
   作者首先处理 $k$-稀疏相位态，定义为 $|\psi\rangle = \frac{1}{\sqrt{k}}\sum_{x \in S} e^{i\theta_x}|x\rangle$，其中 $|S|=k$。该算法分为两个阶段：

   • 支持集识别： 通过在计算基下测量该状态约 $O(k \log k)$ 次来学习支持集 $S$，并利用赠券收集者问题（Coupon Collector Argument）进行处理。
   • 相位恢复： 一旦已知支持集，算法将学习相对相位 $\theta_x$。这通过构建一个顶点为基态、边代表可学习相对相位的图来实现。作者使用一组随机线性函数（哈希函数）在 $\mathbb{F}_2$ 上将基态对映射到相同的输出。测量哈希寄存器会将状态投影到两个基态的叠加态上，即 $|x_1\rangle + e^{i(\theta_{x_2}-\theta_{x_1})}|x_2\rangle$，从而允许通过单比特层析估计相对相位。
   • 图连通性： 一个关键的技术贡献是证明了少量的（$O(\log k)$）随机线性函数足以生成直径为 $O(\log k)$ 的图。这确保了任何基态的相位都可以通过学习到的相对相位短路径相对于参考态来确定。

2. 学习一般稀疏纯态：
   对于一般稀疏纯态 $|\psi\rangle = \sum_{x \in S} \sqrt{p_x}e^{i\theta_x}|x\rangle$，其概率 $p_x$ 是非均匀的。作者借鉴了经典分布学习中的**分桶技术（Bucketing Technique）**来改进相位态算法：

   • 预处理： 使用一种经典分布学习算法来识别支持集，并将基态划分为若干个“桶”（概率能级），使得各桶内的概率近似均匀。
   • 分桶相位学习： 分别对每个桶应用相位图构建过程。至关重要的是，每个桶都包含一个共同的参考态（具有最高概率的基态），以确保全局相位的连贯性。
   • 误差分配： 样本复杂度按每个桶的概率质量进行分配。低概率状态的学习精度较低，这与它们对整体保真度的贡献相一致，从而避免了“低概率瓶颈”问题（即相位图中单个边的学习可能需要过多的样本）。

3. 学习稀疏混合态：
   对于 $k$-稀疏秩为 $r$ 的混合态，作者采用了**随机纯化通道（Random Purification Channel）**技术。

   • 归约： 他们利用一个量子通道，将 $m$ 个混合态 $\rho$ 的副本转换为 $m$ 个均匀随机纯化态 $|\rho\rangle$ 的副本。
   • 稀疏性保持： 研究表明，如果 $\rho$ 是 $k$-稀疏且秩为 $r$，则其随机纯化态是一个 $kr$-稀疏的纯态。
   • 算法： 然后将纯态层析算法应用于这些纯化后的样本，以重建混合态 $\rho$。

关键结果与复杂度界限
本文确立了以下复杂度界限（省略了关于 $k, n, 1/\epsilon$ 的多项式对数因子）：

• 纯态： 对于未知的 $n$-比特 $k$-稀疏纯态，算法输出一个估计值 $|\hat{\psi}\rangle$，满足保真度 $|\langle \psi | \hat{\psi} \rangle|^2 \geq 1 - \epsilon$，所需的：

  • 样本复杂度： $\tilde{O}(k/\epsilon)$ 个副本。
  • 时间复杂度： $\tilde{O}(kn/\epsilon)$。
    这些界限在多项式对数因子范围内是优的，相比于一般层析实现了指数级的提升（当 $k \ll 2^n$ 时）。

• 混合态： 对于未知的 $n$-比特 $k$-稀疏秩为 $r$ 的混合态，算法输出一个估计值 $\hat{\rho}$，满足保真度 $F(\rho, \hat{\rho}) \geq 1 - \epsilon$，所需的：

  • 样本复杂度： $\tilde{O}(kr/\epsilon)$ 个副本。
  • 时间复杂度： $\text{poly}(m, n)$，其中 $m$ 为样本复杂度。
    样本复杂度接近最优。然而，当 $r > 1$ 时，时间复杂度尚未达到最优，因为它目前受限于实现随机纯化通道的开销（该过程依赖于 Schur 变换）。

意义与主张
作者声称这项工作提供了首个近优算法用于学习稀疏量子态，实现了随支持集大小 $k$ 而非维度 $2^n$ 缩放的样本复杂度和时间复杂度。

• 最优性： 纯态算法在参数 $n, k, 1/\epsilon$ 下被证明在样本和时间复杂度上都是优的（至多差一个对数因子）。
• 多项式时间学习： 这些结果意味着，对于在高效可计算基底中稀疏的态（即 $k = \text{poly}(n)$），学习可以在多项式时间内完成。这扩展了高效可学习量子态的范畴，使其超越了稳定器态（Stabilizer States）或矩阵乘积态（MPS）。
• 鲁棒性： 算法对微量噪声具有鲁棒性，并且不严格要求输入精确的稀疏参数 $k$；它们可以通过学习支持集或使用一个上界来运行。
• 开放问题： 本文指出主要开放问题是如何获得一个时间最优的混合态层析算法，使其能随 $k$ 和 $r$ 高效缩放，具体方法是通过改进随机纯化通道的实现。同时，作者也提到移除纯态时间复杂度中多项式对数因子的挑战仍是一个开放课题。

该工作并未提出新的实验装置或特定应用，仅探讨了在理论层面对于学习特殊类别状态（如 GHZ、W、Dicke 态及稀疏相位态）的意义，以及对伪随机量子态的安全性分析。