量子态的有效学习是量子计算中的一个重要问题。不同于经典的情形，完整刻画  个量子比特构成的系统需要  份完全相同的量子态。随着  的增加，这一指数级增长使得完整重构量子态的密度矩阵变得不切实际。针对这一问题，研究者提出了投影成像方法（shadow tomography），通过恢复密度矩阵在给定的一系列二元正定算子值测度（positive operator-valued measure，POVM）集合上的投影以研究量子态的性质，从而规避密度矩阵的重构，相关算法可以做到关于  的多项式级别。但在现实中，POVM  的选取可能基于观察者的历史观测，而非事先确定的。此外，现有的投影成像算法要求对量子态的多个副本进行联合测量，在近期量子计算机上受限于规模问题可能难以实现。鉴于这两点，一种自然的设定是考虑量子态的在线学习。在线学习算法将优化看作一个过程^[1]，在这一设定下，POVM  是顺序产生的，玩家（观察者）在每一步时间  输出对量子态的预测  ，并根据  承受损失。算法的目标是最小化后悔值，也即玩家的损失与最小损失（真实量子态在  下的结果）之间的差距，现有方法对于  步迭代可以做到  。

然而以上方法均未涵盖现有量子计算机的一个重要问题：量子态的涨落。在实际场景中，我们通常无法持续校准量子态，例如在 IBM 的量子计算平台上，一个包含测量的量子电路可能连续执行成百上千次，而在这些实验中途不会进行校准。在现实中，量子态  通常是从初态  开始，通过控制哈密顿量  演化一段时间  得到，如果设备在一段时间内未被校准，则实际制备的量子态受噪声扰动。考虑到这些涨落的存在，我们关心如下问题：如何学习动态变化的量子态。本文采取自适应在线学习（adaptive online learning）方法，对动态量子态的学习取得结果关于量子比特数  呈多项式增长，关于测量次数亚线性增长。

考虑一个  量子比特的量子态，其在时刻  的密度矩阵为  ，即迹为1的  的厄米正定矩阵。在时刻  ，我们通过二值 POVM  测量  ，  可以表示为  的厄米矩阵，其特征值在  范围内。这样的  以  概率接受  （返回1），以  概率拒绝  （返回0）。定义凸损失函数  ，常用的损失函数有  及  等。

我们考虑两种度量：动态后悔值和适应性后悔值。

1. 动态后悔值衡量玩家的损失与变化的比较器（comparator）之间的差异，其界限通常由最佳比较器随时间的变化程度（路径长度  ）来表征。在这一设定下，我们考虑真实世界中量子态缓慢演化的情形，对应于比较器在核范数下的路径长度有界，即 其中  ，  。

2. 适应性后悔值的定义更为精细，其衡量所有时间区间内的最大后悔值，本质上刻画了比较器的变化。在这一设定下，我们考虑量子态在某些时刻发生跳变的情形，相应适应性后悔值的定义是 

在动态后悔值的设定下，假设路径长度  ，且损失函数  为 L-Lipschitz 连续且映射到区间  的凸函数，则 Algorithm 1的动态后悔值上界为  （Theorem 1）。相应地如果任意  ，有  满足  ，则存在显式策略，使得错误次数（  ）最多为  （Corollary 1）。在证明技术上，我们借鉴了先前关于 OMD 后悔值上界的证明。然而，由于优化变量从实数向量转变为厄米矩阵，一些定理不能直接应用，例如布雷格曼散度（Bregman divergence）上界的推导，以及任意两个厄米矩阵的冯诺依曼熵之差与其核范数之间关系的证明。我们在厄米矩阵的框架下解决了这些问题。

在适应性后悔值的设定下，同样假设损失函数  为凸函数、L-Lipschitz 连续，并映射到区间  ，则 Algorithm 3存在强适应性后悔值上界  （Lemma 1），特别地，对于量子态发生  次跳变的情形，相应的  -shift 后悔值 有上界  （Theorem 2）。类似地，在  条件下，错误次数有上界  。

此外，我们还考虑了 Algorithm 1 在量子计算实际场景中的应用：假设预先给定  个量子信道  ，则存在算法动态后悔值有上界  ，其中    。我们观察到，如果比较器的演化和预先给定的某一信道符合，那么算法的表现会较好。通过构造   -net，预先给定的信道集合也可以是无穷集合，例如存在算法的动态后悔值有上界   ，其中  ，  是所有  量子比特上的  -局部量子信道的集合。

为了支持我们的理论发现，我们开展了一系列数值实验以验证所提出模型的有效性。

与非自适应算法的对比 自适应在线学习算法的一大显著优势在于捕捉量子态的动态变化。此前的算法如 RFTL 对于固定量子态有良好的预测能力，但不能很好适应量子态演化。我们比较了 RFTL 算法与我们的 Algorithm 3在量子态发生k次跳变的情形下累积的适应性后悔值，结果如下图所示。“CBCE”代表 Algorithm 3，“RFTL”为非自适应算法。两条曲线表现出相似的趋势，但 Algorithm 3实现了更小的后悔值。在子图 (b)-(f) 中可以明显看出，随着  的增加，两条曲线之间的距离逐渐扩大，表明我们的算法在长期内保持了优势。

后悔值上界的验证 我们还开展了实验用于验证后悔值的上界。

后悔值表征算法预测与最佳值差距在  步的总和，其关于  的平均值能更好地说明每一次预测的差值。我们绘制了在  次跳变设定下后悔值的平均  随  增长的变化，如下图 (a) 所示。在不同的参数选择  下，  总是随着  的增加收敛至0，表明后悔值是次线性的。更具体地，具有较大  值的曲线有更大的  ，且收敛得更慢，这与更多变化使学习任务更困难的直觉一致。

在子图(b) 中，为了精确验证上界，我们绘制了比值  的图像。我们在每个区间上随机重复实验50次，绘制了常数  的最大值。如图所示，该比值被限制在常数  以内，有力地支持了后悔值的上界   。

[1] Elad Hazan, Introduction to online convex optimization, Foundations and Trends® in Optimization 2 (2016), no. 3-4, 157–325, arXiv:1909.05207.

[2] Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou, Adaptive online learning in dynamic environments, Advances in Neural Information Processing Systems, vol. 31, 2018, arXiv:1810.10.

[3] Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, and Ashwin Nayak, Online learning of quantum states, Advances in Neural Information Processing Systems, vol. 31, 2018, arXiv:1802.09025.

[4] Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett, Improved strongly adaptive online learning using coin betting, Artificial Intelligence and Statistics, pp. 943–951, PMLR, 2017, arXiv:1610.04578.

图文 | 杨睿、王昕兆

PKU QUARK Lab