量子计算机真的优越吗？-- 四则量子计算新闻
大家好，我是大老李。今天的节目是有关近期几则量子计算的新闻的，其实也不算太新，很多是去年的，但是几乎没有人用中文报道过，所以大老李给大家介绍下。
这几则新闻共同点都是关于这个问题：量子计算机真的比经典计算机优越吗？如何证明其优越性？这几年我们听到过太多有关量子计算机的事情，它是如何得“快”等等。
通过前两期有关复杂度的问题了解，你应该了解到：量子计算机能快速处理的问题定义为“BQP”问题。对经典计算机来说，能快速处理的问题是P问题，能快速验证的问题是NP问题。重复一次：P问题都是NP问题，但还没有证明P！= NP，这就是克雷数学研究所悬赏的P vs NP 问题。但不管怎么样 ，看起来经典计算机能处理的最复杂的问题的上限，就是NP类问题。
量子计算机概念产生之后，科学家提出：是否有某个问题，属于BQP问题，但不属于NP问题？如果有，那么我们就证明量子计算机确实有其优越性，因为它能快速处理一些经典计算机不能快速处理的问题。
2018年6月21日，在普斯顿和斯坦福大学任职的两位计算机科学家(Ran Raz and Avishay Tal) 发表了一篇论文，第一次证实了，存在这样一个问题，它属于BQP问题，但不属于NP问题。这个问题的描述是这样的： 给你两个随机数生成器，并且你可以让它们生成任意数量的随机数。请问，你能否判断这两个随机数生成器是“独立”的？
我们在学习概率的时候，有一个很重要的概念就是随机变量的“独立”性。在计算概率问题时，判断清楚两次概率事件是否独立是一个很重要的前提。比如，连续丢两次硬币的结果我们认为是独立的。 而有些随机事件就不是独立的，比如你收听“大老李聊数学”节目的概率和你的数学成绩高于90分的概率是有相关性的。
现在有个特别的情况，有人说：我这里有两串随机数，它们是互相独立的，绝无相关性。请问你有没有办法验证这一点？比如，如果其中一串随机数其实是另一串随机数经过某种变换，比如傅里叶变换之后得到的，这样这两串随机数就是完全相关的。但你仅凭目测是绝无可能发现这样的相关的。
以上这个问题是2009年得克萨斯州大学的教授 Scott Aaronson, 首先提出的，他将其命名为“傅里叶相关”（forrelation=fourier+ relation）问题，并且证明了傅里叶相关问题是一个BQP问题，也就是量子计算机能快速处理这个问题。
而去年两位科学家的结论就是，“傅里叶相关”问题不属于NP（或PH)问题，从而正式发现了一个量子计算机可以快速解决，而传统计算机无法快速解决的问题。但另外，科学家也猜想，存在某些问题属于NP，但不属于BQP，也就是经典计算机可以快速处理，而量子计算机无法快速处理的问题。如果这个猜想被证明，那意味着经典计算机有其不可被取代的方面。目前这个猜想还有待证明。
第二则新闻是有关证明“量子计算的真实性”，换句话说就是：量子计算机真的在计算吗？你可能问，这不是废话吗，量子计算能解决经典计算机不能快速处理的问题，这不就是证明量子计算的真实性吗？但可惜，这些都还是理论上的，因为目前实验中的量子计算机还只能处理很简单的问题。
比如2016年，IBM公司曾经演示过用量子计算机进行15=3*5的因子分解，就有人质疑：你怎么证明这是用量子计算方法算出来的，而不是里面藏了一个计算器？当然，如果IBM能对一个非常的大的整数进行这种分解，就不会有人质疑了，但是目前还远做不到。即使有一天，有人能用量子计算机进行大整数分解了 ，还是可以有人质疑，是不是你只是偷偷改进的经典计算机上整数分解的算法，让后骗大家说这是量子计算机完成的？
另一方面 ，量子计算是非常“隐秘”的。量子计算的一个基本原理是利用了量子的叠加态和纠缠，这些状态是很“脆弱”的，你不能太早去“观察”它。量子物理中，有个“观察者效应”就是说你不能“观察”量子，一但“观察”，量子的特殊性就消失了，与宏观世界里的一个“小球”没有区别了。在这里，什么样的动作是一个“观察”，还是物理学家正在研究的领域。无论如何，你不能“看”量子计算机的计算过程，只能静待结果。
因此，就有人问：如何证明量子计算是存在的？如何知道量子正在执行我们赋予的那些“算法”。2018年10月，加州大学伯克利分校的一位女博士研究生(Urmila Mahadev )，在其博士论文里，给出了一种方法，可以让量子计算机向一个只拥有经典计算机的验证着，证明其计算的真实性。
她的思路是这样的：之前已有人证明，如果一个观察者有能力“测量”一个量子位，则这个观察者可以验证这个量子计算机。这有点像让一个量子计算机去检查另一台量子计算机的计算。但现在要求观察者只有经典计算机，那如何验证的？
那就让量子计算机自己“检查”的自己的计算。大致意思就是，让量子计算机进入一种纠缠态，但并不告诉计算机，未来会如何测量的。一直到测量时候，才真相大白，原来是为了完成这种计算，这样量子计算机是无法产生欺骗行为的。
这就好比让一个小学生做很多加减乘除四则运算，这个小学生完全不知道干嘛要算这些，直到计算完成，你才跟他说这是一次矩阵乘法运算。当然，这也可能是一次求π的近似小数的运算。因为运算过程中，运算求解的具体问题不知道，这个小学生就无法进行欺骗。
总之，有了以上成果，我们知道有办法对量子计算的真实性进行检验，而无需等到量子计算机的计算能力超过经典计算机，因为如论如何改进，经典计算机无法通过这种检验。
第三个新闻是有关量子计算机验证问题的能力的。我们已经发现一些量子计算机算法，可以在多项式时间里求解NP问题，也就是那些在经典计算机上只能在多项式时间内验证，而不能在多项式时间里求解的问题。这是我们研发量子计算机的主要动力。
另一方面：量子计算机有没有可能使得之前不能在多项式时间里验证答案的问题，变得可以在多项式时间里验证呢？也就是原先比NP问题更复杂的问题，变为NP问题呢？答案是可以的。
今年4月，加州理工大学和麻省理工大学的两位计算机科学家发表了一篇论文，证明，利用量子计算机，可以大大提高我们对一些问题的验证能力。比如之前节目反复提到的过的三色着色问题：请你给一幅地图用三种颜色着色，使任何相邻的两个区域具有不同的颜色。相应的验证问题是：给你一副用三种颜色着色地图，请你判断，是否任意相邻的两个区域具有不同的颜色。很明显这个问题是可以在多项式时间里验证的的，所以三色着色问题是一个NP问题。
但为了利用量子计算机进行更快的验证，我们引入一个称为“交互式验证”的概念，顾名思义，就是一问一答与机器交互验证的过程。比如还是这个三色着色问题，假设你自己是个色盲，完全辨别不了颜色，你只能让另一个人帮你验证。但另一个人很不配合，他可能对你撒谎。
但是你可以对他进行一种“拷问”，来确保得到你想要的结果。方法是这样：你从已经到手的着色完成的地图里任选两个区域里剪下相同形状的一小块。这样，这两小块区域除了颜色不同，没有任何不同。此时你不能直接问验证者，这两块区域是否同样颜色，因为他可能撒谎。但你可以左右手各放一个小块，给他看，告诉他左手的那块称为“A块”，右手的那叫作“B块”。
然后，你把两小块区域放在身体后面任意交换，然后再给验证者看，哪块是A，哪块是B？此时，如果这两块区域颜色不同，且验证者没有撒谎，那么这就太简单了。他应该能够稳定的说出哪块是A，哪块是B。但如果两块颜色是一样的，则他说对的概率应该趋向于50%。只要经过足够多次的实验，你就能区分出以上两种情况。以上过程就叫交互式证明。
再一次，科学家定义了“IP”(interactive polynomial)问题概念，意思是“交互式多项式时间”问题的意思。经过前两集音频节目，相信你也能猜出这个定义的意思就是：可以用交互的方式，在多项式时间内验证的问题。
科学家证明了所有NP问题都是IP问题（再一次请读者自己思考为啥）。另外，以上问题中只有一个验证者，如果你可以询问多个人进行交互式证明，则这类问题称为MIP问题，这里M就是英语mulitple=“多个”的意思。当然IP问题，都属于MIP问题。
所以，P问题，NP问题，IP问题和MIP问题再一次构成了一组复杂度的“俄罗斯套娃”。而科学家也证明了，量子计算机能在多项式时间内验证所有MIP问题，所以量子计算机能快速验证的问题复杂度上界似乎就是MIP。
之前，科学家还定义过一个复杂度：称为“NEEXP”，意思是“非确定性双重指数时间”。它的意思有点类似NP问题。NP问题的字面意思是“非确定性多项式时间”， 同理我们从中可以推广出“非确定性指数时间”和“非确定性双重指数时间的概念”。
如果一个问题，用传统计算机检查答案的话，需要双重指数的时间，那么它就是NEEXP问题。双重指数就是说指数有两层，比如2^2^n次方。可以想象这种问题要比NP问题复杂非常多，因为NP问题检查只需要多项式时间。
这次，两位科学家证明了，所有NEEXP问题都是MIP问题，意思就是所有用传统计算机需要双重指数时间来验证的问题，都可以用量子计算机在多项式时间内验证。这意味量子计算机不但计算能力优越，连验证问题结果的能力也远优于经典计算机。当然，以上都是理论，如何实现还需要等待。
最后要聊的一则新闻与以上新闻都不同的是：以上新闻都是关于量子计算机对比传统计算机的优越性，而这则新闻则是关于传统计算机借鉴了量子计算机算法，从而提高了算法效率的。这个算法是关于购物网站的“推荐算法”。
现在有很多网站都有一个“猜你喜欢”的功能，就是通过你之前看过的内容，买过的东西来推测你喜欢什么。其原理就是根据历史上很多人的购物记录，从中分析那两样的组合最常出现，这个问题学术上称为“推荐问题”（recommendation problem）。
你脑子里稍微思考一下，你能想到的推荐问题通常都是一个指数时间算法，甚至找出一个多项式时间里的检查算法都很难。而在2016年，有两位计算机科学家（Iordanis Kerenidis, Anupam Prakash）发表了一个关于”推荐问题”的量子计算机算法，其复杂度是多项式时间。(O(poly(k)polylog(mn))。
2018年7月，在德克萨斯大学奥斯丁分校的就读的研究生，时年18岁的华裔少女，Ewin Tang发表了一篇论文，她证明了，对“推荐问题”，经典计算机也可以达到与量子计算同样的复杂度效率，而她的思路正是借鉴了量子计算机的算法。
这就回到了一个老问题：量子计算机对比经典计算机，到底有没有意义？从理论上看，我们确实证明量子计算机优越性，但是从实践上讲，量子计算机除了少数为其“量身定做”的问题，在其他大多数可以比较的问题上，其计算效率还远不如经典计算机。甚至谈不上计算效率，因为都还没有量子计算机可以使用的算法。
而这次，Ewin Tang仅根据理论上的量子计算机算法，就能把经典计算机上的算法效率改进得跟量子计算机上一样好，这使得经典计算机在实践领域里又前进一步。
喜马拉雅上“古哥古点”节目中，曾提到过“量子霸权”和”量子优越”这两个概念。简单说，“霸权”就是绝对的优势，“优越”是暂时局部的优势。那么Ewin Tang的成果至少是延迟了“量子优越”的时间，因为在这个“猜你喜欢”的问题计算上，经典计算机可以做的与量子计算机一样好。
顺便说下，Ewing Tang在本科时期的导师就是之前提到过的，提出“傅里叶相关”问题的Scott Aaronson，可谓名师出高徒。现在，今年19岁的Ewing Tang已经进入华盛顿大学攻读博士学位。
以上就是给大家播报的四则量子计算相关新闻，总结一下：
科学家发现了一个量子计算可以快速处理，而经典计算机不能快速处理的问题，即考察两个随机数序列是否具有相关性的问题。
科学家发现了一个交互式证明方法，可以证实量子计算机确实是以量子理论的方法进行了“计算”，而不被其他计算形式欺骗或是因为“运气”好得到了计算结果。
科学家证实了量子计算机对那些在传统计算机上需要双重指数时间进行验证的问题，在多项式时间内验证。所以，量子计算机在验证问题的能力上比经典计算机非常优越。
科学家成功移植量子计算机上的“推荐问题”，也就是“猜你喜欢”问题的算法到经典计算机上，使得在这一问题上，经典计算机有与量子计算机有相同的计算效率。
好了，祝各位学生朋友暑期愉快，多做数学题，下期再见！
参考链接：
https://www.quantamagazine.org/graduate-student-solves-quantum-verification-problem-20181008/
https://www.quantamagazine.org/teenager-finds-classical-alternative-to-quantum-recommendation-algorithm-20180731/
https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/
https://www.quantamagazine.org/computer-scientists-expand-the-frontier-of-verifiable-knowledge-20190523/
