6种将永久改变计算的量子算法

　　人们将要迎来一个崭新的计算新时代，信息处理的基本单位不再只是经典比特，而是量子比特。这种转变为解决经典计算机无法有效解决的复杂数学问题开辟了广阔的新前景。
　　举个例子，谷歌量子计算机据说比当今最复杂的超级计算机快1。58亿倍这意味着布尔逻辑计算机需要十年才能完成的任务，这些计算机将能够完成三秒后。
　　以下列出的六种量子算法，突出了量子对经典世界的重大影响：秀尔算法
　　我们的整个数据安全系统都基于这样的假设，即对具有一千位或更多位的整数进行因式分解实际上是不可能的。直到PeterShor在1995年提出量子力学允许在多项式时间内执行因式分解，而不是使用经典算法实现的指数时间。
　　随着要因式分解的整数中的位数呈指数增长。另一方面，Shor算法是一种用于分解具有多项式运行时间的整数的量子算法，这意味着分解整数所需的时间仅随整数中的位数呈多项式增长。
　　这是AlexeyKitaev的Shor算法的一种变体，它减少了执行因式分解所需的量子比特数，但仍然能够将运行时间计时大约在d3左右。
　　格罗弗算法
　　格罗弗算法由一位印裔美国计算机科学家开发，被公认为继秀尔算法之后最重要的量子算法之一。它的主要用途是二次加速非结构化搜索问题，但它也可以作为一种有价值的工具或子程序，为各种其他算法获得二次运行时间改进。
　　假设您有一个包含N项的列表，并且您正试图在列表中找到一个唯一的项目。经典计算机需要平均检查列表中的N2个项目才能找到唯一的项目，在最坏的情况下，它必须检查所有N个项目。然而，对于量子计算，Grover的振幅放大可以将步数显著减少到大约N，这与经典算法相比是二次加速。
　　DeutschJozsa算法
　　DeutschJozsa算法是一种旨在解决DeutschJozsa问题的量子算法。这个问题涉及确定一个给定的布尔函数是恒定的（即，对所有可能的输入返回相同的输出）还是平衡的（即，对至少一对输入返回不同的输出），查询次数最少。
　　对于n位作为输入，经典算法需要最少两次调用最多2（n1）1才能确定给定函数是常数还是平衡函数，而量子计算机只需调用一次函数就可以解决这个问题f（x）。BernsteinVazirani算法
　　与DeutschJozsa问题一样，BernsteinVazirani算法也解决了一个特定的黑盒问题。该问题涉及在函数f（x）s中找到s。x，其中s是一些未知字符串，而。表示按位积（即AND）运算。
　　给定输入x，经典算法需要多次调用函数f（x）并使用结果一次确定s的位，需要调用n次函数才能恢复完整字符串。但是，只要调用函数f（x）一次，量子计算机就可以100地解决问题。西蒙算法
　　Simon的算法是第一个在解决特定问题时显示出与最佳经典算法相比呈指数加速的算法。
　　手头的问题涉及一个函数f（x），因为它只有两个结果要么将每个唯一的输入映射到一个唯一的输出（一对一），要么将两个不同的输入映射到一个唯一的输出（二对一））。此外，还有一个未知字符串s，对于所有输入字符串x，f（x）等于f（xs）。
　　如果s的值非零，则函数f是二对一的，而当s是零字符串时，函数f是一对一的。因此，目标是通过简单地找到秘密字符串s来确定函数f是一对一还是二对一。
　　通常，通过检查最多2（n2）次函数调用，可以确定地找到函数f的s值。但是，有了量子，使用指数级减少的查询只比n次调用多一点可以找到100确定的解决方案。量子相位估计（QPE）算法
　　QPE是一个重要的子程序，它是许多量子算法的核心构建块。该算法基本上估计酉算子的特征值的相位。换句话说，给定酉算子U和特征向量使得Ue（2i），其中是未知相位角，QPE的目标是估计。
　　它用于广泛的应用，包括量子模拟、量子化学和优化。