8.3.5 量子层析
由量子过程层析问题可以转换为对其 Choi 态的层析，在这里我们主要关注量子态层析（Quantum State Tomography, QST）。量子态层析主要关注如下问题，对于任意未知的𝑛-qubit 量子态𝜌 ∈ ℂ𝑑×𝑑，这里
𝑑 = 2𝑛，我们需要这个量子态的多少份独立复制才能输出一个量子态 的矩阵描述𝜌̂，使得‖𝜌 − 𝜌̂‖ ≤ 𝛿。一般情况下我们考虑迹距离，即‖⋅‖𝑡𝑟。量子态层析的采样复杂度对很多量子计算问题都有影响，例如量子纠 缠证明[144]、理解量子态之间的纠缠[145]等等。
一个最简单的暴力QST 算法需要𝑂(𝑑6)个量子态的复制：对𝑑2个泡利矩阵来进行测量，每个测量𝑂(𝑑4/𝛿)次，再通过解线性方程组得到𝜌的描述。在 2012 年，一个更高效率的 QST 算法由 Flammia 等人提出[146]，他们使用了一种名为压缩感知的技术，把 QST 需要的量子态复制数提高到了𝑂(𝑑4/𝛿2)。
接下来，Kueng 等人在 2017 年使用更复杂的技术[147]，把需要的
复制数提高到了𝑂(𝑑3/𝛿2)。没过多久，Haah 等人[148]和 O’Donnell 等人[149]在这个问题上取得了突破，得到了这个问题的最优采样复杂度。在迹距离下，进行误差不高于𝛿的量子态层析需要𝑂(𝑑2/𝛿2)个量子态的复制；如果已知这个量子态的秩不超过𝑟，则在保真度（Fidelity）误差不超过𝜖的情况下需要𝑂(𝑑𝑟/𝜖)个量子态的复制。
上面的算法从采样数上来说已经达到了最优，但是这些算法的时间复杂度非常高，事实上，它们的时间复杂度是𝑑的指数级，也就是
𝑛的双指数级。在现实中，这样的时间复杂度是无法忍受的。一个自 然的问题是是否存在时间上高效的层析算法？更具体地来说，如果我 们仅允许每次对一个量子态的复制进行测量操作，最少需要多少份量 子态的复制才能进行QST？有一系列工作对这个问题发起挑战[150, 151]，并且在 2022 年，Chen 等人给出了这个问题紧的下界[152]，结合 Kueng 等人在 2017 年的工作[147]，我们知道在这种情况下需要的量子态复制 数是Θ(𝑑3/𝛿2)。
与量子层析有密切联系的另一个问题是量子态谱估计，目标是学习未知量子态的谱，即特征值。2016 年，O’Donnell 和 Wright 证明了
𝑂(𝑑2/𝜖2)个量子态的复制能够让我们以𝑙1误差𝜖以内估计量子态的特征值，他们也证明了一个下界𝑂(𝑑/𝜖2)。谱估计在一些属性测试问题中有重要意义[149, 153-155]。有关谱估计紧的采样复杂度仍然是一个开放问题。