股票交易也是一个重灾区。在过去，股票交易通常需要在一个很大的交易所中进行，就像我们在电影中看到的那样，交易员在那里用一个很帅的手势来指挥买入和抛售，用一个眼神来匹配最佳的价格。但是现在，算法会自动适应最佳的价格并且买入抛售股票。虽然偶尔会导致“闪崩”的现象。机器学习算法已经很强大了，他们能够替代人类进行一些决策，也能进行人脸识别，将社交媒体的内容和用户进行匹配，也能进行一些司法判决。这些决策系统都为人们提供了便利，但也带来了很大的社会挑战。比如歧视问题和政治两极化的问题正在被拉大。这个问题很复杂我们无法一言概之。上述的问题只是此类场景中的一小部分。作为计算机科学家，我们的目的是使计算尽可能高效和简单，但我们必须保留减少计算复杂性，也就是计算“摩擦力”的成本。随着摩尔定律的失效，计算机研究人员将目光转移到量子计算机的领域，这些年，量子计算机的研究和应用正在经历大幅的增长。谷歌、微软和IBM等大型科技公司，以及各种创业公司都在量子计算机方面投入大量资源进行研究。美国发起了国家级的量子计算研究计划，中国等其他国家也在纷纷效仿。在2019年，谷歌宣布他们已经通过使用53个量子比特的量子计算机实现了“量子霸权”，解决了当前传统计算机无法解决的很多计算任务。虽然有很多人质疑这个说法，但是我们无疑的正在处于量子计算新时代的起点之上。尽管如此，我们距离能够跑起来Peter Shor的量子算法，以及拥有一台真正的量子计算机，还有相当远的距离。保守来说，我们还需要几万个量子位的距离需要攻克。通常来说，量子计算机可以被理解成是由比特表示的状态数的系统，比如53个量子比特计算机的2^53个状态。这可能说明，我们可以通过创建特别多的状态位，也就是使用量子计算来解决NP完全问题——也就是大力出奇迹。但不幸的是，目前我们无法证明量子计算机能够充分操控这些状态位，也就是不知道使用什么算法来解决NP完全问题，在这个角度上，这个问题已经超出了Grover的算法限制。自从2009年以来，我们在高效计算理论方面取得了一些重大的进展。虽然这些结果在解决P和NP方面没什么帮助，但是它们可能从一旁帮助理解相关的问题，并且启发后世的一些研究发展。一些NP问题无法表征为P（有效可解）或NP完全问题（与Clique问题一样难的问题）。我们之前讨论过的最著名的整数因式分解仍然需要指数级的时间来求解。对于另一个这样的问题，也就是图同构问题，我们最近看到了一些戏剧性的进展。图同构问题是指，人们可否找到两个图在统一表示下完全相同。具体举例来说，就像在Facebook中，当我们给定了两组1000人，我们能否将他们映射到另一个组中，在那个新组中好友的关系不变。（小A和小B是好友，在另一群人中A’和B’也是好友）这个图同构的问题在80年代中有了一些理论上的证明。在80年代，有人用交互式的方法证明了图同构问题不是NP完全的，而且它其实不是很困难，在一些实际的情况下，使用启发式的方法也能快速找到解决答案。尽管如此，我们仍然无法找到一个能够在所有场景中都快速找到解的算法。Laszlo Babai在2016年对该问题进行了深入研究，并发表了一种用于图同构的多项式时间的解决算法。简单来说，P中的问题在多项式时间内如果可以得到解决，也就是对于某个常数k，复杂度是n^k，其中n是输入的大小，比如每组的人数。拟多项式时间算法在时间n^(logn)k内执行，只比多项式时间差一点点，但起码比我们预计的NP完全问题所需要的2^n^ε的复杂性好的多。
