量子态层析详解：从指数方法到 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\) 个，故
目标：我们通过测量制备好的量子态副本，估计 \(\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\) 个元素，且在迹内积下两两正交：
展开公式的推导：设 \(\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\)，即
于是估计全部 \(\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\) 后，我们构造随机变量
我们证明 \(\mathbb{E}[X] = \mathrm{tr}(P\rho)\)：记 \(U = \otimes_i U_i\) 为上述基变换，测量结果 \(b\) 的概率为 \(\mathrm{tr}(\rho\, U^\dagger |b\rangle\langle b|\, U)\)，于是
最后一步用了 \(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)\) 次重复测量。
总测量次数：
这是指数级的：\(n = 50\) 时 \(4^{50} \approx 10^{30}\)，完全不可行。
线性反演¶
公式推导：我们把测得的频率 \(\hat f_P\)（对 \(\mathrm{tr}(P\rho)\) 的估计）直接代入泡利展开式：
该估计是无偏的（每个 \(\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\)，则
其 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^{-}\) 次），我们在合法密度矩阵的凸集上最大化似然函数：
取对数便于分析：
凸性：\(\ln\) 是凹函数且每个 \(\mathrm{tr}(P_i\rho)\) 是 \(\rho\) 的线性函数，故 \(\ell(\rho)\) 是 \(\rho\) 的凹函数；约束集（半正定、迹一）是凸集。因此极大似然层析是一个凸优化问题，其最优点全局存在。
驻点条件：引入拉格朗日乘子处理迹约束，对 \(\ell\) 求梯度并令其为零，得
即在最优点处"加权观测算符" \(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]\)，则
代入 \(a = -1, b = 1\) 得 \((b-a)^2 = 4\)，故
令右边等于失败概率 \(\delta\)，解出
这就是单个泡利期望值的 \(O(\varepsilon^{-2})\) 采样复杂度。（用切尔诺夫界可得到相同的指数标度，霍夫丁界给出的是自洽的显式常数。）
对所有泡利字符串取联合界：要让全部 \(4^n - 1\) 个估计同时达到精度 \(\varepsilon\)、总失败概率至多 \(\delta\)，我们对每个字符串分配失败概率 \(\delta' = \delta / 4^n\)，于是
总副本数为 \((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\)，需要更细的分配。由泡利展开与正交性，
其中 \(\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\) 满足：
（其中 \(\|\cdot\|_{\max}\) 是矩阵元素的逐个最大绝对值，不是算符范数；\(\ell_\infty\) 层析因此依赖基的选择。）
实现方法与复杂度推导¶
对角元（可廉价并行估计）。对角元就是计算基测量的输出分布：单次测量得到一个样本 \(j \sim \rho_{jj}\)。要把全部 \(N = 2^n\) 个对角元同时估计到精度 \(\varepsilon\)，我们对频率估计用霍夫丁界并对 \(N\) 个结果取联合界：
即对角元只需要对数多个副本量级，远少于完整层析。
单个非对角元 \(\rho_{xy}\)（\(x \ne y\)）。我们构造两个可观测量的测量。令
两者在二维子空间 \(\mathrm{span}\{|x\rangle, |y\rangle\}\) 上分别同构于 \(\sigma_x\) 与 \(\sigma_y\)（本征值 \(\pm 1\)），在正交补上为零，因此都可以通过一个 \(O(n)\) 深度的多控电路映射到单比特测量。计算迹：
（第二式用了 \(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\) 精度层析可以用
份副本完成（对数因子来自对 \(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\) 个估计的联合界，每个泡利串需要
次测量，总测量次数为
方法三：压缩感知层析。我们利用 \(\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）给出了更实用的方案：随机泡利测量 + 经典后处理。
步骤：
我们对 \(\rho\) 的每个副本，独立、均匀地为每个比特选取 \(X\)、\(Y\)、\(Z\) 三个基之一，等价于施加 \(U \in \{I, H, HS^\dagger\}^{\otimes n}\)；
在计算基测量，得到比特串 \(b \in \{0,1\}^n\)；
计算单副本影子（classical shadow）\(\hat\rho = \bigotimes_{i=1}^{n} \bigl(3\,U_i^\dagger|b_i\rangle\langle b_i|U_i - I\bigr)\)；
重复 \(N_s\) 次，得到影子集合 \(\{\hat\rho^{(1)}, \ldots, \hat\rho^{(N_s)}\}\)；
对任意可观测量 \(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\)。对两个结果求和：
于是
多比特情形。我们用信道语言推广：定义单比特"去极化到对角"的测量信道
上面的计算表明 \(\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}\) 的线性，
\(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\)；否则恰为零。于是
（用了 \(s_i^2 = 1\)），而无偏性给出 \(\mathbb{E}[\mathrm{tr}(P\hat\rho)] = \mathrm{tr}(P\rho)\)，故
矩阵元方差。我们把 \(\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\) 的二项式展开）：
其中 \(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}[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\) 成立，所需副本数为
对权重为 \(k\) 的泡利可观测量，\(\mathrm{Var} \le 3^k\)，故
我们特别指出：方差上界 \(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\) 的局域可观测量，是目前最具可扩展性的方案，但其适用范围限于有限个已知可观测量的期望值估计。
参考文献：
Aaronson, S. (2018). Shadow tomography of quantum states. STOC 2018.
Huang, H. Y., Kueng, R., & Preskill, J. (2020). Predicting many properties of a quantum system from very few measurements. Nature, 587, 589-593.
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.
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.
返回目录：量子计算算法教程系列