有些计算任务表面上看起来很简单。例如,如果我给你一堆由随机排列的线条连接的点,然后给你一个形状并让你在图像中找到它,你可能会做得很好。这个例子不仅仅是一个玩具问题——例如,解决它可以帮助金融机构发现洗钱计划。但这个问题对于经典计算机来说尤其具有挑战性。
在专业术语中,我们称这些问题为子图同构问题。子图同构问题适用于我们可以将数据表示为节点网络的应用,也称为顶点,由我们称为边的线连接。这些应用包括图数据库、生物化学、计算机视觉、社交网络分析、知识图查询,在我们的案例中,还包括洗钱。这个问题是 NP 完全的,这意味着我们不知道是否有有效的解决方案,但我们确实知道它是最难解决的问题之一,我们可以有效地检查提出的解决方案是否正确。也许量子计算机可以加快速度。
在一篇论文中,研究人员设计了一种量子计算算法来解决子图同构问题。这不是量子算法开发人员尝试的常见问题,因为先前的研究表明该问题的量子解决方案实际上无法扩展。研究人员提出了另一种量子算法,他们认为,在中期内,这种算法有可能比最佳经典方法具有量子优势。
目前尚不清楚量子计算机是否能够有效地解决NP-Complete复杂性类的问题(即在多项式时间内解决),包括这一类。许多研究人员怀疑他们无法做到这一点。相反,我们根据其优于经典方法的能力来讨论该算法,而不是其有效解决 NP 完全问题的能力。
研究人员在 IBM Quantum 和 Mastercard 的共同努力下专门开展了这项工作,以开发一种可以区分洗钱计划和合法企业的量子子图同构算法。洗钱掩盖非法资金来源,例如非法武器销售或走私违禁品,犯罪分子可能通过欺诈或将资金转移到不太可疑的资产中进行洗钱。洗钱是一项复杂的活动,旨在通过以下几个步骤使交易看起来像合法的交易:放置(通过合法的金融机构将非法资金投入流通)、分层(通过合法的金融机构层层隐藏资金来源)和整合(将资金整合为正常的业务或个人交易)。
机构通过分析交易网络中重复的图形模式或图案来发现洗钱计划。该网络是一个无向图,由一组有限的节点和连接它们的无方向边组成,例如由双向道路连接的城镇或由线连接的点。顶点用来表示账户,边是账户之间的交易。通过找到与洗钱相关的特定模式,我们可以确定资金的非法来源。在网络中找到这些重复的模式是一个子图同构问题。
我们首先用一个“邻接矩阵”来表示这个图,其中每一列(和每一行)代表一个顶点。如果一条边连接由行和列表示的顶点,我们将矩阵元素设置为 1,如果它们不连接,则设置为 0。该矩阵通过同时排列相应的行和列,提供了一种表示顶点排列的自然方式。
然后,我们有子图——图的一个子单元。如果你想象一个图表看起来像一个简陋的五角形的房子——一个顶部有一个三角形的正方形——那么三角形就是这个图的子图。但是,即使外边缘形成五边形,五边形也不会是子图,因为房子在顶点之间引入了不包含在五边形中的连通性。

三角形是中心图的子图。五角大楼不是。
对于这些子图,我们可以找到一个子图同构,一个函数,对于子图中由一条边连接的每一对顶点,它将它们映射到较大图上的对应顶点对,同时保留该邻接矩阵。通过足够的排列,您可以在图的邻接矩阵中找到子图的邻接矩阵。

示例图及其邻接矩阵

子图同构的一个例子
设计一种用于寻找子图同构的量子算法,首先将邻接矩阵转换为我们可以在量子计算机上实现的东西——也就是说,将其转换为酉算子。我们引入了一个映射,它将邻接矩阵“扁平化”为一个对角矩阵,以达到相同的目的。这种扁平化是我们加速的关键,它允许我们使用数十个量子比特来表示具有数百万个节点的图——随着矩阵大小的增加,我们只提供对数缩放。
由于我们为邻接矩阵创建了上述映射,因此我们还需要为作用于这个新矩阵的置换操作创建一个映射。我们首先定义了一个运算符,它将排列应用于我们未转换的邻接矩阵——一个运算符,当与我们的邻接矩阵相乘时,交换相应的顶点和边。然后,我们通过我们用来单独展平邻接矩阵的相同映射将这个置换算子作用于邻接矩阵。
为邻接矩阵的排列创建一个酉算子,允许我们使用VQE创建子图同构算法。我们从两个图开始,一个较大的图A和一个较小的图B。我们使用这些经过变换的邻接矩阵作为 VQE 算法的 ansatz 的一部分。我们将这个 ansatz 解释为排列的叠加。这种叠加使用经典优化器设置的参数进行调整。我们设计的电路的输出是一个成本函数。我们使用经典优化器来最小化成本函数。当 ansatz 实现一个排列或一组排列时,该函数被最小化,从而在 A 的子图和图 B 之间产生完美匹配。
我们通过下面的算法示例进行演示。我们首先从每个邻接矩阵中获取 ansatz,如下所示,它将返回一个Qiskit量子电路,我们可以将其传递给VQE实现的构造函数。
from qsubgisom import ansatz
qc, params = ansatz(adj1, adj2, topology='circular') qc.draw('mpl')

在上图中,我们展示了 ansatz 电路的框图,我们可以欣赏其中的组件。PermAnsatz 块是排列叠加的生成器,由经典优化器通过参数向量θ(未显示)控制。相反,QAdj 块分别对应于邻接矩阵 A 和 B 的幺正表示。
下一步,我们将分析VQE过程的调用,如下面的代码片段所示:
# Initialization
max_trials = 3
qi = QuantumInstance(Aer.get_backend('statevector_simulator'), seed_transpiler=seed, seed_simulator=seed, shots=1024)
rng = np.random.default_rng(seed=seed) # RNG
optim = SLSQP(maxiter=1000) # Init classical optimizer.
def trial():
# Randomize initial parameters.
initial_point = (rng.uniform(size=len(qc.parameters)) - 1/2) * np.pi
vqe = VQE(qc, quantum_instance=qi, initial_point=initial_point, optimizer=optim) obj = vqe.compute_minimum_eigenvalue(observable(qc.num_qubits))
return obj.optimal_value, obj
# Run a number of trials and select the one presenting # the least minimum eigenvalue.
results = [trial() for _ in tqdm(range(max_trials))]
results = sorted(results, key=lambda obj: obj[0])
result = results[0][1]
在初始化中,我们准备了经典优化器 SLSQP 和随机数生成器来生成起始点。函数 trial() 是调用 VQE 的过程的核心。在这样的函数中,参数的初始值在每次调用时都是随机的。优化问题是非凸的这一事实证明了这一点是合理的,因此算法在每次执行时都可能收敛到不同的解决方案。后一个事实表明,整个过程应该被解释为子图的抽样而不是精确匹配。

一对输入邻接矩阵 A 和 B 以及在左上角显示 B 的置换矩阵 A

具有上述矩阵中突出显示的解决方案的输入图
从上图可以清楚地看出算法是如何工作的。该算法将 ansatz 转换为置换矩阵 P,通过使用 P 及其转置作用于 A 的邻接矩阵A ,我们返回子图 B 的邻接矩阵B作为新置换A的主子矩阵——变换后的 A是B的邻接矩阵,我们在 A 中找到了 B 对应的子图同构。如果我们不得出一个包含所有B作为A的矩阵的左上角元素,那么要么我们从一个无法表示与解决方案对应的任何排列的 ansatz 开始,要么优化器陷入局部最小值,要么输入的图对没有子图同构。
感兴趣的朋友可以在GitHub 教程和这篇论文中看到算法的链接,并深入了解它的工作原理。我们很高兴看到其他社区成员更仔细地研究子图同构问题,并看到我们可以通过其他方式改进这个算法,以增强量子计算机解决这个问题的能力。
原文链接:https://medium.com/qiskit/introducing-a-quantum-subgraph-isomorphism-algorithm-7bd860415422
---煤油灯科技victorlamp.com翻译整理---