量子态的经典阴影（Classical Shadows）

一、量子态层析（Quantum State Tomography）

目前，人们已经可以制备由成百上千个量子比特所构成的量子态（此处省略二十个参考文献）。

但是我们如何知道制备的量子态 \(\rho\) 的确是我们想要的 \(\rho\) ？或者更宽泛地说：如何学习一个量子态 \(\rho\) 的（部分或者所有）信息？

为了学习量子态 \(\rho\) ，我们需要先制备 \(\rho\) ，然后在不同的测量基下对其进行测量，得到概率分布函数，最后通过这些概率分布函数去学习 \(\rho\) 。这个过程就叫做量子态层析。

二、全量子态层析

如果我们的目标是完全重建 \(\rho\) ，即学习到 \(\rho\) 的全部信息，那么这个过程就叫做全量子态层析（Full State Tomography，简称 FST）。

以 \(n\) 个 qubit 构成的系统为例，其量子态 \(\rho\) 可以写成：

\[\begin{aligned} \rho &= \frac{1}{2^n}\sum_i c_i P_i \\ &\phantom{==} P_i = \sigma_{i_1}\otimes \cdots \otimes \sigma_{i_n}, \quad i=(i_1,...,i_n), \quad i_k= 0,1,2,3 \\ &\phantom{==} \sigma_0=\mathbb{I},\, \sigma_1=X,\,\sigma_2 = Y,\,\sigma_3=Z \end{aligned}\]

其中 \(\sigma_0=\mathbb{I},\, \sigma_1=X,\,\sigma_2 = Y,\,\sigma_3=Z\) 为单比特的泡利矩阵，并且 \(c_i = \operatorname{tr}[\rho P_i]\) 。

可见，我们只要测量算符 \(P_i\) 的期望值 \(c_i = \operatorname{tr}[\rho P_i]\) ，就可以对量子态 \(\rho\) 进行 FST。这些 \(c_i\) 叫做泡利系数。

一共有 \(4^n - 1\) 个泡利系数要测量，因为 \(P_0 = \mathbb{I}^{\otimes n}\) 为单位矩阵，导致 \(c_{0}\) 总是等于 1。

这种测量方法叫做泡利测量（Pauli Measurements），是人们最常用的方法。

注意到实际上只需要 \(3^n\) 个测量基，因为其余 \((4^n-3^n-1)\) 个 \(P_i\) 的测量结果是这 \(3^n\) 个 \(P_j\) 的测量结果的边缘分布（marginal distribution）。

例如， \(\mathbb{I}\otimes Y\) 的测量结果完全可以由 \(X \otimes Y\) 的测量结果得到——因为前者的概率分布是后者的概率分布的边缘分布。

本文主要以 \(n\) 个 qubit 构成的系统为例，但推广到 qudit 也是很直接的。但本文暂不涉及连续变量系统。

2.1 样本复杂度

前面说过，为了学习量子态 \(\rho\) ，我们需要先制备 \(\rho\) 的多个样本，然后在不同的测量基下对它们进行测量。于是，一个很直接的问题由之而来：

对于一个 \(d\) 维量子态 \(\rho\) ，我们需要多少个样本才能在误差范围 \(\epsilon\) 内估计 \(\rho\) ？

一个 \(d\) 维量子态 \(\rho\) 定义为 \(d\) 维希尔伯特空间上迹为 1 的半正定算子，通常也叫密度矩阵，由 \(d^2-1\) 个实参数刻画。

为了更好理解和阐述这个问题，我们先引入一些术语。我们定义样本复杂度（sample complexity）：随着维数 \(d\) 增加和误差 \(\epsilon\) 降低，所需要样本数 \(N\) 也会增长。增长速度 \(N \sim O(f(d,\epsilon))\) 就是样本复杂度。

对于单个量子比特（Qubit）而言， \(d=2\) ，但对于 \(n\) 个量子比特所组成的系统，则是 \(d=2^n\) 。对于 \(n\) 个 k 维的 qudit，则是 \(d=k^n\) 。可见，希尔伯特空间维数 \(d\) 随粒子数 \(n\) 的增加而指数级增长。

接下来我们来看看误差 \(\epsilon\) 。刻画两个量子态 \(\rho\) 和 \(\sigma\) 之间的误差最常用的两个函数是保真度（Fidelity） \(F(\rho,\sigma)\) 和迹距离（Trace Distance） \(T(\rho,\sigma)\) ：

\[F(\rho,\sigma):=\operatorname{tr}\left[\sqrt{\sqrt{\sigma}\rho\sqrt{\sigma}}\right]^2\]

\[T(\rho,\sigma):=\frac{1}{2}||\rho-\sigma||_1\]

其中 \(||\cdot||_1\) 是 trace norm / 1-norm，定义为 \(|| A||_1 =\operatorname{tr}\left[\sqrt{A^\dagger A}\right]\) 。

保真度越接近 1，迹距离越接近 0，误差就越小。它们满足 ：

\[1-\sqrt{F} \le T \le \sqrt{1-F}\]

如果以迹距离 \(T(\rho,\sigma)\) 作为误差 \(\epsilon\) ，那么以保真度计算的误差 \(\delta:=1-F\) 则满足 \(\delta\ge \epsilon^2\) 。

本文主要使用迹距离 \(||\rho - \sigma||_1\) 作为误差（额外的常数 1/2 在 scaling 下不重要）。

2.2 样本复杂度的上界

直觉上来看，为了重建量子态 \(\rho\) ，样本复杂度随 \(d\) 的变化至少是 \(\sim d^2\) ，或写成 \(\Omega(d^2)\) ，这是因为我们至少需要 \(\sim d^2\) 个测量基（POVM）元素，才能使测量基是信息完全（informationally complete）的。另一方面，我们要多次测量从而使估计量逼近真实值。为了使两者的误差小于 \(\epsilon\) ，样本复杂度与误差 \(\epsilon\) 之间很可能是反比的关系 \(\sim O(\epsilon^{-m})\) 。

因此，我们猜想，样本复杂度为 \(\boxed{ N = O(d^l/\epsilon^m) }\) ，其中 \(l \ge 2\) 。接下来，我们来研究不同测量方式下的样本复杂度。

2.3 泡利测量的复杂度

接下来我们给出样本复杂度的一个较为宽松的上界[1]，它是由前文提到，也是人们最常用的泡利测量（Pauli measurements）给出的。

我们先介绍霍夫丁不等式（Hoeffding’s inequality），后面会用到：

Hoeffding 不等式
给定 \(N\) 个独立随机变量 \(X_i,\,i=1,...,N\) ，取值范围分别为 \([a_i,b_i]\) ，那么它们的和 \(S=\sum_iX_i\) 满足
\(\begin{aligned} P(|S-\mathbb{E}(S)| \ge \epsilon) < 2\exp \left[-\frac{2 N^2 \epsilon^2}{\sum_{i}(b_i-a_i)^2} \right] \end{aligned}\)
如果 \(X_1,...,X_N\) 的分布相同，取值范围为 \([a,b]\) ，并且记均值为 \(Y = S/N=\sum_iX_i /N\) ，则有
\(\begin{aligned} P(|Y-\mathbb{E}(Y)| \ge \epsilon) < 2\exp \left[ -\frac{2 N \epsilon^2}{(b-a)^2} \right] \end{aligned}\)

接下来我们运用 Hoeffding 不等式。

对于量子态 \(\rho = \frac{1}{2^n}\sum_i c_i P_i \) ，我们反复测量算符 \(P_i\) ，取结果的平均值为 \(c_i = \operatorname{tr}[\rho P_i]\) 的估计量 \(\hat{c}_i\) 。

对 \(\hat{c}_i\) 运用 Hoeffding 不等式，并注意到 \(\hat{c}_i\) 的取值为 \(\pm1\) ，有：

\(P[|\hat{c}_i-c_i| > \epsilon_i] \le 2 \exp \left[-N\epsilon_i^2/2\right]\)

其中 \(N\) 为重复测量 \(P_i\) 的次数。

于是根据 union bound，在 \((4^n-1)\) 个 \(c_i\) 中，任意一个 \(|\hat{c}_i-c_i| > \epsilon_i\) 的概率为：

\(P[|\hat{c}_i-c_i| > \epsilon_i, \,\exists \, i] \le (4^n - 1) \cdot 2 \exp \left[-N\delta^2/2\right]\)

现在，我们希望所有的 \(|\hat{c}_i-c_i|\) 都大概率小于 \(\epsilon_1\) 。也就是说，误差大于 \(\epsilon_1\) 的概率为一个很小的数 \(\delta \ll 1\) 。令上式右边为 \(\delta\) 得到：

\(N= \frac{2}{\epsilon_1^2}\log \frac{2\cdot (4^n-1)}{\delta}= O\left(\frac{n -\log \delta}{\epsilon_1^2}\right) \)

代入 \(d=2^n\) 得：

\(\boxed{ N= O(\log(d/\delta)/\epsilon^2_1) }\)

这就是在误差 \(\epsilon_1\) 内以低于失败率 \(\delta\) 估计所有泡利系数所需要的样本复杂度。

---

注意！这里的 \(\epsilon_1\) 只是单个泡利系数 \(c_i\) 的测量误差，而我们希望得到的是密度矩阵 \(\rho = \frac{1}{2^n}\sum_i c_i P_i \) 的误差 \(\epsilon\) 。

为此，我们定义误差矩阵：

\(\Delta = \hat{\rho}-\rho = \sum_i(\hat{c}_i-c_i)P_i\)

并且要求它的 trace norm 小于 \(\epsilon\) ：

\(||\Delta||_1<\epsilon\)

注意到 Hilbert-Schmidt norm 更好计算： \(||\Delta||_2^2 := \operatorname{tr}[A^\dagger A] = \frac{1}{2^n}\sum_i |\hat{c}_i-c_i|^2\) ，因为
\(\operatorname{tr}[P_i^\dagger P_j]=\operatorname{tr}[P_iP_j]=\delta_{ij}\) 。

于是我们可以使用柯西不等式 \(||A||_1 \le \sqrt{d}||A||_2\) ，其中 \(d = 2^n\) 为矩阵的阶数：

\(||\Delta||_1 \le \sqrt{2^n}||\Delta||_2 = (\sum_i |\hat{c}_i-c_i|^2)^{1/2} \le (\sum_i \epsilon_1^2)^{1/2} = (4^n-1)^{1/2} \,\epsilon_1\)

令 \(||\Delta||_1 \le \epsilon\) ，于是 \(\epsilon \sim(4^n-1)^{1/2} \,\epsilon_1\sim 2^n \epsilon_1\) ，所以

\(N \sim (n - \log \delta)/\epsilon_1^2 \sim (n - \log \delta)4^n /\epsilon^2 = \log \frac{d}{\delta} \cdot d^2/\epsilon^{2}\)

最后，考虑到有 \(3^n\) 个测量基，在每个测量基下都需要测量 \(N\) 次。因此：

\(N \mapsto 3^n \cdot N \sim \log \frac{d}{\delta} \cdot d^{3.585} /\epsilon^{2}\)

通常不将失败率 \(\delta\) 考虑在样本复杂度范围内，于是：

\[\boxed{ N = O(\log d \cdot d^{3.585} /\epsilon^{2}) = O(N \cdot 12^N/\epsilon^2)} \]

update: 2025 年 2 月，上界的记录已经被刷新了，是 \(\boxed{ N = O(\log d \cdot d^{3.322} /\epsilon^{2}) = O(N \cdot 10^N/\epsilon^2)} \) ，而下界则被证明是 \(\Omega(d^{3.188}\log (d)/\epsilon^2)=\Omega(N \cdot 9.118^N /\epsilon^2)\) [2]。

2.3 单样本测量的样本复杂度

实际上，我们可以做得更好：上述上界可以降低到 \(\boxed{O(\log d \cdot d^3 / \epsilon^{2})}\) 。

这是因为 \(3^n\) 个测量基（measuremet settings）给出了 \(3^n \cdot 2^n = 6^n = d^{2.585}\) 个 POVM 元素，但保证 informationally complete 所需要的最少的 POVM 元素数量是 \(4^n = d^2\) 个。可见，我们可以使用正好拥有 \(d^2\) 个元素的 SIC-POVM，或者使用 MUB (Mutually Unbiased Bases)，它包含 \((d+1)\) 个测量基，每个测量基有 \(d\) 个元素，共 \(d(d+1)\) 个 POVM 元素。不管用哪种方法，都可以将样本复杂度上界降低到 \(O(\log d \cdot d^3 /\epsilon^{2})\) 。

下界则被证明是 \(\Omega(d^3 /\epsilon^{2})\) [3]，但尚未发现具体的测量方法。与上界相比，下界只是少了 \(\log(d)\) ，对于一般实验来说影响不大。

2.4 多样本测量的样本复杂度

以上的测量方法都属于单样本测量（Single-copy measurements），因为我们一次只测量一个样本。我们可以考虑更一般的情况——通过纠缠多个样本 \(\rho^{\otimes n}\) 进行联合测量，这叫做多样本测量（Multi-copy measurements）。这样的测量需要量子存储器（quantum memory），在目前的量子硬件中基本很难实现。

人们已经证明，对于这种最一般的测量方式，样本复杂度的确界为 \(\boxed{\Theta(d^2 / \epsilon^{2})}\) [4] [5]。这一点直到 2016 年才被证明。

总结：

\[\begin{aligned} \hline & \text{POVM} & \quad & \text{Sample Complexity}\,(d=2^n)\\ \hline & \text{Pauli Measurements} & \quad & O(d^{3.322}\log (d)/\epsilon^2), \, \Omega(d^{3.188}\log (d)/\epsilon^2) \\ & \text{Single-copy measurements} & \quad & O(d^{3}\log (d)/\epsilon^2),\,\Omega(d^3 / \epsilon^2) \\ & \text{Multi-copy measurements} & \quad & \Theta(d^2/\epsilon^2)\\ \hline \end{aligned}\]

注意，该表中 \(O(\cdot)\) 代表上界， \(\Omega(\cdot)\) 代表下界， \(\Theta(\cdot)\) 代表紧确界。

三、经典阴影（Classical Shadows）

在上一节中我们提到，如果要测量所有泡利系数（泡利算符的期望值），并要求所有结果的误差都不大于 \(\epsilon\) ，且失败率不高于 \(\delta\) ，那么样本复杂度为：

\[\boxed{ N = O\left(\frac{n-\log\delta}{\epsilon^2}\right)=O\left(\log \left(\frac{d}{\delta}\right) \cdot \epsilon^{-2}\right) }\]

这揭示了一个似乎惊人的事实：如果我们只关注算符的期望值，而不是量子态本身，那么样本复杂度可以大大降低到对数级别，完全失去了 \(d^{\sim2-3.5}\) 的依赖。

实际上，对于任何 \(M\) 个算符 \(O_1,...,O_M\) ，如果希望在误差 \(\epsilon\) 内以低于 \(\delta\) 的失败率估计它们的期望值，那么只需要样本复杂度为：

\[\boxed{ N \sim \log(M/\delta)\cdot \epsilon^{-2} \cdot (\max_i||O_i||^2_{\text{shadow}}) }\]

其中 \(||\cdot||_{\text{shadow}}\) 的具体形式取决于测量手段。这个结果来自于 2020 年 Huang et al. 的著名的“经典阴影”（Classical Shadows）[6]。

从第二节的分析可以看出，这一复杂度并不令人意外。那么，为什么“经典阴影”在近年来会变得如此热门呢？

个人认为，这是因为：以往关于样本复杂度的研究，动机多在于缩小理论上的上界，而不是物理应用；即便存在测量方法，在实验中也难以实现，更多属于数学家口中的“理论上存在”。而经典阴影提供了一种简单、具体且有效的测量方法：实现步骤十分明确，实验物理学家可以开箱即用。另外，对数复杂度本身就是一个很大的噱头（即便它并不像乍一看那样令人惊讶）。

实际上，早在 2017 年，Scott Aaronson 就提出了阴影层析（Shadow Tomography）[7]，也指出了对数复杂度 \(\log(M)\) 。只不过他考虑的是 \(M\) 个 two-outcome POVM 的概率 \(\operatorname{tr}[\rho E_i]\) ，而不是 \(M\) 个一般的物理量算符 \(\langle O_i \rangle = \operatorname{tr}[\rho O_i]\) 。之所以 Shadow Tomography 的工作没有 Classical Shadows 那么受关注，也是因为它给出的测量手段比较复杂。

趣事：Scott Aaronson 的博客很有意思，例如这篇争议很大的：Shtetl-Optimized » Blog Archive » Cargo Cult Quantum Factoring

3.1 经典阴影的具体实现

现在我们来看看 Classical Shadows 具体是怎么执行的。

粗略来看，执行步骤分为两步：

1. 测量量子态得到所谓的“Classical Shadows”，并存储到经典计算机中

2. 从存储的 Classical Shadows 出发，通过一定的算法同时估计 \(M\) 个算符的期望值。

我们先来看 1，做法如下：

1.1 从 Clifford 算符中随机选出一个 \(U\) ，作用到量子态 \(\rho\) 上，得到 \(U\rho U^\dagger\) 。

1.2 对 \(U\rho U^\dagger\) （在 computational basis 下）进行测量，得到结果 \(|b\rangle \in \{0,1\}^n\)

1.3 将 \(U | b\rangle \langle b| U^\dagger\) 存储到经典计算机的内存中

现在我们来看看 \(U | b\rangle \langle b| U^\dagger\) 的期望值是什么。注意到这里有两个随机变量， \(U\) 和 \(|b\rangle\) 。我们所说的期望值是对于这两个随机变量而言的，也就是：

\[\begin{aligned} &\mathbb{E}_{U,b}[U^\dagger |b\rangle\langle b| U^\dagger] \\ &:= \mathbb{E}_U\left[\sum_{b=0,1} \langle b | U \rho U^\dagger | b\rangle (U^\dagger |b\rangle\langle b| U^\dagger)\right] \end{aligned}\]

可以证明这是一个量子信道（Quantum Channel），记为：

\[\mathcal{M}(\rho):=\mathbb{E}_{U\sim \nu}\left[\sum_{b=1}^d \langle b | U \rho U^\dagger | b\rangle (U^\dagger |b\rangle\langle b| U^\dagger)\right]\]

其中 \(\nu\) 是 \(U\) 服从的分布，它是一个均匀分布。它的概率空间不是通常的数轴，而是一个群，在此处是 Clifford 群。

可以证明（证明见下一节）， \(\mathcal{M}(\rho)\) 可以解析地写成：

\[\boxed{ \mathcal{M}(\rho)= \frac{\rho + \operatorname{tr}[\rho] \mathbb{I}}{d+1} }\]

其中 \(d=2^n\) 为希尔伯特空间的维数。这个 \(\mathcal{M}(\rho)\) 其实就是一个 depolarizing channel。

于是可以直接得到 \(\mathcal{M}\) 的逆为：

\[\boxed{ \mathcal{M}^{-1}(X)=(d+1) X - \operatorname{tr}[X]\mathbb{I} }\]

于是我们可以把 \(\mathcal{M}^{-1}(U|b\rangle\langle b| U^\dagger)\) 作为 \(\rho\) 的估计量：

\[\boxed{ \begin{aligned} \hat{\rho}&=\mathcal{M}^{-1}(U|b\rangle\langle b| U^\dagger)\\ &=(d+1) U|b\rangle\langle b| U^\dagger - \mathbb{I} \end{aligned} }\]

这个估计量无偏，因为

\[\boxed{ \mathbb{E}[\hat{\rho}]=\rho }\]

现在，重复 \(N\) 次步骤 1，我们可以得到 \(N\) 个 \(\hat{\rho}\) ：

\[\boxed{ S(\rho,N)=\{\hat{\rho}_1,\hat{\rho_2},...,\hat{\rho}_N\} }\]

这个 \(S(\rho,N)\) 就是 \(\rho\) 的经典阴影。

于是第二步（估计 \(\{O_1,...,O_M\}\) 的期望值 \(\{o_1,..., o_M\}\) ）就很直接了：

\[\hat{o_i}=\operatorname{tr}[\hat{\rho} O_i] = \operatorname{tr}[\sum_{k}\hat{\rho}_k O_i]\]

为了避免离群值的影响，给成功率兜底，实际需要使用平均数中位数（Median of means）法，将 \(S(\rho,N)\) 分成 \(K\) 份，对每一份求 \(\hat{o_i}\) ，然后取 \(K\) 个结果的中位数。

3.2 Haar 测度与 Unitary t-design

很明显，上一节描述的步骤之所以成立，关键在于下式：

\[\boxed{ \mathcal{M}(\rho)= \frac{\rho + \operatorname{tr}[\rho] \mathbb{I}}{d+1} }\]

如何证明这个式子呢？我们需要用到一些 Haar 测度与 t-design 的知识。

直观来看，Haar 测度就是群上的“均匀”分布。由于我们考虑的概率分布（测度）是在幺正算符（也就是 \(U(d)\) 群）构成的空间上，而不是普通的数轴上，所以像“均匀”分布这样的概念需要特别的刻画。

Haar 测度（Haar Measure）

给定群 \(U(d)\) 以及它的一个 Borel 子集 \(S\) ，如果对于所有 \(g\in U(d)\) ，测度 \(\mu\) 满足：
\(\mu(g S)=\mu(S)=\mu(Sg)\)
那么称 \(\mu\) 是一个 Haar 测度。

这里 \(U(d)\) 指的是 \(d\) 维幺正群，也就是 \(d\) 维希尔伯特空间上所有幺正算符构成的群。所谓 Borel 子集，可以理解为最简单的一种 \(\sigma\) -代数，也就是可测集的集合。

可见，Haar 测度利用平移不变性来定义“均匀”。

直观来看，如果我们希望量子态层析的误差是均匀的，那么我们就希望按照 Haar 测度从 \(U(d)\) 中随机选取量子门。

然而，在实际的量子硬件中，为了操作简便或者由于硬件的限制，我们一般不会从连续的 \(U(d)\) 中选取量子门。通常的做法是从有限个量子门的集合中均匀随机选取。一般选取 Clifford 群作为这个集合。

于是，一个直接的问题由之而来：有限群的均匀分布能够“逼近”或者“模拟”连续群的均匀分布吗？

更具体地，给定 \(U(d)\) 上的 Haar 测度 \(\mu\) ，及其（有限元素的）子集 \(S \subsetneq U(d)\) 上的测度 \(\nu\) ， \(\nu\) 是否能满足

\[\mathbb{E}_{V\sim \nu}[V^{\otimes t}O V^{\dagger \otimes t}] = \mathbb{E}_{U \sim \mu}[U^{\otimes t}O U^{\dagger \otimes t}]\]

对于希尔伯特空间 \(\mathcal{H}^{\otimes t}:= (\mathbb{C}^d)^{\otimes t}\) 上的任意算符 \(O \in \mathcal{L}({\mathcal{H}^{\otimes t}})\) 成立？

如果成立，那么称 \(\nu\) 为一个 unitary t-design。以下简称 t-design。

为了方便起见，定义算符 \(A\in \mathcal{L}({\mathcal{H}^{\otimes t}})\) 的矩 \(M^{(t)}(A)\) 为：

\[M^{(t)}(A):=\mathbb{E}_{U \sim \mu}[U^{\otimes t}A U^{\dagger \otimes t}]\]

于是我们可以用一句话概括 t-design 的定义：

Unitary t-design

\(U(d)\) 的有限子集上的测度 \(\nu\) 被称为 unitary t-design，如果它的 t 阶矩与 Haar 测度的 t 阶矩相同。

3.3 Schur-Weyl Duality

现在我们来看看 Haar 测度的 t 阶矩 \(M^{(t)}\) ，它有许多有用的性质，我们接下来会不加证明地给出这些性质。

我们先把 \(\mathcal{L}(\mathcal{H}^{\otimes t})\) 通过 Hilbert-Schmidt 内积（HS 内积）变成一个内积空间。HS 内积定义为：

\[\langle A ,B\rangle := \operatorname{tr}[A^\dagger B], \quad A,B \in \mathcal{L}(\mathcal{H^{\otimes t}})\]

有了内积之后，我们就能定义投影了。而 t 阶矩正是这个内积空间上的一个投影算子。

定理：t 阶矩 \(M^{(t)}\) 是投影到 commutant 上的投影算子

\(M^{(t)} \in \mathcal{L}(\mathcal{L}(\mathcal{H}^{\otimes t}))\) 是 HS 内积空间 \(\mathcal{L}(\mathcal{H}^{\otimes t})\) 上的一个投影算子，它将算子 \(A\) 投影到子空间 \(\text{Comm}^{(t)}(U(d))\) 上，其中 \(\text{Comm}^{(t)}(U(d))\) 是 \(U(d)\) 的 commutant，定义为所有与 \(B^{\otimes t}\) 可交换的算符的集合：

\(\text{Comm}^{(t)}(S) :=\{A \in \mathcal{L}(\mathcal{H}^{\otimes t}) \mid [A,B^{\otimes t}] = 0\quad\forall B\in S\}\)

可以证明， \(\text{Comm}^{(t)}(U(d))\) 是 \(\mathcal{L}(\mathcal{H}^{\otimes t})\) 的一个子空间。

Commutant 在群论中也叫 Centralizer。

换句话说，任何算子的 t 阶矩 \(M^{(t)}(A)\) 总是在 Commutant 中。

那么，这个 Commutant 有什么性质呢？

Schur-Weyl 对偶：Commutant 是所有置换算子张成的空间

\(\text{Comm}^{(t)}(U(d)) = \operatorname{span}(V_d(\pi): \pi \in S_t)\)

其中置换算子 \(V_d(\pi) \in \mathcal{L}(\mathcal{H}^{\otimes t})\) 定义为：

\(V_d(\pi) |\psi_1\rangle \otimes \cdots \otimes |\psi_t\rangle := |\psi_{\pi^{-1}(1)}\rangle \otimes \cdots \otimes |\psi_{\pi^{(-1)}(t)}\rangle\)

有了 Schur-Weyl 对偶，我们就可以将置换算子 \(V_{d}(\pi)\) 作为 Commutant 的一组基了。

不过，置换算符作为 Commutant 的基并不是彼此正交的，因为 \(\langle V_d(\pi), V_{d}(\sigma)\rangle \ne \delta_{\pi,\sigma}\) 。

实际上： \(\langle V_d(\pi), V_{d}(\sigma)\rangle = \operatorname{tr}[V_d(\pi)^{\dagger} V_{d}(\sigma)] = \operatorname{tr}[V_d(\pi^{-1}\sigma)]=d^{\# \text{cycle}(\pi^{-1}\sigma)}\)
其中 \(\#\text{cycle}(\pi)\) 是置换 \(\pi\) 的循环数（置换图中有多少个闭合的圈）。

于是，任何算子的 t 阶矩 \(M^{(t)}(A)\) 都可以写成 t 阶置换群对应的置换算子的线性组合。

利用这一点，我们可以轻松地计算一阶和二阶矩，因为一阶置换群是平凡的，只有单位算子 \(\mathbb{I}\) ，二阶置换群只有单位算子 \(\mathbb{I}_2 = \mathbb{I}^{\otimes2}\) 和 SWAP 算子，记为 \(F := \mathsf{SWAP}\) 。

算子的一阶矩和二阶矩：
\(\boxed{ M^{(1)}(A):=\mathbb{E}_{U \sim \mu}[UA U^\dagger]=\operatorname{tr}[A] \frac{\mathbb{I}}{d} }\)
\(\boxed{ M^{(2)}(A):=\mathbb{E}_{U \sim \mu}[U^{\otimes 2}A U^{\dagger \otimes 2}] = \alpha\ \mathbb{I}_2+ \beta\ F}\)
其中
\(\alpha = \frac{\operatorname{tr}(O)-d^{-1}\operatorname{tr}(FO)}{d^2-1}, \quad \beta = \frac{\operatorname{tr}(FO)-d^{-1}\operatorname{tr}(O)}{d^2-1}\)
证明提示：将矩写成置换算子的线性组合，然后对左右两边取迹，就可以解出系数。

特别地，纯态的二阶矩为：

纯态的二阶矩
\(\boxed{ M^{(2)}(|\psi\rangle\langle\psi|)=\frac{\mathbb{I}_2+ F}{d(d+1)} }\)
其中 \(|\psi\rangle \in \mathcal{H}^{\otimes 2}\) 。
证明提示：直接根据公式计算即可。
实际上，纯态的 t 阶矩是所有 t 阶置换群的置换算子的等权线性组合。

最后，我们不加证明地指出，Clifford 群上的均匀分布构成一个 3-design。并且，一个 (t+1)-design 也是一个 t-design。因此 Clifford 群上的均匀分布也是一个 2-design。这些事实我们在下节会用到。

3.4 测量信道

有了 Haar measure 和 t-design 的铺垫之后，我们这节就可以来证明测量信道可以写成以下解析形式了：

\[\begin{aligned} \mathcal{M}(\rho)&:=\mathbb{E}_{U\sim \nu}\left[\sum_{b=1}^d \langle b | U \rho U^\dagger | b\rangle (U^\dagger |b\rangle\langle b| U^\dagger)\right] \\ &= \frac{\operatorname{tr}(\rho) \mathbb{I} + \rho}{d+1} \end{aligned}\]

证明：
根据偏迹的性质，有
\(\begin{aligned} \mathcal{M}(\rho)&:=\mathbb{E}_{U\sim \nu}\left[\sum_{b=1}^d \langle b | U \rho U^\dagger | b\rangle (U^\dagger |b\rangle\langle b| U^\dagger)\right] \\ &= \sum_{b=1}^d \operatorname{tr}_1\left( (\rho \otimes \mathbb{I}) \mathbb{E}_{U\sim \nu} [U^{\otimes 2} |b\rangle\langle b|^{\otimes 2}U^{\dagger\otimes 2}]\right) \end{aligned}\)
由于 \(\nu\) 是一个 2-design，所以它的二阶矩与 Haar 测度的二阶矩相同：
\(\begin{aligned} \mathbb{E}_{U\sim \nu} [U^{\otimes 2} |b\rangle\langle b|^{\otimes 2}U^{\dagger\otimes 2}] &= \frac{\mathbb{I} \otimes \mathbb{I}+ F}{d(d+1)} \end{aligned}\)
于是
\(\begin{aligned} \mathcal{M}(\rho)&= \sum_{b=1}^d \operatorname{tr}_1\left( (\rho \otimes \mathbb{I}) \frac{\mathbb{I} \otimes\ \mathbb{I}+ F}{d(d+1)}\right) \\ &= \frac{d}{d(d+1)}\operatorname{tr}_1\left( (\rho \otimes \mathbb{I}) + F(\rho \otimes \mathbb{I})\right) \\ &= \frac{1}{d+1}(\operatorname{tr}(\rho)\mathbb{I}+ \rho) \end{aligned}\)
证毕。

3.5 估计量方差的上界

我们在上一节证明了

\[\boxed{ \mathcal{M}(\rho)= \frac{\rho + \operatorname{tr}[\rho] \mathbb{I}}{d+1} }\]

也就是证明了

\[\boxed{ \begin{aligned} \hat{\rho}&=\mathcal{M}^{-1}(U|b\rangle\langle b| U^\dagger)\\ &=(d+1) U|b\rangle\langle b| U^\dagger - \mathbb{I} \end{aligned} }\]

是无偏的。换句话说，算符的估计量 \(\hat{o_i}:= \operatorname{tr}(O_i \hat{\rho})\) 的期望值等于真实值 \(\mathbb{E}[\hat{o}_i] = \operatorname{tr}[\rho O_i]\) 。

然而仅此还不够，我们没有给出估计量的方差的上界，从而求出样本复杂度。

我们接下来证明估计量的方差的上界为 \(\boxed{\operatorname{Var}(\hat{o}_i) \le 3 \operatorname{tr}(O_i^2)}\) 。

估计量的方差的上界
估计量的方差为：
\(\operatorname{Var}(\hat{o_i})=\mathbb{E}[\hat{o}_i^2]-\mathbb{E}[\hat{o}_i]^2\)
其中
\(\mathbb{E}\left(\hat{\sigma}_i^2\right):=\sum_{b=1}^d \underset{U \sim \nu}{\mathbb{E}}\left[\langle b| U \rho U^{\dagger}|b\rangle \operatorname{tr}\left(O_i \mathcal{M}^{-1}\left(U^{\dagger}|b\rangle\langle b| U\right)\right)^2\right]\)
首先，注意到
\(\operatorname{tr}(A \mathcal{M}(B))=\sum_{b=1}^d \underset{U \sim \nu}{\mathbb{E}}\left[\langle b| U B U^{\dagger}|b\rangle\langle b| U A U^{\dagger}|b\rangle\right]=\operatorname{tr}(\mathcal{M}(A) B)\)
所以 \(\operatorname{tr}(A \mathcal{M}^{-1}(B))=\operatorname{tr}(\mathcal{M}^{-1}(A) B)\)
所以
\(\begin{aligned} \mathbb{E}\left(\hat{o}_i^2\right) & =\sum_{b=1}^d \underset{U \sim \nu}{\mathbb{E}}\left[\langle b| U \rho U^{\dagger}|b\rangle \operatorname{tr}\left(\mathcal{M}^{-1}\left(O_i\right) U^{\dagger}|b\rangle\langle b| U\right)^2\right] \\ & =\sum_{b=1}^d \underset{U \sim \nu}{\mathbb{E}}\left[\operatorname{tr}\left(\rho U^{\dagger}|b\rangle\langle b| U\right) \operatorname{tr}\left(\mathcal{M}^{-1}\left(O_i\right) U^{\dagger}|b\rangle\langle b| U\right)^2\right] \\ & =\operatorname{tr}\left(\left(\rho \otimes \mathcal{M}^{-1}\left(O_i\right) \otimes \mathcal{M}^{-1}\left(O_i\right)\right)\left(\sum_{b=1}^d \underset{U \sim \nu}{\mathbb{E}}\left[U^{\dagger \otimes 3}|b\rangle\left\langle b\right|^{\otimes 3} U^{\otimes 3}\right]\right)\right) \end{aligned}\)
其中最后一步用到了 \(\operatorname{tr}(A \otimes B) = \operatorname{tr}(A) \operatorname{tr}(B)\) 。
由于 \(\nu\) 是一个 3-design，所以
\(\begin{aligned} \underset{U \sim \nu}{\mathbb{E}}\left[U^{\dagger \otimes 3}|b\rangle\left\langle b\right|^{\otimes 3} U^{\otimes 3}\right] = \frac{1}{d(d+1)(d+1)}\underset{\pi \in S_3}{\sum}V_d(\pi) \end{aligned}\)
于是
\(\begin{aligned} &\operatorname{tr}\left(\left(\rho \otimes \mathcal{M}^{-1}\left(O_i\right) \otimes \mathcal{M}^{-1}\left(O_i\right)\right)\left(\sum_{\pi \in S_3} V_d(\pi)\right)\right) \\ & =\operatorname{tr}(\rho) \operatorname{tr}\left(\mathcal{M}^{-1}\left(O_i\right)\right) \operatorname{tr}\left(\mathcal{M}^{-1}\left(O_i\right)\right)+\operatorname{tr}(\rho) \operatorname{tr}\left(\mathcal{M}^{-1}\left(O_i\right)^2\right)\\ & \quad+\operatorname{tr}\left(\rho \mathcal{M}^{-1}\left(O_i\right)\right) \operatorname{tr}\left(\mathcal{M}^{-1}\left(O_i\right)\right) +\operatorname{tr}\left(\rho \mathcal{M}^{-1}\left(O_i\right)^2\right)\\ & \quad+\operatorname{tr}\left(\rho \mathcal{M}^{-1}\left(O_i\right)^2\right)+\operatorname{tr}\left(\rho \mathcal{M}^{-1}\left(O_i\right)\right) \operatorname{tr}\left(\mathcal{M}^{-1}\left(O_i\right)\right) \end{aligned}\) （*）
现在我们要用一个技巧：方差 \(\operatorname{Var}\left(\hat{o}_i\right)=\mathbb{E}\left[\left(\hat{o}_i-\operatorname{Tr}\left(O_i \rho\right)\right)^2\right]\) 只取决于 \(O_i\) 的无迹部分 \(O_i^{(0)} := O_i - \operatorname{tr}(O_i) \frac{\mathbb{I}}{d}\) 。这是因为
\(\hat{o}_i-\operatorname{Tr}\left(O_i \rho\right)=\operatorname{Tr}\left(O_i \hat{\rho}\right)-\operatorname{Tr}\left(O_i \rho\right)=\operatorname{Tr}\left(O_i^{(0)} \hat{\rho}\right)-\operatorname{Tr}\left(O_i^{(0)} \rho\right)\)
注意到 \(\mathcal{M}\) 是保迹的。
所以可以把方差的表达式中将所有 \(O_i\) 换成 \(O_i^{(0)}\) ：
\(\begin{aligned} & \operatorname{tr}\left(\left(\rho \otimes \mathcal{M}^{-1}\left(O_i^{(0)}\right) \otimes \mathcal{M}^{-1}\left(O_i^{(0)}\right)\right)\left(\sum_{\pi \in S_3} V_d(\pi)\right)\right) \\ & =0+\operatorname{tr}(\rho) \operatorname{tr}\left(\mathcal{M}^{-1}\left(O_i^{(0)}\right)^2\right)+0+\operatorname{tr}\left(\rho \mathcal{M}^{-1}\left(O_i^{(0)}\right)^2\right)+\operatorname{tr}\left(\rho \mathcal{M}^{-1}\left(O_i^{(0)}\right)^2\right)+0 \\ & =(d+1)^2 \operatorname{tr}\left(O_i^{(0) 2}\right)+2(d+1)^2 \operatorname{tr}\left(\rho O_i^{(0) 2}\right) \end{aligned}\)
于是
\(\begin{aligned} \operatorname{Var}\left(\hat{o}_i\right) & =\frac{(d+1)^2}{(d+1)(d+2)}\left(\operatorname{tr}\left(O_i^{(0) 2}\right)+2 \operatorname{tr}\left(\rho O_i^{(0) 2}\right)\right)-\operatorname{tr}\left(O_i^{(0)} \rho\right)^2 \\ & \leq \operatorname{tr}\left(O_i^{(0) 2}\right)+2 \operatorname{tr}\left(\rho O_i^{(0) 2}\right) \\ & \leq 3 \operatorname{tr}\left(O_i^{(0) 2}\right) \\ & \leq 3 \operatorname{tr}\left( O_i^2\right) \end{aligned}\)
证毕。

3.6 样本复杂度

在第二节中，我们使用了 Hoeffding 不等式给出样本复杂度的宽松上界。这里，我们使用平均数中位数估计（Median of means estimation）来给出样本复杂度的宽松上界。

平均数中位数估计（Median of means estimation）
给定 \(N\) 个独立同分布随机变量 \(X_i,\,i=1,...,N\) ，期望值为 \(\mu\) ，方差为 \(\sigma^2\) 。将它们分成 \(k\) 组，每组 \(m=N/k\) 个随机变量。那么其中一组的平均值 \(\hat{\mu}_j = \sum_{i=j}^{j+m-1} X_i\) 的方差为 \(\sigma^2/m\) 。根据 Chebyshev 不等式，有：
\(\begin{aligned} P(|\hat{\mu}_j - \mu| > \epsilon ) \le \frac{\sigma^2}{m \epsilon^2} \end{aligned}\)
令右边等于 \(p\) ，那么 \(m= \sigma^2/(p\epsilon^2)\) 。
定义随机变量：
\(Z_j = \begin{cases} 1,& |\hat{\mu}_j - \mu| > \epsilon \\ 0,& |\hat{\mu}_j - \mu| \le \epsilon \end{cases}\)
由于我们最终取 \(\hat{\mu}_1,...,\hat{\mu}_k\) 的中位数，我们希望一半以上的 \(\hat{\mu}_j\) 误差大于 \(\epsilon\) 的概率 \(P\left(\sum_{j=1}^k Z_j > \frac{k}{2}\right)\) 足够小。
记 \(S=\sum_{j=1}^k Z_j\) ，根据 Hoeffding 不等式有：
\(P(S-\mathbb{E}(S)>t)\le \exp\left(-\frac{2t^2}{k}\right)\)
其中 \(\mathbb{E}(S) \le kp\) 。令 \(t = k/2 - kp\) ，于是：
\(P\left(S>\frac{k}{2}\right) \le P(S-\mathbb{E}(S)>t)\le \exp\left(-2k\left(\frac{1}{2}-p\right)^2\right)\)
不妨令 \(p = 1/4\) ，于是
\(P\left(\sum_{j=1}^k Z_j > \frac{k}{2}\right) \le \exp\left( - \frac{k}{8}\right)\)
令右边等于 \(\delta\) 得 \(k =8 \log (1/\delta)\) 。
又因为 \(m=\sigma^2/(p\epsilon^2) =4\sigma^2/\epsilon^2\) ，所以
\(\boxed{ N = km =32 \sigma^2 \log(1/\delta)/\epsilon^2 }\)
这就是以低于失败率 \(\delta\) 在误差 \(\epsilon\) 内估计 \(\hat{\mu}\) 所需要的样本数。

现在把 Median of means 用到我们的问题中。 \(X_i:= \hat{o}_i\) 的方差 \(\sigma^2\) 满足 \(\sigma^2 \le 3 \operatorname{tr}(O_i^2) = 3||O_i||^2\) ，代入得

\[N = 96 ||O_i||^2\log(1/\delta)/\epsilon^2\]

现在我们要同时估计 \(M\) 个 \(\hat{o}_i\) ，即 \(\hat{o}_1,...,\hat{o}_M\) 。

在运用 Hoeffding 不等式的时候：

\[P(S-\mathbb{E}(S)>t)\le \exp\left(-\frac{2t^2}{k}\right)\]

我们可以选取 \(M\) 个 \(S_i\) ，即 \(S_1, ..., S_M\) ，并取 union bound：

\[P(S_i-\mathbb{E}(S_i)>t,\ \exists S_i \in\{S_1,...,S_M\})\le M\exp\left(-\frac{2t^2}{k}\right)\]

对数复杂度的关键就在这里：取 union bound 的时候， \(M\) 出现在指数的外面。因此反过来求 \(N\) 的时候， \(M\) 会出现在对数里面。

因此，我们可以证明样本复杂度为：

\[\boxed{ N = O\left( \log(M/\delta)\max_i||O_i||^2 /\epsilon^2 \right) }\]

3.7 泡利测量

前面介绍的一切推导都基于 Clifford 测量。但 Clifford 测量是一种全局测量，需要将各个 qubit 进行纠缠门操作，再在计算基下测量。

实践中更常用的是局部测量，即对各个 qubit 分别进行单比特门操作，然后在计算基下测量。通常这些门被选取为单比特的 Clifford 群，它们能够实现泡利基（也就是 \(X, Y, Z\) ）下的测量。在这种情况下，样本复杂度还取决于待测算符的 locality。这是很显然的：如果待测算符是高度纠缠的，那么你很难指望很少的局域测量能给出纠缠的信息。

(未完待续)

3.8 去随机化（Derandomization）

经典阴影与传统的 FST 非常不同。在传统的 FST 中，我们在每个测量基下都测量一样多的样本，这样能够保证误差在一定程度上更加均匀。而在经典阴影中，由于测量基是随机选取的，所以不同测量基下的样本数也不同。

于是问题由之而来：与随机选基相比，设定不同测量基下的样本数相同是否更好？这就是所谓的去随机化（Derandomization）。

(未完待续)

参考

1. ^Cotler, J. & Wilczek, F. Quantum Overlapping Tomography. Phys. Rev. Lett. 124, 100401 (2020).
2. ^Acharya, Jayadev, et al. “Pauli measurements are not optimal for single-copy tomography.” Proceedings of the 57th Annual ACM Symposium on Theory of Computing. 2025.
3. ^Nayak, A., & Lowe, A. (2025). Lower bounds for learning quantum states with single-copy measurements. ACM Transactions on Computation Theory.
4. ^O’Donnell, R. & Wright, J. Efficient quantum tomography. in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing 899–912 (ACM, Cambridge MA USA, 2016). doi:10.1145/2897518.2897544.
5. ^Haah, J., Harrow, A. W., Ji, Z., Wu, X. & Yu, N. Sample-optimal tomography of quantum states. in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing 913–925 (ACM, Cambridge MA USA, 2016). doi:10.1145/2897518.2897585.
6. ^Huang, H.-Y., Kueng, R. & Preskill, J. Predicting many properties of a quantum system from very few measurements. Nat. Phys. 16, 1050–1057 (2020).
7. ^Aaronson, Scott. “Shadow tomography of quantum states.” Proceedings of the 50th annual ACM SIGACT symposium on theory of computing. 2018.