Shadow bootstrapping: Nearly minimal-setting pure-state tomography with shallow Clifford measurements

技术摘要：用于近极小设置下纯态量子态层析的阴影引导（Shadow Bootstrapping）技术

问题陈述
量子态层析（QST）旨在从测量数据中重建未知的量子态。对于维度为 $d=2^n$ 的 $n$ 量子比特纯态 $|\psi\rangle$，要达到保真度 $1 - |\langle \hat{\psi}|\psi\rangle|^2 \le \epsilon$，其最优样本复杂度已知为 $\Theta(d/\epsilon)$ 个副本。虽然已有多种协议实现了这一样本复杂度，但一个显著的瓶颈在于所需的不同测量设置的数量。许多现有方法要求的设置数量随 $1/\epsilon$ 呈多项式增长，或随 $d$ 呈线性增长，这由于电路编译和控制程序变更导致了巨大的实验开销。此外，存储大量采样次数的原始测量结果也非常耗费内存。本研究的目标是在实现最优样本复杂度的同时，使用近乎极小的测量设置数量（理想情况下与 $d$ 无关，且对 $1/\epsilon$ 为多项式对数级），并保持来自紧凑数据表示的高效经典后处理。

方法论
本文提出了一种利用非自适应单副本浅层 Clifford 测量和一种称为**阴影引导（shadow bootstrapping）**的新技术的两阶段算法。

1. 测量系综： 该协议使用两层 Clifford 系综，其中电路由作用于 $k$ 量子比特块（其中 $k = \Theta(\log n)$）的交错局部 Clifford 幺正变换层组成。这确保了电路深度为 $O(\log n)$。
2. 数据表示： 算法不再存储原始位串列表，而是将测量结果聚合为逐基组直方图（per-basis histograms）。这降低了内存需求，并作为经典后处理的输入。
3. 初始化（树状重建）：
   • 算法首先构建一个与目标态 $|\psi\rangle$ 具有常数重叠（$\ge 1/2$）的初始估计 $|\sigma_0\rangle$。
   • 这是通过一个递归重建框架实现的（受 [GGH+26] 启发），该框架通过从代表前缀条件态的二叉树叶节点向上构建到根节点来构建状态。
   • 在每个节点处，利用从直方图中导出的阴影估计量估计一个 $2 \times 2$ 的“重建矩阵”。该矩阵的最高特征向量提供了组合子估计量的系数。
   • 此阶段使用 $O(d)$ 个副本和 $O(n^3)$ 个测量设置，确保初始估计足够精确，以引导下一阶段的引导过程。
4. 阴影引导（迭代精炼）：
   • 核心创新是一个迭代精炼过程，它通过仅使用常数个新测量设置，在每个阶段将目标保真度减半。
   • 方差缩减： 标准的阴影估计量由于测量基底的随机选择而产生波动。阴影引导通过使用当前估计值 $|\sigma_{t-1}\rangle$ 作为参考来减轻这种波动。
   • 残差估计： 对于新的一批测量，算法计算一个“残差估计量”，定义为经验阴影估计量与基于 $|\sigma_{t-1}\rangle$ 的理论预测之间的差异。
   • 由于参考态 $|\sigma_{t-1}\rangle$ 与真实态接近，预测值与观测频率高度匹配，从而导致残差的方差随当前误差而非全维度进行缩放。
   • 算法通过将平均残差加到之前的状态矢量上并进行归一化来更新估计值。
   • 该过程重复进行 $J = O(\log(1/\epsilon))$ 个阶段。每基组的采样次数（shots）呈指数级增加（$S_t \propto 2^t$）以抑制 shot noise，同时每阶段新增的基组数量保持不变（$N_t = O(1)$）。
5. 经典后处理：
   • 算法避免了构建稠密的 $d \times d$ 阴影矩阵。相反，它利用 Clifford 系综的结构和 Walsh–Hadamard 变换直接对向量应用逆阴影通道。
   • 这使得直接处理直方图并计算更新在 $\tilde{O}(d)$ 时间和内存内完成成为可能。

核心贡献

• 阴影引导（Shadow Bootstrapping）： 一种利用当前状态估计来降低后续残差估计量方差的技术，从而能够以常数个新增测量设置实现高精度重建。
• 近极小设置： 该算法实现了 $O(d/\epsilon)$ 的最优样本复杂度，同时仅使用 $\tilde{O}(1)$ 个不同的测量设置（具体为 $O(n^3 + \log(1/\epsilon))$），相比于以往设置随 $1/\epsilon$ 或 $d$ 缩放的方法有了显著改进。
• 高效直方图处理： 该方法展示了如何直接从输出直方图中进行近线性时间（$\tilde{O}(d)$）的经典后处理，绕过了密集的矩阵构建。
• 浅层电路： 协议利用了深度为 $O(\log n)$ 的非自适应 Clifford 测量，使其适用于近期的量子设备。

结果
本文为 $n$ 量子比特纯态 $|\psi\rangle$ 和目标保真度 $\epsilon$ 建立了以下理论保证：

• 样本复杂度： $T = O(d \log(1/\delta) / \epsilon)$ 个副本，在对数因子意义上是优的。
• 测量设置： $N = \tilde{O}(1)$（具体为 $O(n^3 + \log(1/\epsilon))$）个不同的测量基底。
• 电路深度： $O(\log n)$。
• 经典运行时间： 在给定每基组直方图的情况下为 $\tilde{O}(d)$（忽略关于 $d, 1/\epsilon, 1/\delta$ 的多项式对数因子）。
• 成功概率： 算法输出的状态 $|\hat{\psi}\rangle$ 满足 $1 - |\langle \hat{\psi}|\psi\rangle|^2 \le \epsilon$，且概率至少为 $1-\delta$。

重要性
作者声称这是第一个同时实现以下目标的算法：

1. 最优样本复杂度（$O(d/\epsilon)$）。
2. 近乎极小的测量设置数量（与 $d$ 无关，且对 $1/\epsilon$ 为多项式对数级）。
3. 从紧凑直方图数据进行近线性时间经典后处理。
4. 浅层测量电路（$O(\log n)$ 深度）。

通过将测量设置的数量与目标精度和维度解耦，这项工作解决了电路编译和控制的开销问题。此外，使用直方图和高效的基于矢量的更新，减轻了经典重建的内存和计算负担，使高保真纯态层析更具可扩展性。阴影引导技术也被指出可能适用于低秩混合态层析和通道学习。