退量子化

左 芬

10.21

回头看了一下，今年都没写过什么东西，难怪总觉得活得云里雾里。最近在读Abraham Pais写的“Subtle is the Lord…”和“Einstein Lived Here”的中译本，觉得很有特色。Pais本是物理学家，但可能因为撰写科学家传记而更为人熟知。等到时机成熟，俺也许会做这方面的尝试。

这次我们来说一个有趣的同行，Ewin Tang。她的主页见 https://ewintang.com/。Tang是00后，14岁就上了大学，是不折不扣的少年大学生。18岁大学还没毕业的时候，她就已经在Aaronson的指导下提出了一种全新的算法，即关于推荐体系的量子启发式算法。此前人们倾向于认为，量子算法可能在该体系中存在指数式加速。Tang的新算法让这一加速落空，并为改进经典算法给出了新的思路。这一工作很快得到了Lloyd以及Preskill等人的重视。

Tang 后来的工作都是沿着这一思路开展的。现在人们把这套程式简称为“退量子化”（dequantization）。我还没有非常仔细地去读相关的文献，只是大致了解了一下。简单来说，就是在某些问题中，我们需要处理大量经典数据。这时我们需要假定这些数据存在一定结构，以便快速地读入到量子计算机中。一旦这种假定得到满足，后续的量子算法往往可以很高效，甚至达到指数级的加速。而Tang及其合作者则发现，在同样的结构下，很多这类量子算法都可以用某种概率型的经典算法来实现，从而“退量子化”。结果表明，量子机器学习中的大部分算法都可以这样退量子化。夸张一点地说，Tang的新思路几乎消除了大部分量子机器学习类算法中可能出现的指数式加速。同时，这也引发了人们的进一步思索：量子与经典之间的差距到底有多大？

最后说一句题外话。Ewin特意在主页上让大家以“她”称呼自己。So, is it true that“a great mind must be androgynous”?