闲话态层析 (state tomography)

幸福侠侣

(几周前写的, 没动力把剩下的补了, 诸位将就看吧...)
写这个的起因是若干周前的 theory seminar, 总算有个机会把态层析相关的工作串起来. 这篇文章几乎只会谈论问题的 statement 和主要结果 (定理) , 此外本文的主要参考是 Aaronson 关于 shadow tomography 的 talk, 所以内容上难免有所偏颇——大概会出现 Ronald de wolf 吐槽著名"小黄书" Kitaev-Shen-Vyalyi 的同样问题 (见 Book reviews, 吐槽相当精彩).
态层析和实验密切相关, 不过本文不会涉及任何相关内容. 这里关心的是如何在 Learning theory 的视角下看待这一问题. 态层析大致说的是这么一件事, 给定一个量子态 (密度矩阵表述) 的若干份拷贝, 如何通过一系列局部测量结果学习它的相关信息. 如果问题是重构整个密度矩阵, 那么这就是态层析, 可以证明指数时间是充分且必要的; 反之, 如果只需要得到量子态的部分信息, 那么在一些情况下可以得到多项式时间的结果.

Full tomography & shadow tomography

态层析 (state tomography) 说的是这么一件事:

State tomography
给定未知的密度矩阵描述的量子态 \rho ( D\times D 矩阵), 我们需要多少份拷贝来重建 (reconstruction) 量子态 \rho ?

我们总是需要测量来读取量子态中的信息, 但是测量会破坏量子态, 因而我们并不能指望对同一量子态进行多次局部测量来重建它. 对于 n -粒子系统 D=2^n , 那么量子态 \rho 是个十分巨大的 2^n\times 2^n 矩阵, 所以看起来我们重构 \rho 需要的测量次数是 \Omega(D^2) , 这是必要条件. 在 STOC 2016 上, O'Donnell-Wright [4] 和 Haah-Harrow-Ji-Wu-Yu [3] 分别证明了这也是充分条件.
记重建后的量子态为 \rho^{\prime} , 那么它们的误差可以由迹距离刻画 \|\rho-\rho^{'}\|\leq\epsilon . [4] 中给出了一组 PVOM 测量, 使得我们只需要 O((Dr/{\epsilon}^2)\mathrm{ln}(D/\epsilon)) 份拷贝, 其中 r 是密度矩阵的秩. 证明本身涉及群表示论 (如 Schur-Weyl duality) 这里不再讨论.

看起来指数规模的拷贝个数是绕不过去了, 不过上面说的是重建整个矩阵, 如果只是重建量子态的一部分信息呢? Aaronson 的近作 [2] 中提及的 shadow tomography (Steve Flammia 语) 就是个例子, 这次要重建的不是整个矩阵, 而是重建给定 POVM 中每个矩阵测量后的结果; 因为只涉及了密度矩阵中的一部分, 故而谓之"shadow":

Shadow tomography
给定一组已知的2-输出 POVM 测量 E_1,\cdots,E_M , 以及未知的密度矩阵描述量子态 \rho ( D\times D 矩阵, 且 D=2^n ). 对于所有 i\in\{1,2,\cdots,M\} , 以 additive error \epsilon 估计接受概率 Pr[acc]=Tr(E_i \rho) \geq 1-\delta. 那么在这种情况下, 我们需要多少份量子态 \rho 的拷贝?

很直观的想想, 如果从量子态出发有 O(D^2) ; 而从测量出发有 O(M) . 于是能否只需要多项式规模 poly(\log D, \log M) 份拷贝呢? [2] 中给出了肯定答案, 即需要的拷贝个数为 O(\frac{\log 1/\epsilon}{\epsilon^5} \log^4 M \log D) . 而且这并不违背 Holevo 定理, 因为 full tomography 仍然需要 \Theta(D^2) 份拷贝.

Learning theory 与态层析

Leslie Valiant 在 2010 年的 Turing award 提及了 PAC learning, 即 probably approximately correct. (以下细节省略...)
不过我们可以控制一下测量对量子态的破坏程度, 如 gentle measurement (Andres Winter 语, 物理学家似乎偏爱 weak measurement? )

给定一组2-输出测量 {E_1,\cdots,E_N} , 并满足 \mathrm{Tr}(E_i \rho) \geq 1-\epsilon , 使得 \|\rho^{\prime}-\rho\|_{tr} \leq \sqrt{\epsilon} -close, 其中 \rho^{\prime} 是测量后的量子态.

这里说的是选择一组比较好的 POVM, 并设法控制测量前后的量子态的迹距离.

再论 Shadow tomography

一件有趣的事情是 shadow tomography 的动机, 它来自于 private-key quantum money. (以下细节省略...)

下面简单提几句和证明相关的事情.
一是 Absent-Minded Adviser problem (大概可以译成 脑子缺跟弦的导师?)
Aaronson 在 2004 年得到的 Postselected Learning theorem, 这里的量子态 \rho 对于 Alice 来说是已知的. 那么需要的拷贝份数是 O(\log M\log D/M^2) . Bob 不断迭代学习过程, 即以 POVM 测量 \{E_1,\cdots,E_M\} 得到 \rho^* ; 在重复 O(\log D^*) 次迭代后, 得到估计的量子态 \rho_T .
这一过程可以导出 \mathsf{BQP}/\mathsf{qpoly}\subseteq \mathsf{PostBQP}/\mathsf{poly} , 类似复杂性类 \mathsf{P}/\mathsf{poly} 包括任何多项式规模的经典线路可以解决的问题 ( \mathsf{P} 在此基础上还要保证用于求解问题的线路, 必须在多项式时间内生成). \mathsf{BQP}/\mathsf{qpoly} 是任何多项式规模的量子线路可以求解的问题, 而 \mathsf{PostBQP}/\mathsf{poly} 则在此基础上加了个"post-selection". (我想这里还是省略了某些细节...)
与之相关的一个公开问题是 \mathsf{BQP}/\mathsf{qpoly}\overset{?}{=}\mathsf{BQP}/\mathsf{poly} .

最后很自然地我们会想问:

• 需要的拷贝个数是否可以与 D 无关?
  
• 是否存在某些特殊的量子态, 仅需要多项式规模份拷贝就足以进行 full tomography? 如 [5] 中提及的 stabilizer state 是 PAC 可学习的.
  

Reference
[1] [1701.06806v3] A Survey of Quantum Learning Theory
[2] [1711.01053] Shadow Tomography of Quantum States
[3] [1508.01797] Sample-optimal tomography of quantum states
[4] [1508.01907] Efficient quantum tomography
[5] [1705.00345] Stabiliser states are efficiently PAC-learnable

原文地址：https://zhuanlan.zhihu.com/p/30898796