- 3blue1brown的 Grant Sanderson 发布了一段精彩的 YouTube 视频，解释了 Grover 的算法，并消除了人们对量子计算的基本误解，认为 QC 的工作原理只是“并行尝试所有可能性”。让我不要胡思乱想：这个视频在 36 分钟内解释了我 20 年来在这个博客上一遍又一遍地试图解释的内容……而且它做得更好。这是一部杰作。是的，我就这个视频咨询了格兰特（他想要我的直觉“为什么答案是√N？”），我什至在它的结尾有一个客串，但我希望我制作了这个视频。该死的，格兰特！
- 无比伟大、多产的博客作者Zvi Mowshowitz和您真正花了 1 小时 40 分钟讨论人工智能的存在风险、教育、博客等。我最终“采访”了兹维，他说了大部分话，这对我来说很好，因为他有很多重要的事情要说！ （其中：那个。）非常感谢 Rick Coyle 安排这次谈话。
- 量子复杂性理论取得进展！ 2000 年， John Watrous 证明了群组非成员问题属于复杂度类别QMA（Quantum Merlin-Arthur） 。换句话说，如果某个元素 g不包含在通过黑匣子指定的指数大有限群 G 的给定子群 H 中，则有一个简短的量子证明 g∉H，仅具有 ~log|G|量子位，可以在量子计算机上以 log|G| 的时间多项式进行验证。这很快就提出了一个问题，即是否可以使用团体非会员制来通过预言机将 QMA 与 QCMA 分开，其中QCMA（Quantum Classical Merlin Arthur）由Aharonov 和 Naveh在 2002 年定义，是 QMA 的子类，其证明需要是经典的，但验证过程仍然可以是量子的。换句话说，团体非会员资格是否可以成为量子证明真正有帮助的第一个非量子例子？
唉，2006 年， Greg Kuperberg 和我表明答案可能是“否”：组非成员资格具有“多项式 QCMA 查询复杂性”。这意味着有一个 QCMA 协议来解决 Arthur 只生成 polylog|G| 的问题。对群组预言机的量子查询——尽管可能是log|G| 中的指数除此之外还有量子计算步骤的数量！为了证明我们的结果，格雷格和我需要适度使用有限简单群的分类，这是 20 世纪数学的最高成就之一（其证明大约有 15,000 页长）。我们推测（但无法证明）其他比我们更了解分类的人可以证明团体非会员资格完全属于 QCMA。
现在，近 20 年后， François Le Gall、Harumichi Nishimura 和 Dhara Thakkar 终于证明了我们的猜想，表明团体秩序以及团体非会员资格确实存在于 QCMA 中。他们确实需要使用分类，对分类涵盖的几乎所有有限群做一件事，但对“Ree型”群（无论它们是什么）做另一件事。
有趣的是，组成员问题也是将BQP/qpoly或具有多项式大小的量子建议的量子多项式时间（我个人最喜欢的复杂性类别）与BQP/poly或具有多项式大小的经典建议的相同事物分开的候选者。可以想象，它仍然可能是！作者向我解释说，他们的协议没有将组成员资格（组 G 和子组 H 仅取决于输入长度 n）放入 BQP/poly 中，原因是他们对 g∉H 的简短经典见证同时依赖于 g和H，与 Watrous 的量子见证相比，它仅依赖于 H。所以这里还有很多开放的内容！事实上，就这个问题而言，我不知道有什么充分的证据表明整个小组成员问题不在 BQP 中——也就是说，量子计算机不能在没有 Merlin 或目击者的情况下直接解决整个问题！
不管怎样，衷心祝贺勒加尔、西村和塔卡进一步揭开了我们对这些问题的无知！哎呀哎呀！
- 量子算法潜在的重大进展！ Vittorio Giovannetti、Seth Lloyd 和 Lorenzo Maccone (GLM) 给出了一种量子算法来估计 n×n 矩阵 A 的行列式，在某些情况下，其速度比我们知道的经典方法要快得多。该算法与 2008 年用于求解线性方程组的HHL (Harrow-Hassidim-Lloyd)量子算法密切相关。这意味着任何了解此类量子算法历史的人都知道要立即问：细则是什么？几周前，当我访问哈佛大学和麻省理工学院时，我有机会见到了塞思·劳埃德，所以我问了他，他友善地告诉了我。首先，我们假设矩阵 A 是 Hermitian 且半正定的。接下来，我们假设 A 是稀疏的，不仅如此，还有一个QRAM数据结构指向它的非零条目，因此不需要进行 Grover 搜索等来找到它们，并且可以以相干叠加的方式查询它们。最后，我们假设 A 的所有特征值至少是某个常数 λ>0。然后，该算法将 det(A) 估计为乘法误差 ε，时间与 log(n) 成线性比例，并与 1/λ 和 1/ε 成多项式。
现在，我留给雄心勃勃的读者提出的挑战：是否有一种经典的随机算法可以在相同的假设和可比的运行时间下估计行列式？换句话说，GLM算法可以“Ewinized”吗？赛斯不知道，我认为这是一个非常棒的开放式问题！一方面，如果 Ewinization 是可能的，那么该博客上的宣传导致诱人的量子加速被残酷谋杀就不是第一次了。另一方面……好吧，也许不是！我还认为 GLM 解决的问题（对于指数大、隐式指定的矩阵 A）可能是BQP 完全的，例如 HHL 解决的一般问题。例如，这意味着可以将 Shor 的因式分解算法嵌入到 GLM 中，并且除非 P=BQP，否则不可能对其进行反量化。 （尽管如此，就像 HHL 算法一样，我们仍然面临这样的问题：GLM 算法是否“独立有用”，或者它是否仅仅再现了已知的量子加速。）
不管怎样，量子算法研究还活着！反量化研究也是如此！如果美国的基础科学能够继续下去——我承诺在这篇文章中不会谈论这一点——那么在接下来的几年里，我们将有很多事情让我们忙碌。