DAOrayaki DAO研究奖金池：
资助地址: DAOrayaki.eth
投票进展：DAO Reviewer 1/0 通 过
赏金总量：35 USD
研究种类：Quantum Computing, Subgraph Isomorphism Algorithm
原文作者: Qiskit
创作者：Sylvia@DAOrayaki.org
审核者：Sleepygirl@DAOrayaki.org
原文: Introducing: A quantum subgraph isomorphism algorithm
量子子图同构算法介绍
作者：Nicola Mariella¹、Anton Dekusar¹、Steve Flinter²、Mehrdad Maleki²、Prina Patel³、Ryan Mandelbaum⁴
有些计算任务表面上看起来很容易。例如，如果我给你一堆由随机排列的线连接的点，然后给你一个形状并让你在图像中找到它，你可能会做得很好。这个例子不仅仅是一个玩具问题——例如，解决它可以帮助金融机构发现洗钱计划。但这个问题对于经典计算机来说尤其具有挑战性。
在技术术语中，我们称这些问题为子图同构问题。子图同构问题适用于我们可以将数据表示为节点网络的应用，也称为顶点，由我们称为边的线连接。这些应用包括图数据库、生物化学、计算机视觉、社交网络分析、知识图查询，以及在我们的例子中，还包括洗钱。这是个 NP-Complete问题，这意味着我们不知道是否有有效的解决方案，但我们确实知道它是最难解决的问题之一，我们可以有效地检查提出的解决方案是否正确。也许量子计算机可以加快事情的进展。
在我们最近的论文中，我们设计了一种量子计算算法来解决子图同构问题。对于量子算法开发者来说，这是非常规问题，因为先前的研究表明，该问题的量子解决方案无法扩展。然而，在我们的新论文中，我们提出了一种量子算法，我们认为在中期内，量子算法可能比最佳经典算法更具优势。你们可以在这篇博文的底部找到相应的教程链接。
当然需要注意的是：目前尚不清楚量子计算机是否能够有效地解决（即在多项式时间内解决）NP-Complete 复杂性类别的问题，包括本文讨论的这个问题。许多研究人员怀疑他们无法做到。相反，我们根据其优于经典方法的能力来讨论该算法，而不是其有效解决 NP-Complete 的能力。你们可以在此阅读有关复杂性类别和量子计算机堆栈的更多信息：https://medium.com/qiskit/what-can-a-quantum-computer-actually-do-4daed0691f6b
在 IBM Quantum 和 Mastercard 的共同努力下，我们专门开展了这项工作，以开发一种可以区分洗钱计划和合法企业的量子子图同构算法。洗钱掩盖非法资金来源，例如非法武器销售或走私违禁品，犯罪分子可能通过欺诈或将资金转移到不太可疑的资产中进行洗钱。洗钱是一项复杂的活动，旨在通过以下几个步骤使交易看起来合法：放置，非法资金通过合法金融机构进入流通；分层，通过合法金融机构层层隐藏来源；整合，这些资金被整合为正常的商业或个人交易。
机构通过分析交易网络中重复的图形模式或图案来发现洗钱计划。该网络是一个无向图，由一组有限的节点和连接它们的无向边组成，例如由双向道路连接的城镇或由线连接的点。顶点用来表示账户，边是它们之间的交易。通过找到与洗钱相关的特定模式，我们可以确定资金的非法来源。在网络中找到这些重复的模式是一个子图同构问题。
我们首先用一个“邻接矩阵”来表示这个图，其中每一列（和每一行）代表一个顶点。如果一条边连接由行和列表示的顶点，我们将矩阵元素设置为 1，如果它们不连接，则设置为 0。该矩阵通过同时排列相应的行和列，提供了一种表示顶点排列的自然方式。
然后，我们有子图——图的一个子单元。想象一个图表看起来像一个基本的五角房子图——一个顶部有一个三角形的正方形——那么三角形就是这个图的子图。但是，即使外边缘形成五边形，五边形也不会是子图，因为房子图的顶点间有不包含在五边形中的连接。
三角形是中心图的子图。五角形则不是
对于这些子图，我们可以找到一个子图同构，一个函数。对于子图中由一条边连接的每一对顶点，它将它们映射到较大图上的对应顶点对，同时保留该邻接矩阵。通过足够的排列，你们可以在图的邻接矩阵中找到子图的邻接矩阵。
示例图及其邻接矩阵
子图同构的一个例子
设计一种用于查找子图同构的量子算法首先将邻接矩阵转换为我们可以在量子计算机上实现的东西——即将其转换为酉算子。我们引入了一个映射（我们在论文和教程中详细介绍了映射），它将邻接矩阵“扁平化”为一个对角矩阵，用于相同的目的。这种扁平化是我们加速的关键，它允许我们使用数十个量子比特来表示具有数百万个节点的图——随着矩阵大小的增加，我们只提供对数缩放。
由于我们为邻接矩阵创建了上述映射，因此我们还需要为作用于这个新矩阵的置换操作创建一个映射。我们首先定义了一个运算符，它将排列应用于我们未转换的邻接矩阵，当与我们的邻接矩阵相乘时，交换相应的顶点和边。然后，我们通过同样用来单独展平邻接矩阵的映射将这个置换算子作用于邻接矩阵。
为邻接矩阵的排列创建酉算子，使我们能够使用 VQE 创建一个子图同构算法。我们从两个图开始，一个较大的图 A 和一个较小的 B。我们使用这些经过变换的邻接矩阵作为 VQE 算法的拟设的一部分。我们将这个拟设解释为排列的叠加。这种叠加使用经典优化器设置的参数进行调整。我们设计的电路的输出是一个成本函数。我们使用经典优化器来最小化成本函数。当拟设实现一个排列或一组排列时，该函数被最小化，从而在 A 的子图和图 B 之间产生完美匹配。
我们通过下面的算法示例进行演示。我们首先从每个邻接矩阵中获取拟设，如下所示，它将返回一个 Qiskit QuantumCircuit，我们可以将其传递给 VQE 实现的构造函数。
（github 链接：https://gist.github.com/ryanfmandelbaum/c650da7f4a86f75adfbf38705194e188#file-subgr_ansatz-py）
在上图中，我们展示了拟设电路的框图，我们可以在其中欣赏各个组件。 PermAnsatz 块是排列叠加的生成器，由经典优化器通过参数向量 θ（未显示）控制。相反，QAdj 块分别对应于邻接矩阵 A 和 B 的单元表示。
下一步，我们分析下面代码片段中呈现的 VQE 流程的调用：
在初始化中，我们准备了经典优化器 SLSQP 和用于生成起点的随机数发生器。函数 trial() 是调用 VQE 程序的核心。在该函数中，参数的初始值在每次调用时都是随机的。优化问题是非凸的证明了这一点，因此算法在每次执行时都可能收敛到不同的解决方案。后一个事实表明，整个过程应该被解释为子图的抽样而不是精确匹配。
一对输入邻接矩阵 A 和 B，以及在左上角显示 B 的置换矩阵 A
输入图与来自上述矩阵的高亮解决方案
从上图中，应该可以看出算法的工作原理。该算法将拟设转换为置换矩阵 P，这样通过使用 P 及其转置作用于 A 的邻接矩阵 A，我们返回子图 B 的邻接矩阵 B 作为新置换 A 的主子矩阵——置换后的 A 是 B 的邻接矩阵，我们在 A 中找到了 B 对应的子图同构。如果我们没有得到一个包含所有 B 作为 A 左上角元素的矩阵，那么要么我们从一个无法表示与解决方案相对应的排列拟设开始，要么优化器就会卡在一个本地最小值，要么输入的图对没有子图同构。
大家可以在我们的 GitHub 教程和最近的这篇论文中看到我们算法的链接，并深入了解它的工作原理。我们很高兴看到其他社区成员更仔细地研究子图同构问题，看看我们可以通过哪些其他方式改进该算法，从而增强量子计算机解决这个问题的能力。
作者单位：
IBM 欧洲研究院——都柏林
Mastercard 爱尔兰公司
Mastercard 英国
IBM Quantum
通过 DAO，研究组织和媒体可以打破地域的限制，以社区的方式资助和生产内容。DAOrayaki将会通过DAO的形式，构建一个代表社区意志并由社区控制的功能齐全的去中心化媒体。欢迎通过文末方式提交与DAO、量子计算、星际移民、DA相关的内容，瓜分10000USDC赏金池！欢迎加入DAOrayaki社区，了解去中心化自治组织（DAO），探讨最新话题！
Media：https://media.daorayaki.org
Discord server: https://discord.gg/wNUPmsGsa4
Medium: https://medium.com/@daorayaki
Email: daorayaki@dorafactory.org
Twitter: @daorayaki_
微信助手：DAOrayaki-Media
小宇宙：DAOrayaki
详情请参考：
Dora Factory支持去中心化DAO研究组织DAOrayaki
DAOrayaki ｜DAOrayaki 开启去中心化治理2.0时代
DAOrayaki ｜风险投资的范式转移：无限主义基金和无限游戏
DAOrayaki ｜DAOrayaki dGov 模型：基于Futarchy的正和游戏
更多关于DAO的文章，关注Dorafactory，查看往期文章。
