# 量子态层析详解：从指数方法到 Shadow Tomography

量子态层析（Quantum State Tomography, QST）是量子信息科学中最基础的实验技术之一：我们通过对量子态的大量测量，重建其完整描述——密度矩阵 $\rho$。本文系统介绍从指数级标准层析到多项式级 Shadow Tomography 的方法演进；对每个关键复杂度结论，我们都从基本不等式出发逐步推导，并说明各方法的适用场景与局限。

## 问题背景

### 量子态的完整描述

$n$ 量子比特系统的状态由密度矩阵 $\rho \in \mathbb{C}^{N \times N}$（$N = 2^n$）完全描述。$\rho$ 必须满足厄米性、半正定性与迹为一。我们先计算独立实参数的个数：$N \times N$ 厄米矩阵有 $N^2$ 个实自由度（对角 $N$ 个实数、非对角 $N(N-1)/2$ 个复数），迹为一的约束消去 $1$ 个，故

$$\dim = N^2 - 1 = 4^n - 1 .$$

**目标**：我们通过测量制备好的量子态副本，估计 $\rho$ 的全部参数。

### 测量的量子力学限制

量子测量会扰动态：测量 $\rho$ 在基矢 $|b\rangle$ 上的投影 $P_b = |b\rangle\langle b|$ 得到结果 $b$ 的概率为 $\mathrm{tr}(P_b\rho)$，且测量后态坍缩为 $P_b\rho P_b/\mathrm{tr}(P_b\rho)$。因此每次测量只能给出 $O(n)$ 比特的结果（一个比特串），而完整描述 $\rho$ 需要 $4^n$ 个精度为 $O(\log(1/\varepsilon))$ 比特的实参数。这一信息量的悬殊差距是层析复杂度的根源：完整重建 $\rho$ 需要 $\Omega(N^2)$ 份副本，我们在方法一中看到标准方案确实达到（并略超）这一量级。

## 方法一：标准层析（指数方法）

### Pauli 层析

**基本思想**：我们把 $\rho$ 展开为泡利基。$n$ 比特泡利算符集合为 $\{I, X, Y, Z\}^{\otimes n}$，共有 $4^n$ 个元素，且在迹内积下两两正交：

$$\mathrm{tr}(P Q) = N\,\delta_{PQ}, \qquad P, Q \in \{I, X, Y, Z\}^{\otimes n}.$$

**展开公式的推导**：设 $\rho = \sum_Q c_Q Q$，两边左乘 $P$ 并取迹，得 $\mathrm{tr}(P\rho) = \sum_Q c_Q\,\mathrm{tr}(PQ) = N c_P$，因此 $c_P = \mathrm{tr}(P\rho)/N$，即

$$\rho = \frac{1}{N} \sum_{P \in \{I, X, Y, Z\}^{\otimes n}} \mathrm{tr}(P\rho)\, P .$$

于是估计全部 $\mathrm{tr}(P\rho)$ 即可重建 $\rho$。

**测量基的选择**：对每个泡利字符串 $P = P_1 \otimes \cdots \otimes P_n$，我们先施加相应的基变换，再在计算基测量。单个比特的变换为：$Z$ 基不需要变换（恒等 $I$）；$X$ 基施加 $H$（因为 $H|+\rangle = |0\rangle$，$H|-\rangle = |1\rangle$）；$Y$ 基施加 $HS^\dagger$。我们验证后者：$Y$ 的本征态为 $|\pm i\rangle = (|0\rangle \pm i|1\rangle)/\sqrt 2$，由 $S^\dagger = \mathrm{diag}(1, -i)$ 得 $S^\dagger|{+i}\rangle = (|0\rangle + i(-i)|1\rangle)/\sqrt2 = (|0\rangle+|1\rangle)/\sqrt2 = |+\rangle$，再经 $H$ 映到 $|0\rangle$；同理 $HS^\dagger|-i\rangle = |1\rangle$。

**期望值的读出**：测量得到比特串 $b = b_1\cdots b_n$ 后，我们构造随机变量

$$X(b) = \prod_{i=1}^{n} (-1)^{b_i} \in \{+1, -1\}.$$

我们证明 $\mathbb{E}[X] = \mathrm{tr}(P\rho)$：记 $U = \otimes_i U_i$ 为上述基变换，测量结果 $b$ 的概率为 $\mathrm{tr}(\rho\, U^\dagger |b\rangle\langle b|\, U)$，于是

$$\mathbb{E}[X] = \sum_b \left(\prod_i (-1)^{b_i}\right) \mathrm{tr}\!\left(\rho\, U^\dagger |b\rangle\langle b| U\right) = \mathrm{tr}\!\left(\rho\, U^\dagger \left[\sum_b \prod_i (-1)^{b_i} |b\rangle\langle b|\right] U\right) = \mathrm{tr}(\rho\, P),$$

最后一步用了 $U^\dagger\left[\otimes_i (-1)^{b_i}|b_i\rangle\langle b_i|\right]U = \otimes_i P_i = P$（$U_i$ 把 $P_i$ 的本征态映到计算基）。

**泡利字符串总数**：非平凡的泡利字符串共 $4^n - 1$ 个（去掉 $I^{\otimes n}$，它对应恒等式 $\mathrm{tr}(\rho) = 1$）。

**每个 $\mathrm{tr}(P\rho)$ 的测量次数**：由下节的霍夫丁界，达到精度 $\varepsilon$ 需要 $O(1/\varepsilon^2)$ 次重复测量。

**总测量次数**：

$$M = O\!\left(\frac{4^n}{\varepsilon^2}\right) = O\!\left(\frac{N^2}{\varepsilon^2}\right).$$

这是指数级的：$n = 50$ 时 $4^{50} \approx 10^{30}$，完全不可行。

### 线性反演

**公式推导**：我们把测得的频率 $\hat f_P$（对 $\mathrm{tr}(P\rho)$ 的估计）直接代入泡利展开式：

$$\hat\rho_{\mathrm{lin}} = \frac{1}{N}\left(I + \sum_{P \ne I} \hat f_P\, P\right).$$

该估计是无偏的（每个 $\hat f_P$ 无偏），且由 $4^n - 1$ 个频率唯一决定 $\rho$——这正是泡利基层析"层析完备"的含义。

**物理性问题**：$\hat\rho_{\mathrm{lin}}$ 一般不是合法密度矩阵，因为半正定性是 $4^n$ 个非线性约束（所有特征值非负），无偏的线性估计无法保证它们。我们给出一个单比特的反例：设统计涨落使得 $\hat f_X = 0.9$、$\hat f_Y = 0.9$、$\hat f_Z = 0$，则

$$\hat\rho_{\mathrm{lin}} = \frac{1}{2}\bigl(I + 0.9X + 0.9Y\bigr),$$

其 Bloch 向量长度为 $\sqrt{0.81 + 0.81 + 0} = \sqrt{1.62} \approx 1.27 > 1$，故 $\hat\rho_{\mathrm{lin}}$ 有负特征值（$\lambda = (1 \pm 1.27)/2$，其中一个约为 $-0.14$）。线性反演的负特征值问题是层析中的著名现象，也是引入极大似然估计的动机。

### 极大似然层析（MLE）

给定测量数据 $\{(P_i, m_i)\}$（对泡利字符串 $P_i$ 独立测量，结果 $\pm 1$ 各出现 $m_i^{+}, m_i^{-}$ 次），我们在合法密度矩阵的凸集上最大化似然函数：

$$\mathcal{L}(\rho) = \prod_i \left[\frac{1 + \mathrm{tr}(P_i\rho)}{2}\right]^{m_i^{+}} \left[\frac{1 - \mathrm{tr}(P_i\rho)}{2}\right]^{m_i^{-}}, \qquad \rho \succeq 0,\ \ \mathrm{tr}(\rho) = 1 .$$

取对数便于分析：

$$\ell(\rho) = \sum_i \Bigl[ m_i^{+} \ln\tfrac{1 + \mathrm{tr}(P_i\rho)}{2} + m_i^{-} \ln\tfrac{1 - \mathrm{tr}(P_i\rho)}{2} \Bigr].$$

**凸性**：$\ln$ 是凹函数且每个 $\mathrm{tr}(P_i\rho)$ 是 $\rho$ 的线性函数，故 $\ell(\rho)$ 是 $\rho$ 的凹函数；约束集（半正定、迹一）是凸集。因此极大似然层析是一个凸优化问题，其最优点全局存在。

**驻点条件**：引入拉格朗日乘子处理迹约束，对 $\ell$ 求梯度并令其为零，得

$$R(\rho^\ast) \;=\; \sum_i \frac{m_i^{+} - m_i^{-}}{\mathrm{tr}(P_i \rho^\ast)}\, P_i \;\propto\; I ,$$

即在最优点处"加权观测算符" $R$ 必须与单位算符成比例。常用的 R$\rho$R 类不动点迭代正是利用该条件：交替更新 $\rho_{k+1} \propto R(\rho_k)^{-1/2} \rho_k R(\rho_k)^{-1/2}$，每步使 $\ell$ 单调不减并收敛到 MLE（其收敛性分析超出本文范围，此处作为数值方案陈述）。

MLE 的优点是保证输出合法的密度矩阵（半正定、迹一），缺点是凸优化在 $4^n$ 维空间中求解代价高，且似然函数对频率为零的事件需要正则化。

### 采样复杂度：从霍夫丁界出发的推导

我们补全 $O(1/\varepsilon^2)$ 的推导。固定一个泡利字符串 $P$，单次测量的随机变量 $X \in \{-1, +1\}$ 满足 $\mathbb{E}[X] = \mathrm{tr}(P\rho) =: \mu$。取 $m$ 次独立重复的均值 $\bar X$。

**霍夫丁不等式**：若 $X_1, \ldots, X_m$ 独立、取值于 $[a, b]$，则

$$\Pr\bigl[\,\lvert \bar X - \mu \rvert \ge \varepsilon\,\bigr] \;\le\; 2 \exp\!\left(-\frac{2 m \varepsilon^2}{(b-a)^2}\right).$$

代入 $a = -1, b = 1$ 得 $(b-a)^2 = 4$，故

$$\Pr\bigl[\,\lvert \bar X - \mu \rvert \ge \varepsilon\,\bigr] \;\le\; 2\, e^{-m\varepsilon^2/2}.$$

令右边等于失败概率 $\delta$，解出

$$m \;=\; \frac{2 \ln(2/\delta)}{\varepsilon^2} \;=\; O\!\left(\frac{\log(1/\delta)}{\varepsilon^2}\right).$$

这就是单个泡利期望值的 $O(\varepsilon^{-2})$ 采样复杂度。（用切尔诺夫界可得到相同的指数标度，霍夫丁界给出的是自洽的显式常数。）

**对所有泡利字符串取联合界**：要让全部 $4^n - 1$ 个估计同时达到精度 $\varepsilon$、总失败概率至多 $\delta$，我们对每个字符串分配失败概率 $\delta' = \delta / 4^n$，于是

$$m \;=\; \frac{2\ln(2 \cdot 4^n/\delta)}{\varepsilon^2} \;=\; O\!\left(\frac{n + \log(1/\delta)}{\varepsilon^2}\right).$$

总副本数为 $(4^n - 1) \cdot m = O\!\bigl(4^n (n + \log(1/\delta))/\varepsilon^2\bigr)$，通常简写为 $O(4^n/\varepsilon^2)$（把对数因子吸收进大 $O$）。

**范数的区分**：上述 $\varepsilon$ 是每个泡利系数的精度。若我们要求 Frobenius 范数精度 $\|\hat\rho - \rho\|_F \le \varepsilon$，需要更细的分配。由泡利展开与正交性，

$$\hat\rho - \rho = \frac{1}{N}\sum_P \Delta_P P \quad\Longrightarrow\quad \|\hat\rho - \rho\|_F^2 = \frac{1}{N^2}\, N \sum_P \Delta_P^2 = \frac{1}{N}\sum_P \Delta_P^2,$$

其中 $\Delta_P$ 是 $\mathrm{tr}(P\rho)$ 的误差。要使左边 $\le \varepsilon^2$，需 $\sum_P \Delta_P^2 \le N\varepsilon^2$；在 $4^n$ 个系数上均匀分配即要求每个 $\Delta_P \le \varepsilon\sqrt{N}/2^n = \varepsilon \cdot 2^{-n/2}$，从而每个泡利串需要 $O(2^n/\varepsilon^2)$ 次测量，总计 $O(N^3/\varepsilon^2)$。作为对照，Haah 等人证明了信息论最优的完整层析采样复杂度为 $\Theta(N^2/\varepsilon^2)$——朴素逐泡利方案距最优有 $N$ 因子差距，差距来源于信息量的重复利用。

### 复杂度总结

| 方法 | 测量次数 | 经典后处理 | 量子比特 |
|------|---------|-----------|---------|
| Pauli 线性反演 | $O(4^n/\varepsilon^2)$ | $O(4^n)$ | $n$ |
| MLE | $O(4^n/\varepsilon^2)$ | $O(N^6)$（凸优化迭代） | $n$ |
| 信息论最优 | $\Theta(N^2/\varepsilon^2)$ | — | $n$ |

## 方法二：$\ell_\infty$ 层析（矩阵元精度）

### 动机

标准层析估计所有 $4^n$ 个泡利系数，信息量极大；但许多应用只需要 $\rho$ 的**部分性质**（如若干矩阵元、保真度、纯度、纠缠度量）。$\ell_\infty$ 层析（Infinity Norm Tomography）专注于逐矩阵元的精度，即在最大元素偏差意义下逼近 $\rho$。

### 数学定义

$\ell_\infty$ 层析的目标是找到 $\hat\rho$ 满足：

$$\|\rho - \hat\rho\|_{\max} = \max_{i,j} \lvert \rho_{ij} - \hat\rho_{ij} \rvert \le \varepsilon .$$

（其中 $\|\cdot\|_{\max}$ 是矩阵元素的逐个最大绝对值，不是算符范数；$\ell_\infty$ 层析因此依赖基的选择。）

### 实现方法与复杂度推导

**对角元（可廉价并行估计）**。对角元就是计算基测量的输出分布：单次测量得到一个样本 $j \sim \rho_{jj}$。要把全部 $N = 2^n$ 个对角元同时估计到精度 $\varepsilon$，我们对频率估计用霍夫丁界并对 $N$ 个结果取联合界：

$$m_{\mathrm{diag}} = \frac{\ln(2N/\delta)}{2\varepsilon^2} = O\!\left(\frac{\log(N/\delta)}{\varepsilon^2}\right),$$

即对角元只需要对数多个副本量级，远少于完整层析。

**单个非对角元 $\rho_{xy}$（$x \ne y$）**。我们构造两个可观测量的测量。令

$$O = |x\rangle\langle y| + |y\rangle\langle x|, \qquad O' = i\bigl(|x\rangle\langle y| - |y\rangle\langle x|\bigr),$$

两者在二维子空间 $\mathrm{span}\{|x\rangle, |y\rangle\}$ 上分别同构于 $\sigma_x$ 与 $\sigma_y$（本征值 $\pm 1$），在正交补上为零，因此都可以通过一个 $O(n)$ 深度的多控电路映射到单比特测量。计算迹：

$$\mathrm{tr}(O\rho) = \langle y|\rho|x\rangle + \langle x|\rho|y\rangle = \rho_{xy}^{\ast} + \rho_{xy} = 2\,\mathrm{Re}\,\rho_{xy},$$
$$\mathrm{tr}(O'\rho) = i\bigl(\rho_{xy}^{\ast} - \rho_{xy}\bigr) = 2\,\mathrm{Im}\,\rho_{xy},$$

（第二式用了 $z^{\ast} - z = -2i\,\mathrm{Im}\,z$。）于是 $\rho_{xy} = \tfrac{1}{2}\mathrm{tr}(O\rho) + \tfrac{i}{2}\mathrm{tr}(O'\rho)$，每个观测量由霍夫丁界需要 $O(\varepsilon^{-2})$ 次测量。估计 $k$ 个指定矩阵元因此共需 $O(k/\varepsilon^2)$ 次测量。

**全部矩阵元**。若要求所有 $N^2$ 个矩阵元都达到精度 $\varepsilon$，逐个测量的方案退化为 $O(4^n/\varepsilon^2)$，与完整层析同阶。利用方法四的随机基测量可以同时服务所有矩阵元：我们在方法四中推导出，矩阵元估计的单副本方差至多为 $(3/2)^n$，从而全部矩阵元的 $\ell_\infty$ 精度层析可以用

$$M = O\!\left(\frac{n \,(3/2)^n}{\varepsilon^2}\right)$$

份副本完成（对数因子来自对 $N^2$ 个元素取联合界）。这一结果由本文的方差计算直接推出，优于朴素方案的 $4^n$ 因子；我们不再沿用早期版本中未经推导的 $O(n 2^n/\varepsilon^2)$ 表述。

### 限制

- $\ell_\infty$（逐元素）范数不是酉不变的，依赖于基的选择；
- 对角元便宜、非对角元昂贵，两类元素的采样代价极不对称；
- 逐元素精度不能直接给出保真度等酉不变量的精度（保真度对谱敏感）。

## 方法三：稀疏层析

### 动机

许多物理相关的量子态是**稀疏的**——在某个基下，大部分元素为零或可忽略：

- 低纠缠态（矩阵乘积态，MPS）；
- 对角密度矩阵（经典概率混合）；
- 局域关联态（如满足面积律的关联函数）。

### 定义

密度矩阵 $\rho$ 是 $s$-稀疏的：在计算基下至多有 $s$ 个非零元素。

**目标**：以 $O(s\cdot \mathrm{poly}(n, 1/\varepsilon))$ 次测量重建 $\rho$。

### 稀疏层析方法

**方法一：直接元素估计**。对每个可能非零的 $(i, j)$，我们用方法二的单矩阵元方案，即 $O(\varepsilon^{-2})$ 次测量估计 $\rho_{ij}$。其困难在于：需要预先知道哪些 $(i, j)$ 非零——这本身需要探索性搜索。

**方法二：泡利基下的稀疏性**。若 $\rho$ 在泡利基下有 $s$ 个非零系数（$s = \mathrm{poly}(n)$），则我们只需测量 $s$ 个泡利字符串。推导：$\rho = \frac{1}{N}\sum_P \mathrm{tr}(P\rho)P$ 中只有 $s$ 项非零时，估计这 $s$ 个期望值即可；由霍夫丁界与对 $s$ 个估计的联合界，每个泡利串需要

$$m = \frac{2\ln(2s/\delta)}{\varepsilon^2}$$

次测量，总测量次数为

$$M = O\!\left(\frac{s\log s}{\varepsilon^2}\right).$$

**方法三：压缩感知层析**。我们利用 $\rho$ 的低秩或稀疏性，通过随机测量（如随机泡利测量）和压缩感知重构算法，以 $O(s\cdot\mathrm{poly}(n)/\varepsilon^2)$ 次测量重建 $\rho$（Gross 等人 2010 证明了低秩 + 纯态情形的最优性）。

**数学基础**：若 $\rho$ 在某个正交基下是 $s$-稀疏的，则 $O(s\log N)$ 次随机线性测量在 RIP（Restricted Isometry Property，受限等距性质）条件下足以唯一确定 $\rho$——这与经典压缩感知的稀疏恢复定理同构，$\log N$ 因子来自"命中支撑"的耦合收集（coupon-collector）效应。

### 复杂度对比

| 方法 | 测量次数 | 适用条件 |
|------|---------|---------|
| 标准层析 | $O(4^n/\varepsilon^2)$ | 通用 |
| $\ell_\infty$ 层析 | $O(n(3/2)^n/\varepsilon^2)$ | 全矩阵元精度 |
| 稀疏层析 | $O(s\cdot\mathrm{poly}(n)/\varepsilon^2)$ | $s$-稀疏态 |
| Shadow Tomography | $O(3^k \log M/\varepsilon^2)$ | $M$ 个局域可观测量 |

## 方法四：Shadow Tomography（影子层析）

### 突破性思想

Shadow Tomography 由 Scott Aaronson 于 2018 年提出，由 Huang、Kueng、Preskill 于 2020 年发展为实用方法（经典影子，classical shadow）。它不重建完整的 $\rho$，而是直接估计 $\rho$ 的 $M$ 个函数值 $\mathrm{tr}(O_1\rho), \ldots, \mathrm{tr}(O_M\rho)$，以 $O(\log M)$ 的副本数达到给定精度。

**问题陈述**：给定 $\rho$ 的制备访问，以及 $M$ 个可观测量 $O_1, \ldots, O_M$（$\|O_k\| \le 1$），我们要求估计所有 $\mathrm{tr}(O_k\rho)$ 到精度 $\varepsilon$。

**Aaronson 定理（2018）**：存在量子算法以 $O(\log M \cdot \log^4 N / \varepsilon^5)$ 份副本估计所有 $\mathrm{tr}(O_k\rho)$。

**关键改进**：$\log M$ 因子——即使 $M = 2^{2^n}$（所有可能的可观测量），也只需 $O(n)$ 量级的对数因子。

### 随机测量 Shadow Tomography（实用版本）

Huang、Kueng、Preskill（2020）给出了更实用的方案：**随机泡利测量 + 经典后处理**。

**步骤**：

1. 我们对 $\rho$ 的每个副本，独立、均匀地为每个比特选取 $X$、$Y$、$Z$ 三个基之一，等价于施加 $U \in \{I, H, HS^\dagger\}^{\otimes n}$；
2. 在计算基测量，得到比特串 $b \in \{0,1\}^n$；
3. 计算单副本影子（classical shadow）$\hat\rho = \bigotimes_{i=1}^{n} \bigl(3\,U_i^\dagger|b_i\rangle\langle b_i|U_i - I\bigr)$；
4. 重复 $N_s$ 次，得到影子集合 $\{\hat\rho^{(1)}, \ldots, \hat\rho^{(N_s)}\}$；
5. 对任意可观测量 $O_k$，用均值估计 $\mathrm{tr}(O_k\rho) \approx \frac{1}{N_s}\sum_{t} \mathrm{tr}(O_k \hat\rho^{(t)})$。

**单比特情形的无偏性推导**。我们证明 $\mathbb{E}[\hat\rho] = \rho$。设 $\rho = \frac{1}{2}(I + xX + yY + zZ)$，测量基 $b \in \{X, Y, Z\}$ 等概率选取，结果为对应本征态 $|s_b\rangle$（$s = \pm 1$），影子为 $\hat\rho = 3|s_b\rangle\langle s_b| - I$。结果概率为 $\Pr(s \mid b) = \mathrm{tr}(\rho |s_b\rangle\langle s_b|) = \frac{1 + s\,r_b}{2}$，其中 $r_X = x$、$r_Y = y$、$r_Z = z$。对两个结果求和：

$$\sum_{s=\pm 1} \Pr(s\mid b)\,|s_b\rangle\langle s_b| = \frac{1}{2}\bigl(|+_b\rangle\langle+_b| + |-_b\rangle\langle-_b|\bigr) + \frac{r_b}{2}\bigl(|+_b\rangle\langle+_b| - |-_b\rangle\langle-_b|\bigr) = \frac{I}{2} + \frac{r_b}{2}\,\sigma_b .$$

于是

$$\mathbb{E}[\hat\rho] = \frac{1}{3}\sum_{b}\left[3\left(\frac{I}{2} + \frac{r_b}{2}\sigma_b\right) - I\right] = \frac{1}{3}\sum_b \left[\frac{I}{2} + \frac{3 r_b}{2}\sigma_b\right] = \frac{I}{2} + \frac{1}{2}(xX + yY + zZ) = \rho .$$

**多比特情形**。我们用信道语言推广：定义单比特"去极化到对角"的测量信道

$$\mathcal{M}(\rho) = \frac{1}{3}\sum_{b \in \{X,Y,Z\}} \sum_{s=\pm 1} \mathrm{tr}\bigl(\rho\,|s_b\rangle\langle s_b|\bigr)\,|s_b\rangle\langle s_b| ,$$

上面的计算表明 $\mathcal{M}(\rho) = \frac{I}{2} + \frac{1}{6}(xX + yY + zZ)$，其逆为 $\mathcal{M}^{-1}(A) = 3A - \mathrm{tr}(A)\, I$，影子即 $\hat\rho = \mathcal{M}^{-1}(|s_b\rangle\langle s_b|) = 3|s_b\rangle\langle s_b| - I$。由 $\mathcal{M}^{-1}$ 的线性，

$$\mathbb{E}[\hat\rho] = \mathcal{M}^{-1}\bigl(\mathbb{E}[\text{结果投影}] \bigr) = \mathcal{M}^{-1}\bigl(\mathcal{M}(\rho)\bigr) = \rho .$$

$n$ 比特情形测量信道为张量积 $\mathcal{M}^{\otimes n}$、逆为 $(\mathcal{M}^{-1})^{\otimes n}$，逐比特选取基正对应 $\bigotimes_i(3U_i^\dagger|b_i\rangle\langle b_i|U_i - I)$，无偏性由张量积的线性直接继承。

### 方差与样本复杂度

**单副本方差**。对权重为 $k$ 的泡利可观测量 $P$（在 $k$ 个比特上取 $X/Y/Z$、其余取 $I$），我们精确计算 $\mathrm{tr}(P\hat\rho)$ 的方差。由张量积结构，$\mathrm{tr}(P\hat\rho) = \prod_{i \in \mathrm{supp}(P)} \mathrm{tr}\bigl(P_i (3|b_i\rangle\langle b_i| - I)\bigr)$，且每个因子只在"该比特恰好测在 $P_i$ 的本征基"时非零（否则 $\langle b|P_i|b\rangle = 0$，因子为零）。因此在全部 $k$ 个支撑比特都测对基（概率 $3^{-k}$）时，$\mathrm{tr}(P\hat\rho) = 3^k \prod_i s_i$，其中 $s_i = \pm 1$；否则恰为零。于是

$$\mathbb{E}\bigl[(\mathrm{tr}(P\hat\rho))^2\bigr] = 3^{2k}\cdot 3^{-k}\cdot \mathbb{E}\Bigl[\prod_i s_i^2\Bigr] = 3^k,$$

（用了 $s_i^2 = 1$），而无偏性给出 $\mathbb{E}[\mathrm{tr}(P\hat\rho)] = \mathrm{tr}(P\rho)$，故

$$\mathrm{Var}\bigl[\mathrm{tr}(P\hat\rho)\bigr] = 3^k - \mathrm{tr}(P\rho)^2 \;\le\; 3^k .$$

**矩阵元方差**。我们把 $\rho_{xy} = \frac{1}{N}\sum_P \langle x|P|y\rangle\,\mathrm{tr}(P\hat\rho)$ 中的求和按"差异比特"（$x_i \ne y_i$，共 $k = |x \oplus y|$ 个）与"相同比特"（$n-k$ 个）分组：使 $\langle x|P|y\rangle \ne 0$ 的 $P$ 恰在差异比特上取 $X$ 或 $Y$、在相同比特上取 $I$ 或 $Z$。给定一次测量的基组态 $B$，差异比特部分只有唯一的 $F$（每个差异比特所选的基恰好指定该比特取 $X$ 还是 $Y$）能全部匹配，其贡献为 $3^k\prod_{i \in \text{diff}} s_i$，模长为 $3^k$；若任一差异比特测在 $Z$ 轴，则所有 $F$ 的因子为零、整个估计为零，该约束把二阶矩乘上因子 $(2/3)^k$。相同比特部分可以闭式求和（对 $I/Z$ 的二项式展开）：

$$\sum_{D \in \{I,Z\}^{\otimes(n-k)}} b_D\, \mathrm{tr}(D\hat\rho) \;=\; \prod_{j \in Z_B}\bigl(1 + 3\, b_j s_j\bigr),$$

其中 $Z_B$ 是测在 $Z$ 轴的相同比特集合、$b_js_j = \pm 1$，故每个因子的平方不超过 $16$。合并以上各点，并利用无偏性 $\mathbb{E}[|\hat\rho_{xy} - \rho_{xy}|^2] = \mathbb{E}[|\hat\rho_{xy}|^2] - |\rho_{xy}|^2 \le \mathbb{E}[|\hat\rho_{xy}|^2]$，得

$$\mathbb{E}\bigl[|\hat\rho_{xy}|^2\bigr] \;\le\; \frac{9^k}{N^2}\cdot\left(\frac{2}{3}\right)^{\!k}\cdot \mathbb{E}\bigl[16^{|Z_B|}\bigr] \;=\; \frac{6^k \,\cdot\, 6^{\,n-k}}{4^n} \;=\; \left(\frac{3}{2}\right)^{\!n},$$

其中用了 $\mathbb{E}[16^{|Z_B|}] = \bigl(\tfrac{2}{3} + \tfrac{16}{3}\bigr)^{n-k} = 6^{\,n-k}$（每个相同比特以 $1/3$ 概率测在 $Z$ 轴）。该界对一切 $x, y$ 一致成立。单比特数值检验：$n = 1$ 时对角元的二阶矩为 $1 + z/2 \le \tfrac32$、非对角元的二阶矩恰为 $\tfrac32$，与上式吻合。这正是方法二中 $\ell_\infty$ 复杂度 $O(n(3/2)^n/\varepsilon^2)$ 的来源。

**中位数均值（median of means）**。我们把 $N_s$ 个影子分成 $K$ 组、每组 $m$ 个；取组内均值的 $K$ 个值的中位数作为估计。由 Chebyshev 不等式，组均值偏离期望超过 $\varepsilon$ 的概率至多 $\mathrm{Var}/(m\varepsilon^2) \le \frac{1}{4}$（取 $m = 4\cdot 3^k/\varepsilon^2$）。中位数偏离要求至少一半的组失败；设 $K$ 为偶数，则失败组数服从二项分布 $\mathrm{Bin}(K, \tfrac14)$，其在 $j = K/2$ 处的单点概率为 $\binom{K}{K/2}\bigl(\tfrac{1}{4}\bigr)^{K/2}\bigl(\tfrac{3}{4}\bigr)^{K/2} \le 2^K \bigl(\tfrac{3}{16}\bigr)^{K/2} = \bigl(\tfrac{3}{4}\bigr)^{K/2}$，而对 $j \ge K/2$ 求和至多再乘一个线性因子（项数 $\le K/2 + 1$，且各点概率单调递减），故失败概率随 $K$ 指数衰减。对 $M$ 个可观测量取联合界，我们得到：

**定理（Huang, Kueng, Preskill, 2020）**：为使 $\max_k \lvert \mathrm{tr}(O_k\rho) - \widehat{\mathrm{tr}(O_k\rho)} \rvert \le \varepsilon$ 以概率 $1 - \delta$ 成立，所需副本数为

$$N_s = O\!\left(\frac{\log(M/\delta)}{\varepsilon^2}\cdot \max_k \mathrm{Var}\bigl[\mathrm{tr}(O_k\hat\rho)\bigr]\right).$$

对权重为 $k$ 的泡利可观测量，$\mathrm{Var} \le 3^k$，故

$$N_s = O\!\left(\frac{3^k \log(M/\delta)}{\varepsilon^2}\right).$$

我们特别指出：方差上界 $3^k$ 只对**固定权重**（局域）泡利算符是 $O(1)$；对满权重 $k = n$ 的泡利串，方差为 $3^n$，随机泡利影子并不免费给出全部泡利系数的精度。

**对比**：

| 方法 | 副本数（估计 $M$ 个可观测量） |
|------|--------------------------|
| 标准层析（逐个测量） | $O(M/\varepsilon^2)$ |
| 分组测量 | $O(M_{\mathrm{groups}}/\varepsilon^2)$ |
| Shadow Tomography | $O(3^k\log M/\varepsilon^2)$（$k$ 为观测量权重） |

### 应用场景

**保真度估计**：$F = \mathrm{tr}(\rho\sigma)$，$\sigma$ 已知。只需 $M = 1$，$N_s = O(1/\varepsilon^2)$。

**纠缠检测**：估计 $M$ 个 Bell 不等式期望值，$N_s = O(3^k\log M/\varepsilon^2)$，局域算符 $k = O(1)$ 时为 $O(\log M/\varepsilon^2)$。

**量子态验证**：验证实验制备的态与目标态的接近程度。

**量子基准测试**：随机基准测试中估计门保真度。

## 各方法的比较总结

| 方法 | 测量次数 | 重建能力 | 适用场景 |
|------|---------|---------|---------|
| Pauli 层析 | $O(4^n/\varepsilon^2)$ | 完整 $\rho$ | 小系统（$n \le 10$） |
| $\ell_\infty$ 层析 | $O(n(3/2)^n/\varepsilon^2)$ | 全矩阵元逐元素精度 | 需要矩阵元而无需谱 |
| 稀疏层析 | $O(s\cdot\mathrm{poly}(n)/\varepsilon^2)$ | 稀疏 $\rho$ | 低纠缠态、MPS |
| Shadow Tomography | $O(3^k\log M/\varepsilon^2)$ | $M$ 个局域函数值 | 多个局域可观测量 |

## 实验实现

### 标准层析的实验进展

- 2019：Google 在 Sycamore（53 量子比特）上实现 2 量子比特态层析；
- 2021：中国科学技术大学在 76 光子系统上演示高维态层析。

### Shadow Tomography 的实验进展

- 2021：IBM 在 27 量子比特设备上验证 shadow tomography；
- 2022：多个实验组演示 $O(10)$ 量子比特的高效 shadow estimation；
- 2023：扩展到量子过程层析（channel shadow）。

## 局限性

### 标准层析

- 指数测量次数限制了 $n \lesssim 15$；
- 经典后处理（MLE）在高维空间中代价极高；
- 系统误差（不完美测量、态漂移）难以校正。

### $\ell_\infty$ 层析

- 对非对角元仍需 $(3/2)^n$ 量级的副本数；
- 逐元素范数不是酉不变的，物理意义有限；
- 对复数相干元的处理比对角元更昂贵。

### 稀疏层析

- 需要预先知道稀疏结构（或用压缩感知自动发现）；
- 对"近似稀疏"态，近似误差难以控制；
- 经典后处理（压缩感知重构）可能不稳定。

### Shadow Tomography

- 不重建完整 $\rho$，只估计特定函数；
- 对非泡利可观测量，方差（影子范数）需要额外分析；
- 显式存储单个影子 $\hat\rho$ 需要 $O(4^n)$ 内存，实际实现只存储测量比特串（每份 $n$ 比特）并按需计算 $\mathrm{tr}(O_k\hat\rho)$；
- 对量子通道层析（channel shadow），资源需求显著增加。

## 总结

量子态层析经历了从"完整重建 $\rho$"到"估计 $\rho$ 的函数"的范式转变。我们用霍夫丁界推导了逐泡利方案的 $O(4^n/\varepsilon^2)$ 采样复杂度，并指出 Frobenius 精度下朴素方案达到 $O(N^3/\varepsilon^2)$、信息论最优为 $\Theta(N^2/\varepsilon^2)$。Shadow Tomography 以 $O(3^k\log M/\varepsilon^2)$ 的副本数估计 $M$ 个权重为 $k$ 的局域可观测量，是目前最具可扩展性的方案，但其适用范围限于有限个已知可观测量的期望值估计。

---

**参考文献：**

1. Aaronson, S. (2018). *Shadow tomography of quantum states.* STOC 2018.
2. Huang, H. Y., Kueng, R., & Preskill, J. (2020). *Predicting many properties of a quantum system from very few measurements.* Nature, 587, 589-593.
3. Gross, D., Liu, Y. K., Flammia, S. T., Becker, S., & Eisert, J. (2010). *Quantum state tomography via compressed sensing.* Physical Review Letters, 105(15), 150401.
4. Haah, J., Harrow, A. W., Ji, Z., Wu, X., & Yu, N. (2017). *Sample-optimal tomography of quantum states.* IEEE Transactions on Information Theory, 63(9), 5834-5851.
---

> 返回目录：[量子计算算法教程系列](https://chenzhaoyun.com/index.php/archives/54/)