DAOrayaki ｜可能改变世界的5种量子算法

Quantum Computing

a year ago • 18 min read

DAOrayaki ｜可能改变世界的5种量子算法

Quantum Computing

a year ago • 18 min read • Loading Views

DAOrayaki DAO研究奖金池：

资助地址: DAOrayaki.eth

投票进展：DAO Reviewer 1/0 通过

赏金总量：80 USD

研究种类：Quantum Algorithms

原文作者: Anastasia Marchenkova

创作者：xingyang@DAOrayaki.org

审核者：Yofu@DAOrayaki.org

原文: 5 Quantum Algorithms That Could Change The World

DAOrayaki 是一个去中心化的研究者组织和去中心化媒体，通过 DAO的形式去中心化地资助世界各地的研究者进行研究、翻译、分析等工作。DAOrayaki 由早期的 DAO 组织 DAOONE 核心成员发起，得到了Dora Factory基础设施的支持。欢迎通过文末方式提交DAO的研究，瓜分10000USDC赏金池！了解去中心化自治组织（DAO），探讨最新治理话题，关注DAO的发展趋势，欢迎加入DAOrayaki社区！

FX电视剧集《开发者》Devs中的量子计算机

量子计算将帮助我们创造一个更好的世界，还是带来破坏？

量子计算机的工作方式不是一次性遍历。

量子计算机不能更快地处理所有问题。

它处理特定问题的速度更快。

目前只有几十种量子算法。在传统的术语中，算法的意思是一组普通指令。但加上量子二字的算法是指利用到量子特性的指令，这有可能比传统计算机能更快地解决一些数学问题。

尽管现有的量子算法数量并不多，但是已经能对我们关心的很多问题带来巨大的影响。

变分量子本征求解（VQE）和化学模拟

Variational Quantum Eigensolver是可以模拟分子和化学反应的基础算法。

在化学中，原子和分子的属性可以通过解决薛定谔方程来找到。你添加的原子越多，问题就越难解决，哪怕仅仅几个原子，想精确计算都非常耗时。我们可以采用近似解决方案，但是一旦你增加到几十个原子，传统计算机就无法再有效地完成这些问题。

VQE所做的是计算一个矩阵的特征值。而且它能胜任大型矩阵的计算，这意味着我们能以一种传统计算机无法做到的方式计算大分子的这些属性。

那么到底什么是特征值呢？

矩阵 M 的特征值是一个标量 λ，使方程 Mv = λv 的矩阵 m 乘以特征向量有一个非平凡解。

我们在这个计算中使用的矩阵是表示哈密顿的矩阵。哈密顿描述了原子和分子系统的总能量，即所有的原子和它们之间的相互作用。

这个量子子程序有两个步骤。

准备好量子状态拟设（Ansatz)
测量期望值——如果你熟悉机器学习，可以把它看作是“代价函数”

我们从一个Ansatz开始——指一个有根据的猜测或假设。在模拟分子和寻找基态能量的问题上，我们从对该量子态的猜测开始。

诀窍是准备好这个Ansatz——最好猜准一点。这个VQE算法是混合型的，它在经典优化循环中嵌套一个量子步骤，以帮助准备量子状态。然后开始循环的过程，直到我们找到哈密顿的最小特征值，或系统的状态，也就是最低的基态能量。

现在你知道为什么它被称为“变分”了。这是一种数学分析，它使用变化，也就是函数的微小变化，来寻找最大值和最小值。这很适合我们在这里求期望值的最小化。

值得注意，由于变分原理，这个期望值大于哈密顿 H 的最小特征值。量子子程序测量该期望值，并使其更接近哈密顿的最小特征值，这就是我们正在寻找的基态能量。

然后，我们可以在其他计算中使用这个最小能量，比如对波函数（用于代表分子）随时间的演变进行建模。

在化学之外，大型特征值问题的求解会有更多的应用，并切实影响我们的日常生活，比如设计新材料，可以是发现新的耐高温和应力、适合用于飞机的材料，帮我们飞得更快，也可以是制造出更高效的电池。

我们即将进入噪声中等规模量子（NISQ, Noisy Intermediate Scale Quantum）装置时代。我们的芯片有几十个到几百个物理量子比特，但错误率高而相干时间短，可能需要大量的纠错。

然而，像VQE这样的算法只需要少量的量子比特就可以工作。它也是一个“浅层”电路，这意味着它没有大量的时序门。

这很重要，因为量子信息只能储存很短的时间，称为“相干时间”。我们需要在量子比特解聚（或失去其量子状态）之前应用所有的门并读出数据。电路越深，相干时间越长。VQE的工作方式是使用量子计算机计算数据的某些部分，将该信息反馈给传统计算机，然后循环往复。这就是我们所说的经典—量子混合算法。

因此，如果我们没有大量的按顺序操作的门，那么我们需要更短的相干时间！

其他变分算法的例子包括变分量子分解（VQF, Variational quantum factoring）——以新的方式对RSA加密进行数字分解。还有量子近似优化算法（QAOA, Quantum approximate optimization algorithm），它可以应用于调度问题（scheduling problem）。

量子无约束二元优化（QUBO）

量子退火器是为了将 QUBO 和 Ising 问题有效地移植到量子硬件上而建的。旅行推销员问题、调度问题、优化安置问题、图形着色问题，甚至游戏优化都可以在这些量子系统上有效解决。

这非常有用，因为效率很重要。

二元目标函数，也就是QUBO可以有效解决的目标函数，可以被视为图。这个图可以转化为量子芯片的拓扑结构。所以你可以带着这个最优化问题，构建我们需要最小化的哈密顿方程。

𝐻 (𝑎, 𝑏) = 5𝑎 + 7𝑎𝑏 − 3𝑏

你可以用图形来表示，节点a和b表示城市，每个城市销售的时间作为权重体现在等式中，它们之间的边a-b表示距离，权重为7。

该函数的最小化就是系统的“最低能量状态”。

现实中，这在量子退火器上是如何工作的？我们施加一个磁场来控制量子比特的叠加，改变它是1或0的概率。权重由量子比特的叠加来控制。你可以调整耦合器，将两个量子比特关联起来，这相当于旅行推销员中城市之间的距离。

对于最优化问题来说，你可以把它看作是在一个景观中寻找最低点。最低能量的配置是这些QUBO问题的“最优”解决方案。

量子机器学习算法

量子机器学习和研究，可以有不同的路径：

量子计算机上的量子机器学习算法
受到量子力学启发的经典算法
基于量子数据的经典机器学习

所有这些都属于“量子机器学习”的范畴。

量子机器学习的一个主要研究方向是开发已知经典机器学习算法的量子版本。然而，另一个方向是制造新的量子算法——完全采用量子步骤。

但你也可以在机器学习中拥有量子子程序。一个想法是让量子子程序准备好传统计算机可以更有效地处理的数据，或加快训练中的瓶颈部分。现有研究正在寻找K-NN邻近算法、SVM支持向量机和其他经典机器学习算法的量子版本。

另一个有趣的途径是“量子学习”。量子技术将如何处理输入—输出，或者优化参数，并找到一个新的有效学习策略？我们甚至不知道如何以量子的方式表示数据。

有一些关于量子版神经网络的建议。他们中的大多数人都在使用Hopfield网络，这对于关联记忆的相关任务来说非常强大，该网络更多源自神经科学而非机器学习。

其他方法还有，使用量子模糊前馈网络（quantum fuzzy feed forward networks），或用绝热计算进行模式识别。

任何机器学习算法都有非凡潜力，我们已经看到了机器学习的巨大影响。谷歌页面排行是机器学习的最早例子之一，它今天统治着我们的生活。

现在任何人都可以用几行代码很容易地训练一个神经网络。但世界上有很多数据，而且还在不断增加。我们希望量子计算可以帮助处理或产生更有效的算法。

Grover高效搜索算法

未排序数据库的搜索复杂度为O(n)，使用大O符号。

Grover算法需要的时间是sqrt(N)，也就是根号N，是搜索未排序数据库最快的量子算法。

当谈到Grover的算法搜索速度更快，有时会被解读成 “哦！它只是用了并行处理！”，但事实并非如此。正确的解读是，Grover的算法并没有搜索得更快，它只是使用了逆函数。

当你有一个函数，对其中一个输入返回“真”，而对所有其他的输入返回“假”时，Grover算法就适用。该算法的工作是找到返回“真”的那一个。它实际做的是搜索函数的输入值，直到找到使函数返回“真”的那一个。

逆函数与数据库的搜索很像，因为我们可以造出这样的函数：如果所查与数据库中的条目相匹配，则产生一个特定的值（例如“真”），而对其他值则产生另一个值（“假”）。

因此，即使Grover能更快地搜索，问题是——你的应用有办法映射到量子系统上吗？分子在量子态上的映射比较清晰，但是其他场景呢？比如说，我们要搜索单词，你怎么把一个单词映射到一个量子态上？

所以，尽管Grover的算法可以用于搜索，但这并不代表我们可以加快任一种搜索。Grover算法的威力将体现在传统搜索无法到达的领域。

在这些问题中，Grover算法可以发挥作用，但在经典算法中难度成倍提高，典型的例子是旅行推销员和图形着色问题（例如，你必须用三种颜色给地图着色，并确保相同的颜色不相接触）。虽然Grover的算法并不适用于每一个搜索函数，但人们正在研究如何利用Grover的算法来解决NP完全问题。

用于快速数字因式分解的Shor算法

两个常见的密码系统是Rivest-Shamir-Adleman（RSA）和椭圆曲线加密（ECC）。当你上网时，你所交换的任何信息通常都使用这两种加密方式。他们都容易受到量子计算机的攻击。

例如，RSA依靠的是数字因式分解的复杂度。将两个质数相乘很容易，但取一个大数并对其进行因式分解以得到这两个质数就很难了。用一台传统计算机对一个4096比特的密钥进行因式分解，需要的时间比宇宙的年龄还要长。

Shor的算法可以找到一个数字的质因数，并且可以比传统计算机更容易地 “解开”这个因式分解问题。而这个算法是在1994年发明的！Shor算法的工作原理是通过寻找一个函数的“周期”。

函数的周期是指当你给定一些输入时，结果会上升和下降，就像一个频率波。

如果我们有一个快速找到某个已知的周期函数的周期的方法，我们就可以快速找到因子。

f(x) = m^x (mod N)

Shor算法有5个步骤，但只有这一个步骤是量子计算。（译注：下图Step 2，也就是查找周期那一步）

我们有一个熟悉的与频率和时间有关的经典函数，叫做傅里叶变换。我们也有一个量子版本，叫做量子傅里叶变换。傅里叶变换从时域映射到频域（傅里叶）。而频率正是我们在这里想知道的。

破解加密算法是一个相当大的问题。我们必须找到能抵御量子计算攻击的新加密技术。

要破解一个RSA密钥，大约需要4000个量子比特。然而，这些是完美的、“逻辑的 ”量子比特。由于纠错的原因，我们需要更多的物理量子比特。John Preskill 在他关于量子信息的演讲中指出，我们需要的是有1,000万个物理量子比特和1万个逻辑量子比特的量子计算机。虽然还远谈不上实现，但也要从长远考虑。

这使得量子计算成为一项有很多潜在未来影响的技术，甚至不仅网络安全和电信方面的用例。尽管我们只有几十个量子算法，但它们能产生的影响是广泛的，因为最优化和搜索问题真的无处不在。

你也可以参考 quantumalgorithmzoo.org，有量子算法的列表。

即使只是能够模拟量子态，在化学、材料和能源方面也有很多应用。随着我们研究出更多的算法，它们可以帮助解决最优化和调度问题，以后或许还包括搜索问题。而我们如何将问题转换到哈密顿路径问题上，是任何量子算法及其威力的关键。

请看我在YouTube上谈论这些量子算法的视频。

【嵌入视频】https://www.youtube.com/watch?v=_54i80UFHSs

参考链接

1.变分原理：

https://en.wikipedia.org/wiki/Variational_method_%28quantum_mechanics%29

2.关于量子信息的演讲中：

https://www.youtube.com/watch?v=Q4xBlSi_fOs

通过 DAO，研究组织和媒体可以打破地域的限制，以社区的方式资助和生产内容。DAOrayaki将会通过DAO的形式，构建一个代表社区意志并由社区控制的功能齐全的去中心化媒体。欢迎通过文末方式提交与DAO、量子计算、星际移民、DA相关的内容，瓜分10000USDC赏金池！欢迎加入DAOrayaki社区，了解去中心化自治组织（DAO），探讨最新话题！

官方网站：daorayaki.org

Discord server: https://discord.gg/2UjpmPH9

Medium: https://medium.com/@daorayaki

Email: daorayaki@dorafactory.org

微信助手：DAOrayaki-Media