典型的量子算法不包括什么

量子退火算法。

量子退火算法的提出者是西森教授，人类第一个商用量子计算机Dwave和另一个非常重要的算法量子退火。

典型量子算法包括：1、Shor算法。2、Grove算法。3、HHL算法。4、量子机器学习与深度学习算法。2015年，潘建伟教授团队在小型光量子计算机上，首次实现了量子机器学习算法。

量子计算是一种基于量子物理学的计算形式。经典计算机依靠位（零或一）进行计算，而量子计算机使用利用量子力学以“叠加”形式存在的量子位（量子位）：零和一的组合，每个都有一定的概率。例如，一个量子位可能有 80% 的几率为零，20% 的几率为零。或者 60% 的机会为零，40% 的机会成为 1。等等。

1980 年代，物理学家保罗·贝尼奥夫 (Paul Benioff) 首次提出了量子计算的概念。不久之后，理论物理学家理查德·费曼和数学家尤里·曼宁率先提出量子计算机可以解决经典计算机无法解决的问题。事实上，在 1990 年代，数学家 Peter Shor 开发了一种算法，量子计算机可以用它来破解公钥密码学：“ Shor 算法”——如果量子计算机变得足够强大的话。

2019 年 10 月，经过数十年的研究，谷歌正式宣称已达到“量子霸权”。这实质上意味着量子计算机解决了经典计算机无法解决的问题。或者，更具体地说，它在 200 秒内解决了一个问题，即使是最强大的经典超级计算机也需要 10,000 年才能解决。

虽然这是一个重大突破，但量子计算机似乎离运行 Shor 的算法还有很长的路要走。一方面，目前的量子计算机还不够强大，而且不清楚扩大这项技术的难易程度。此外，要真正发挥作用，量子计算机依赖于一种称为“纠错”的技术解决方案，这仍然是一个挑战。

预测这项技术的未来发展很困难，但可以运行 Shor 算法的量子计算机可能需要数年甚至数十年的时间——也许它们根本不可能实现。

如果量子计算机能够运行 Shor 算法并破解公钥密码学，那么比特币确实可能会受到攻击。具体来说，一些硬币可能会被盗。

然而，有些人认为盗窃会受到一定程度的限制。虽然所有硬币都由公钥加密（目前是 ECDSA 算法）保护，但大多数硬币也由 SHA256 散列算法保护。只有当这两种算法都被破解时，所有硬币才能彻底被盗，但目前看来 SHA256（或任何其他哈希算法）似乎无法被量子计算机破解。

也就是说，大量的硬币只能通过公钥密码术来保护。目前的估计表明，如果公钥密码体制被破解，大约 500 万比特币将被盗。以下是比特币可能面临风险的一些情况：

事实上，即使比特币同时受到公钥和哈希的保护，在“量子世界”中安全地使用这种比特币也可能是一个挑战。当用户尝试花费他们的比特币并通过比特币网络传输交易时，攻击者将有机会尝试窃取资金。此时，攻击者可以在交易确认之前尝试破解公钥加密，然后将比特币重新发送到他自己的地址之一。

我只想说，如果量子计算机突然变得比任何人预期的都要强大，比特币就会有问题。

需要注意的是，如果可以运行肖尔算法的量子计算机突然出现，比特币不太可能成为第一个或主要的目标。公钥加密可以保护世界上几乎所有其他数字信息，包括军事情报、银行数据和其他现有金融基础设施、通信网络等。

是的，比特币协议可以升级为抗量子。

简而言之，比特币的签名算法将不得不被量子抗性签名算法所取代。由于隔离见证的激活，比特币的签名算法可以通过向后兼容的软分叉升级相对容易地被替换。（当前的 ECDSA 签名算法可能会在不久的将来通过软分叉被 Schnorr 签名算法部分取代。）

升级后，用户应该将他们的比特币迁移到新地址，以便受到抗量子签名算法的保护。在量子计算机可以运行 Shor 算法之前，没有及时迁移的用户将面临比特币以某种方式被盗的风险。

如果比特币没有及时转移到安全地址，比特币协议也可能会升级以阻止比特币被消费。这种措施意味着原始所有者也会丢失比特币——但是，当然，无论如何，他们很可能会将比特币丢失给攻击者。（有人建议，这些比特币可能会被其合法所有者通过零知识证明密码术解锁——但这仍然是非常投机的。）

鉴于量子计算的当前发展状况，预计比特币将有足够的提前警告，表明需要进行升级。专家认为，我们还没有接近那个时间点。

量子计算机或许能够比传统计算机更快地挖掘比特币。然而，因为比特币挖掘是基于散列（而不是公钥密码学），所以它可能不会被破坏到任何有意义的程度。

相反，量子计算的出现可能会导致一场新的军备竞赛，以建立最快的采矿硬件，直到找到新的平衡点。当 GPU 取代 CPU 和 ASIC 取代 GPU 时，比特币挖矿格局已经发生了类似的演变。

以下内容参照微软研究院主题演讲《Quantum Computing for Computer Scientists（计算机科学家量子计算导读）》的结构进行整理和扩充的。

本篇是第六部分。上一篇 【科普】量子计算通识-5

量子计算能做什么？有什么优势？

我们从最简单的多伊奇问题开始。

首先，我们知道，对于一个比特进行操作，有四种方法：不变，翻转，等0，等1，它们都可以表示成用一个矩阵相乘的模式。

这四种操作又可以根据输入输出的对比分为两种情况：

现在问题是，假设有一个函数操作 ，我们只知道它是四种操作里的一种，但我们可以用输入输出进行测试，那么，要确定 属于情况A（变量可逆）还是情况B（常数不可逆），我们最少做几次测试？

这个问题最早是英国物理学家David Deutsch提出来的，当然他也提出了量子算法的解决方案。

用经典计算机来判断 到底是情况A（变量结果操作）还是情况B（常量结果操作），必须要经过两次尝试，第一次输入0观看结果，第二次输入1观看结果。

所以，必须至少尝试两次，第一次输入0，第二次输入1或者相反：

我们经过两次经典计算可以确定 属于变量操作或者常量操作。

在量子计算中我们要求所有操作都是可逆的，那么我们先对四种位操作进行重新布线，也就是说设计四种可逆的量子位操作线路，或者说四种算法。当然，这四种算法也必须满足实现四种操作：

在这里我们输入两个量子位InputA和InputB，其中InputA是固定的|0>，你可以把它视为冗余的辅助输入；同样输出的OutputA是真正的操作结果，而OutputB也可以视为冗余的副产品。

为什么设计成这样的线路？先不急，我们先看在这个结构下如何实现四种可逆的量子位操作。

注意上面四个图的OutputA，分别是|0>、|1>、|x>、|﹁x>，这正对应了量子比特的四种操作。

有了上面四种操作全新的可逆线路算法，我们用一次测试就可以确定 是变量操作还是常量操作了。

首先我们把 当做一个未知的黑盒子，并向两端增加一些翻转操作（X）、Hadamard门操作（H）和一些测量Measure操作（M），组成下面的测试电路：

从图中可知，我们的两个输入InputA和InputB都是|0>，那么我们来看一下在等0、等1、不变、翻转四种不同的操作情况下输出的结果都是什么。

在此之前，我们先把左侧的翻转（X）和Hadamard（H）处理出来：

InputA和InputB，都是|0>，经过-X-H-后得到 ：

我们把这个点作为进入未知黑盒 的起点，下面用蓝色圆点表示。

但OutputA是怎么回事？首先我们知道这是个CNOT可控非门操作，而CNOT就是乘以一个特别的矩阵，我们有如下公式：

注意这里最后一步的巧妙之处在于开头的CNOT操作相当于把两个 的张量积转换为 和 的张量积，简化后就是：

所以有上图，OutputA是 测量后是|0>，联合OutputA和OutputB仍然得到|01>

综合上面四种情况，我们得到：

所以，输入InputA和InputB两个都是|0>，如果结果是|11>，那么 就是个常量操作，如果结果是|01>，那么 就是个变量操作。

只要一次操作就完成了！速度快了一倍！

下一篇： 【科普】量子计算通识-7-Deutsch算法解析

END

---