量子退火方法用于解决高密度采样形状的形状对应关系问题

7586NPNP联系我们Q-Match：通过量子退火的Marcel Seelbach Benkner1Zorah L¨ ahner1Vladislav Golyanik2Christof Wunderlich1Christian Theobalt2迈克尔·穆勒11锡根大学2MPI for Informatics，SIC给定两个循环C1，C2，我们1Q-MatchQGM [62]α11- α1000年01月01日参数化所有组合0α11α1、α2的所有选择的可能排列：231452314523145（一）（二）α1= 0，α2= 0α1= 0，α2= 1α1= 1，α2= 0α1= 1，α2= 1图1.（i）通过两种量子方法获得的示例对应关系，提出的Q-Match（左，502个点）和QGM [62]（右，三个点）。具有相同颜色的顶点彼此映射 我们的迭代方法直接在空间中的排列，因此可以处理更多的顶点相比，QGM。（ii）我们通过一组循环来表示排列，这允许我们通过二进制变量来参数化它们，而不需要强制执行任何类型的约束（右上）。 Q-Match决定是否应应用每个循环Ci（αi = 1）或不应用（αi = 0）以向较低能量解前进。摘要寻找形状对应关系可以被公式化为一个硬二次分配问题（QAP），对于具有高采样密度的形状是不可行的。一个有前途的研究方向是用量子退火来解决二进制变量上的二次优化问题不幸的是，通过惩罚符号在QAP中强制执行线性等式约束1. 介绍形状对应是许多计算机视觉和图形应用的核心，因为知道点之间的关系允许将信息传递到新的形状。虽然这个问题已经存在了很长时间[41]，但非刚性变形形状的设置仍然具有挑战性[20]。 一个原因是两个形状中的n个点的通用匹配可以被公式化为一个非困难的二次分配问题（QAP）。Iicantly限制了这种方法在当前可用的量子硬件上的成功概率。为了解决这一限制，本文提出了Q匹配，即，一种新的迭代minX∈Pn E（X）：=xTWx，（1）量子方法的QAP启发的α-展开算法，它允许解决问题的数量级大于目前的量子方法。它通过以循环方式更新当前估计来隐式地强制执行QAP约束。此外，Q-Match可以迭代地应用于精心选择的对应关系的子集，允许我们扩展到现实世界的问题。使用最新的量子退火，D-波的优势，我们评估所提出的方法QAPLIB的一个子集，以及从FAUST数据集的等距形状匹配问题。其中x=vec（X）是n个2维向量cor。响应于排列集合P中的矩阵0，1n×n和WRn2×n2是描述匹配对之间某些成对性质保持得如何好 对于W的一些选择和假设在输入形状上，（1）可以通过添加先验知识和利用几何结构而变得可行例如，刚性形状可以仅通过旋转和平移来对齐一一这是仅具有六个自由度的问题。对于一般情况，QAP仍然具有挑战性。有两个二元变量α1，α20001- α2α2000α21- α27587不超过在这项工作中，我们提出了一种新的形状匹配的方法，采用量子退火，发现高质量的解决方案，具有高概率的QAP，是适合于现实世界的问题。近年来，量子计算机取得了重大进展，如IBMQ System One（电路模型）和D-Wave Advantage System 1。1（绝热，量子退火）成为可用于研究目的。基于电路的模型和绝热模型在理论上是多项式等价的[1]。然而，当前的实现方式有很大的不同，并且有不同的挑战要克服。绝热量子计算的一个优点是它对噪声和退相干不太敏感[16]。不幸的是，绝热量子计算机（AQCer）只能先验地解决无约束的问题，因此不能直接解决被约束到置换矩阵的QAP（1为了克服这个限制，最近的方法[62]增加了一个惩罚项，强制解决方案是一个置换。然而，这将可解决的问题大小减少到非常小的n4，并且在实践中，可能找到全局最优解的概率下降到随机猜测相比之下，我们提出了一个新的配方AQCing，保证导致置换矩阵的问题大小的数量级的可用（完全连接）量子位。见图表1为方法概述，表1为我们使用的首字母缩略词列表。我们的方法是迭代的，我们解决了一系列的二次无约束二进制优化（QUBO）问题的D-波准备在一个经典的CPU。总之，本文的贡献如下：• Q匹配，即，一种新的可扩展的量子方法，用于搜索由非刚性变换（等距或近等距）相关的两个形状之间的对应关系• 通过α-展开的一个变体的迭代问题公式化，避免了置换的显式线性约束，并且可以应用于大的问题实例。我们评估我们的方法上一个真正的AQCer，D-波优势系统1。1，并获得与以前的量子方法[62]相比改进的结果。此外，Q-Match的性能与经典匹配方法[52]相当。本文不假设读者对量子计算有先验知识。Secs. 3.1和3.2审查理解、实施和应用拟议的Q匹配方法所需的先决源代码可在https://4dqv.mpi-inf.mpg.de/QMATCH/上获得。2. 相关工作本节回顾了量子计算，计算机视觉和形状匹配的交叉点上的先前工作。缩写意义AQCer/ing绝热量子计算机QPU量子处理单元QAP二次分配问题Qubo二次无约束二元优化表1. 常用的首字母缩略词及其含义。在国际上[17，29]，越来越多的兴趣正在发展以将量子计算或其概念应用于计算机视觉。在量子计算机上表示、检索和处理图像的方法已经在理论文献中被广泛研究[68，14，64，71]。图像识别和分类方法是在真实AQCer上评估的第一批低级技术[46，9，48，15，39]。O'Malley等人 [53]在AQCing的帮助下学习面部特征并再现人脸的图像集。Cavallaro等人。 [15]使用量子支持向量机的集合对多光谱图像进行分类[70]。为了解决D-Wave 2000 Q的物理量子位图的有限连接性，他们将训练集分成多个不相交的子集，并在每个子集上独立地训练分类器Li和Ghosh [39]使用来自[58]的QUBO公式消除了D-Wave 2X上多目标检测中的误报。它提供了最先进的准确性，量子退火的实现比贪婪和禁忌搜索更快。在[47]中首次从理论上研究了用量子退火器解决图像匹配问题。在[24]中已经引入了用于绝对定向问题和点集对准的实际可应用的量子算法。工作表明，表示旋转矩阵使用线性基础允许映射到QU-BO的两个问题。最近在[50]中导出了用于门模型量子计算机的新的点集对准方法，其受到早期核相关方法[67]的启发。QGM[62]是作为具有惩罚方法的单个QUBO的针对小问题实例的图匹配的第一实现，而QuantumSync [6]是针对AQCer开发并在AQCer上测试的用于置换同步的第一方法（Advantage system 1. ①的人。[62]《易经》中的卦。具有线性项的置换矩阵约束导致在现代AQCer上的单个退火循环中测量全局最优解的概率低。与[62，6]相反，我们避免了确保有效排列的显式约束，并使用一系列QUBO，导致能量的连续改进。因此，我们可以对齐更大的图形和形状。形状对应：在网格之间寻找逐点匹配是视觉领域中一个非常活跃的研究课题有关AQCing的基础，请参见第3.1和[30，22]。计算机视觉AQCing：在量子硬件的进步推动下，广泛的研究领域-和图形。建立通过等距相关的形状之间的匹配的一种常见方式是比较形状函数或签名。此类别的多个方法7588NPNPNP--| | 2联系我们| ⟩ | ⟩| ⟩|⟩| ∈| ⟩| ⟩ ⊗ |⟩| ∈|∈|⟩| ⟩|∈||||lyze谱的Laplace-Beltrami运营商的形状表面是不变的等距变形下[65，3，52，59，27]。功能图[52，27]将问题解释为在预定义的基础上对齐功能（例如，Laplace-Beltrami算子的本征函数）。需要后处理来提取逐点匹配。在形状描述符中，波核信号（WKS）[3]受到量子物理学的启发。它依赖于解决薛定谔方程的动力学（耗散）的量子力学粒子的形状表面。WKS可以解决精细的细节，是稳健的中度非等距扰动。最近，卷积运算符被推广到非欧几里德结构，并且大规模形状集合的可用性使得能够监督密集形状对应的学习[42，45，40]。两个形状之间的逐点对应搜索可以用公式表示为排列空间上的线性（LAP）或二次分配问题（QAP），其中匹配成本依赖于特征描述符[65，3，59]计算。这两个问题的解空间是指数的点的数量。对于LAP，存在具有多项式运行时间的快速拍卖算法[5]。根据构造，用于匹配的LAP公式对表面噪声敏感，并且不明确地考虑空间点关系，这通常导致局部最小值（并且，因此）。优化方案基于测地线嵌入添加新的匹配，而我们可以细化任何给定的初始化。3. 背景3.1. 绝热量子退火Kadowaki和Nishimori [30]的开创性工作引入了量子退火。作者认为，量子计算机可以基于在横向磁场诱导的量子涨落（引起状态跃迁）下找到伊辛模型基态的原理来构建。这种计算机器的理论基础是基于绝热理论[8]。 在后续工作中，Farhi等人 [22]测试了量子退火算法模拟经典计算机上的硬实例- 完全的问题。尽管人们不认为量子退火可以在多项式时间内解决完全问题，但对于具有高和窄尖峰的崎岖能量景观，量子退火可以比模拟退火更快[18，19]，并且在某些情况下，D-Wave比经典路径积分蒙特卡罗方法更好[33]。AQCing可以解决二次无约束二进制优化（QUBO）问题，其读取不准确的解决方案）。QAP [34，35]为匹配点对添加二次成本，并将点邻居视为mins∈{−1，1}nsJs+bs，（2）罩;解决方案在空间上更平滑。缺点是它们的复杂性，这使得寻找大输入的全局最优解变得不可行.文献中已经提出了多种有效解决QAP的策略，例如分支定界[57，26]、谱分析[38]、乘数的交替方向方法[36]、能量景观的熵规则化[63]和模拟退火[28]。凸松弛是QAP的最彻底研究的策略之一[72，2，54，23，31，4]。这些方法或者具有禁止性的最坏情况运行时复杂度（分支定界），依赖于启发式算法选择（例如，熵正则化和模拟退火），或者不保证全局最优。相比之下，我们解决QAP与一个新的AQCing元启发式找到高质量的解决方案，具有很高的概率。Holzschuh等人 [28]提出了一个与我们的算法密切相关的非量子算法。可以看出，我们的设置的一个特殊情况是每次迭代仅应用一个2周期这意味着与Q-Match相比步长小得多，因此迭代次数更多，直到收敛，对局部最优值的敏感性更高。在[28]中进一步使用了几种启发式方法来获得鲁棒性和速度。首先，该算法是基于模拟退火和接受更坏的状态有一定的概率步过局部最优。相比之下，我们的Q-Match同时探索更大的解空间，并在更少的迭代中收敛第二，他们的等级其中s是未知数的二进制向量，J是量子位间耦合的对称矩阵，并且b包含量子位偏置。要将二进制变量改变为x0，1n，只需要在（2）中的任何地方插入si=2x i1。量子计算机利用量子位进行操作，即，可以用正规化矢量建模的量子力学系统|在Hilbert空间H中人写信|ϕ⟩=α0 +β1 关于α，βC和 α2+β2=1，其中0，1表示标准正交基。与处于状态0或1的经典位相比，量子位具有以下特征：机械系统可以处于叠加α0 +β1中，其中在所谓的计算基础（{|0，|1}）一个获得|0概率|阿尔法|2和|1.概率 β值 . 一种复合系统，例如，、两个量子比特可以用来自各个希尔伯特空间ψH H的张量积的向量来描述。 如果两个量子比特可以相互独立地描述，我们有H和ηH，两个量子比特态ψ由乘积态ψ =描述η。 由于n个量子比特的状态空间是2n维的，因此经典计算机即使存储n=50的所有系数也会有问题[49]。除了量子位状态的叠加之外，量子计算所需的第二成分是由量子位之间的相互作用引起的2n维状态空间中的不同可能计算路径之间的干扰因此，在量子75892nNτH（t）=.1−ΣH+H。（四）我01-02|0|0+|1|（1）是不能以上述形式分解的。量子态之间的纠缠通常被认为是量子计算的必要资源[55]。在量子算法的最后，协-在适当的测量中确定每个量子位的系数α和β，使（绝热或电路模型）量子计算机处于经典（非纠缠）状态。量子力学中的另一个中心概念是作用于H元素的线性哈密顿算符，它被用来用薛定谔方程描述量子系统的静态和动态性质。（与时间无关的）哈密顿量的本征态本征值给出了系统能量的相应可能值。用于解决像（2）这样的问题的关键思想是准备处于哈密顿H1的最低能量的已知状态的量子系统，最常见的是以下形式的乘积状态：O1嵌入）、解嵌入、位串选择（在多重退火的情况下）和解解释。QUBO制备：请注意，许多计算机视觉问题自然地以QUBO以外的形式进行表述。因此，许多研究集中在QUBO制备上，即，如何将目标问题表述为可映射到AQCer 的 QUBO （ 第 2 节 ） 4 完 全 致 力 于 Q-Match 的QUBO准备）。请注意，这一步是执行-形成完全在CPU上。在QUBO中，每个二进制变量被解释为量子上下文中的一个逻辑量子位。因此，偏置b和量子位J之间的耦合定义逻辑问题量子位的图。次要嵌入是逻辑量子位到AQCer的物理硬件量子位的网格的映射。由于物理量子位之间的有限连接性，每个逻辑量子位通常需要在次要嵌入中的若干物理量子位。实现单个逻辑量子位并且在退火期间具有尽可能相似的量子态的物理量子位构建链。找到一个次要嵌入|ψ（t =0）>=i=1 √2（|0+|（3）是一个NP-困难的优化问题。其中接下来，构造问题哈密顿量HP，使得HP的最低能态是（2）的解。最后，从初始哈密顿量H1缓慢切换到最终哈密顿量Hp，例如，的线性组合t tτP如果（4）中的转变足够慢（即，如果τ足够大），并且如果H（t）的最低能量状态（基态）保持唯一，则绝热定理[8]保证量子系统对于所有t都将保持在基态。因此，（2）的解可以在开始于H1的本征态（其通常容易制备）并结束于H2的本征态的时间演化之后简单地测量。绝热蒸发的理论要求可以根据H（t）的光谱间隙的大小精确，即，在时间演化期间，H（t）的最小和第二小特征值之间的差。构建一个系统来实际准备一个量子系统，并在实践中以绝热的方式进化它，然而，仍然是非常具有挑战性的。太小的光谱间隙将导致在退火过程期间激发更高的能量状态，从而防止系统终止。自己的[13]。然而，问题变得更容易，因为一个图是由硬件固定的，并且可以使用诸如[13]的启发式方法。最优子嵌入的核心标准是联合最小化链长度和所需物理量子位的总数。一旦次要嵌入完成，就开始量子退火它对应于相对于时间相关的哈密顿量（例如（4））的系统的评估，在此期间，量子系统在整个退火期间理想地保持在基态，参见第2节。第3.1条在实践中，由于诸如1）预期量子位寿命（例如，受与环境的相互作用的影响，这不能完全避免），以及2）H（t）的小光谱间隙，需要多次退火，每次退火以一定概率导致全局最优<1.一、在每次退火之后，解嵌入算法将测量值标记为逻辑量子位。在位串选择步骤中基于出现频率或所得能量来选择多次退火的最终解。 最后，在原始问题的背景下解释了该解决方案。并返回给用户。就这一点而言，解释涉及将测量的位串变换为初始数据模态（例如， 置换矩阵）。D-Wave 编程 完成在所需的HP基态中运行。接下来，我们讨论关于这种实际实现的一些细节。3.2. D波量子退火每个AQCing算法包括六个步骤，即，QUBO制备、次要包埋、量子退火（sam-铌环约瑟夫森结图2. 超导通量量子比特。在Python中，使用Leap 2编程接口和远程访问工具[17]。D-Wave机器使用超导通量量子比特[43]。量子位和耦合器是用铌环来实现的，7590--Σ我--联系我们|}Qn我我0J我JXi′i=1，Xi′i=1，Xii=1。证明不相交置换可交换是很容易的。此外，委员会认为，00J0J我我Σ0Σ必须冷却到17mK以下。顺时针或逆时针流过铌环的电流可以被建模为量子位，参见图1B。二、因此，只要没有测量被干扰，就可以在顺时针和逆时针流动的电流之间具有叠加。4.1. 循环α-展开令C=cl，…，c m是m个不相交循环的集合。我们考虑初始置换P0的以下优化问题：执行。（2）中指定的耦合J和偏置b确定了在测量期间磁通量的时间演变。arg min{P∈P |ξα∈{0，1}m：P=（Qcαi）P}E（P），（5）量子退火3.3. α-展开在[10]中引入了α-扩展算法来解决标记优化问题（例如，用于语义分割或视差估计）。一个值得注意的扩展是[37]，其中该方法被推广到允许并行计算等。在每次迭代中，计算对应于标签的两个提议值的二进制变量α的向量，使得提议之间的决策提高能量。[10]通过图切割找到最佳扩展，使得如果αi=1，则图像中的每个像素被分配给第一个建议的标签，或者如果α=0，则分配给第二个建议的标签。除此应用外，α展开在子问题（即，α1的优化是次模的。然后利用图割技术有效地求解子问题。3.4. 循环置换我们定义置换矩阵的集合为 Pn={X∈0，1n×niX ij=1，jX ij=1i，j.一个置换矩阵X称为k-圈，如果存在k个互不相交的指数i1，…，i2，…，i3，…，i4，…，i5，…，i6，…，i7，…，i8，…，i9，…，i10，…，i11，…，i12，…，i11 . . ，i k，使得X i1 ik =1且X ij+1ij = 1其中E在⑴中定义，并且α是参数化P的二进制向量。如第二节所述。3.4，所有cαi的乘积的顺序并不重要，因为不相交的排列可换。如果C不固定为不相交的循环，则（5）将等同于（1），但也可以被优化。问题复杂性：（5）中的优化问题针对每个周期做出是否应当应用它的二元决策。在本节中，我们证明了（5）是一个优化问题，其复杂性取决于循环数而不是n。我们可以将（5）中的圈的乘法转换为下面的线性组合MP（α）=P0+αi（ci−I）P0，（6）i=1我就是身份。见补充证明。接下来，我们使用该表示来表明（5）是大小为m的形式为（2）的问题。设P，Q是两个置换，E（Q，R）=vec（Q）TWvec（R）在每个分量上都是线性的. 我们写C i=（c iI）P0以简化符号。因此，为了解决（5），我们需要最小化E（P0+αi Ci，P0+αj Cj）I j对于所有j=1，. . . ，k−1，且Xll=1，对于所有l∈f{i1，. . . ，k}，=E（P0，P0+ΣαjCj）+Σα iE（Ci，P0+ΣαjCj）两个排列X和X′称为不相交的，如果Xii=1̸=E（P，P）+Σα E（P，C）+Σα E（C，P）J我它认为任何X都可以写成2-圈的乘积c i，即，X =Ni=0时c岛最后，我们使用符号X1=X+ΣΣαjαiE（Ci，Cj）=E（P0，P0）+αTW~α，我 J且X0=I，其中I是任何矩阵X的单位元。4. 方法与W~ij =.E（Ci，Cj）如果i j，先前的量子计算方法（诸如[62]）用于求解（1）的主要困难是处理线性的E（Ci，Ci）+E（Ci，P0）+E（P0，Cj）。（七）当E（P0，P0）为常数时. α，我们只剩下等式约束产生的优化per-mutation矩阵。而不是通过惩罚来强制执行minα∈{0，1}mαW~α，（8）Q-Match的核心思想是迭代地最小化（1）：我们建议使用α-扩展算法的变体，该算法选择k个不相交的候选循环ci，并使用量子计算来求解（仍然是NP-困难的，但更小和这可以通过AQCers直接解决最佳α的解释是是否应用相应循环的二元指标。在建立了（8）的基本方法的情况下，我们迭代地进行：在这种情况下，X=（i1i2. . . i k）是一个常用的符号。7591Σαj无约束）子问题，决定是否应用ci或不（分别用αi=1和αi=0在当前估计P不相交圈i−1 最小化（1），我们选择一组接下来，我们详细介绍了循环α-展开的思想以及我们提出的Q-Match算法。Pi=.QJC={c1，c2，. . . ，c m}，优化（8），并设置jPi−1。C7592Σ×个∈∈∈算法1：Q-匹配输入：形状M、N输出：对应关系P1 初始化P（秒4.2.3）2个重复3计算k个最差顶点IM，IN（10）4构造最差匹配子矩阵Ws（S. 4.2.2）5个重复6选择新的2-循环7计算W~（秒4.2.2和（7））8用AQCing求解QUBO（89根据（6）10，直到每2个循环在一组11将置换应用于P12 直到P不再变化13 返回P4.2. Q-Match循环α-扩展可以优化任何QAP，直到适合AQC的问题大小，例如， 通过在循环的随机集合上迭代。为了解决两个3D形状M和N之间的（等距）形状对应的更大问题，我们提出了Q-Match。如果两个形状都用n个顶点的相同网格离散化，则W具有以下形式：最差顶点：对于M中具有索引v和置换P的点，我们可以通过以下公式量化v对⑴的影响：I（v）=Wv·n+P（v），w·n+P（w），（10）w∈M其中P（v）表示索引v被映射到。对于N上的顶点，我们等价地进行。如果I（v）为高，则这是P（v）与P中的大多数其他匹配不一致的指示符。因此，我们在两个集合IM和IN中的每个形状上收集具有I的最高值的m个顶点。通过这种选择，（1）的潜在改进被最大化参见第5.3对于m的大小的分析。2-圈：随后，我们从IM，IN中选择一组k个随机但不相交的2-圈。虽然对2-圈的限制听起来可能是限制性的，但以下引理（在附录和许多抽象代数教科书中证明[60]）突出了不相交2-圈的表达能力：引理4.1. 每个置换P可以写成P=其中Q和R是不相交2-圈的乘积4.2.2子问题3D网格通常由一千多个顶点组成这意味着W∈Rn2×n2不能预先计算和存储W i·n+k，j·n+l= |dM（i，j）− dN（k，l）|（九）其中i，j是M上的顶点，k，l是N上的顶点，并且dg（a，b）是同一形状上的两个点之间的测地线距离因 此 ，对于两个匹配（i，k），（j，l），Wi·n+k，j·n+l描述了在该对的元素之间保持测地线距离的程度。 最优解是所有点对之间的距离保持最佳的对应关系，对于isome，（1）的最优能量为零。 由于测地线距离具有几何意义，因此这传播到QAP中，并且Q-Match利用这一点来选择更好的循环集。在Q-Match中，测试循环的集合基于每个顶点对（1）（Sec.4.2.1），我们可以迭代地解决子问题（Sec.4.2.2），初始排列是基于描述符的（第4.2.2节）。4.2.3）。 整个Q-Match算法的概述可以在Alg. 1.一、4.2.1选择周期选择C的一个选项是通过随机绘制不相交的循环，然而，这可能需要多次迭代才能达到最优。相反，我们利用等度量形状匹配问题创建其中条目高度相关的QAP的事实。在记忆里因此，在每次迭代中，计算（8）的W的所有所需条目将从头开始计算。 如在（7）中可以看到的，对于W ~需要对成本函数E的若干评估，这使得该操作花费ive。为了更有效，我们将计算分成Ws的计算，W s是基于IM，IN中的k个最差顶点的W的k2k2约简。这是我们算法中最昂贵的操作（见图1）。（六）。 对于IM，IN上的一组2-循环，计算W~是不足够的。 为了减少我们必须计算W的次数，我们评估几个集合，而不是仅仅在每个IM、IN上选择一个2-循环的集合。在实践中，我们对IM、IN和UN上的2-循环的集合进行直到每一个可能的2-循环被选择至少一次。如何计算Ws和W~ s以及运行时分析的详细描述可以在补充材料中找到。4.2.3初始化唯一剩下的就是选择P0作为第一次迭代。代替随机初始化，我们计算基于描述符的相似性SRN×N在M和N的所有顶点之间，等价于[69]的策略。Smn包含顶点mM，n N的规范化HKS [65]和SHOT [66]描述子的内积，我们求解S上的一个线性分配问题得到第一置换。7593Q-MatchZo [44]FMs [52]美国[28]%对应性能源联系我们10.50两次一次二四六八十10的情况。80的情况。60的情况。40的情况。20Q-MatchQGM [62]2 4 6 101214161820100380六零二402010个0个0 5·10−2 0. 10的情况。1502五十十五问题大小N#实例测地误差迭代次数图3. 关于Q-Match检索（1）的最优值的频率的实验。（左）随着问题大小的增加，我们的迭代方法通过强力计算得到最优结果的随机实例的比例。（右）20个随机问题的Q-Match和QGM [62我们计算（QGM）或下限（我们的）达到最佳退火的百分比。5. 实验我们评估我们的方法在随机QAP实例上的准确性、收敛性和运行时间（Sec. 5.1）、FAUST（第5.2）和QAPLIB（第5.5）。由于量子计算时间仍然非常昂贵，我们只评估了FAUST和QAPLIB的子集，但我们的结果表明这项技术在未来是多么有前途。所有实验都是在Intel i5 8265U CPU上使用Python 3完成的，具有16GB RAM。8和D-Wave Advantage系统1。1由Leap 2访问。注意，可以使用经典的QUBO求解器来求解子问题。在附录中，我们提出了一个模拟退火采样器的实验。5.1. 与基于惩罚的实施方式的我们比较Q-匹配与[62]中的插入方法，用于形式（9）的问题，其中距离di，j从[0，1]均匀随机绘制，并且W使用随机绘制的真置换P构造。我们比较了两种方 法 在 20 个 随 机 情 况 下 的 成 功 概 率 ， 见 图 。 3-（右）。Q-Match在除4种情况外的所有情况下均找到最佳值。为了公平的比较，我们将我们的方法中每次迭代的退火次数限制为10次，并使用500次退火用于插入方法。另外，迭代方法的成功概率由各个步骤的成功概率彼此相乘在多个不同输出具有最低能量的情况下，两个结果都对于n2，4，6，8，10，如果每个子问题都被解决为全局最优，我们计算达到最优置换的频率。为此，我们针对n=10生成了20个随机实例，并且针对其他维度生成了100个随机实例。误差计算为二项式比例置信区间，其应包含95%情况下的真实概率。首先进行该实验，使得所有2个循环仅发生一次，并且第二次整个过程进行两次，参见图1B。3-（左）。图4. FAUST上的累积误差[32]（左）和收敛（右）的评价。（左）我们与没有后处理的模拟退火[28]和功能图[52]进行比较虚线指示非量子方法。结果去除了对称翻转的解，这些解对于所有方法具有可比的最终能量，但在评价中不被认为是正确的。（右）我们展示了30次迭代的能量收敛最差顶点的集合越大，我们的方法收敛得越快灰色虚线示出了最佳能量。(i)（二）图5. 来自FAUST注册的示例对应关系。(i)我们的结果总体上是正确的，有一些离群值。(ii)失败案例。溶液的正面和背面部分交换这些类型的解决方案是近等距的，具有接近最优的能量，并且经常出现在纯粹解决（1）的所有方法中。此外，我们研究的解决方案与量子退火返回的最低对于500次运行和高达13大小的耦合矩阵，情况总是如此。因此，通过Q-Match找到的最优值的数量与图1中的概率相同。3-（左）。5.2. 浮士德我们对FAUST数据集的配准进行了实验[7]。我们对FAUST内的一个类的5个不同对进行评估，这些对被下采样到502个顶点。理论上可以在原始分辨率和更多对上使用我们的方法，但是QPU不像传统硬件那样免费可用，并且我们将可用的计算时间集中在对我们的方法的更深入分析我们应用如Alg.1与500退火，并比较两个非量子方法，模拟退火[28]和功能图[52]。[28]在没有ZoomOut [44]的情况下应用，使得它接近于我们的算法的版本，其中在每次迭代中仅选择一个2-循环。函数映射实现包括拉普拉斯交换性正则化器，并检索最终的点到·104最差26最差40最差50分最优性概率退火百分比7594Eopt604020010 15 20 25#最差顶点15105010 15 20 25#最差顶点10.50.1100 2 4 68实例[12]15105132.50 5 10实例[61，25，56]图6. 问题大小对运行时的影响。我们增加了最差顶点集的大小（见第二节）。4.2），并测量管道不同部分的运行时开发。虽然QPU访问时间大部分独立于问题大小，但是在CPU上计算W-是非常困难的。510 5 1015在[51]21.510.50 0 2 4 6 8实例[21]通过LAP进行点对应[52]。虽然[62]是概念上最接近我们的方法，但它只为预选的4个顶点产生匹配。定量评估可以在图中看到。4，和一些定性的例子，我们的方法在图。五、虽然我们没有达到与最近[28]相同的准确性，但我们确实优于经典但仍然流行的功能图。由于AQCers仍然是新开发的，并且与传统计算机相比具有有限的复杂性，因此我们将其视为量子退火在现实世界问题中的成功应用。5.3. 收敛我们评估了Q-Match需要多少次迭代才能在FAUST上收敛图图4示出了在每次迭代中选择26、40、50个最差顶点时的收敛性由于40和50之间的差值很小，我们选择用40个最差匹配进行所有进一步的实验在每次迭代中，每个2-循环在集合C中出现一次。以这种方式获得的一些示例性匹配可以在图1中看到。五、5.4. 运行时图6示出了Q-Match的运行时间如何随着由最差顶点的数量给出的问题大小而缩放。子矩阵Ws的计算是最昂贵的。计算矩阵W~gi venWs仅花费ms，而Ws的计算是秒的量级。但是我们QPU访问时间是量子退火器解决问题所花费的时间，并且主要与问题大小无关我们报告了约25分钟的QPU时间的结果，这使我们能够评估104个QUBO。一个FAUST实例使用40个最差顶点和500个退火每QUBO需要约2分钟的QPU时间。对于所有实验，我们使用默认退火路径和20µs的默认退火时间。选择链强度为1。0001倍的耦合或偏置的最大绝对值。图7. [2019 - 05 - 15][2019 - 05][ 问题大小在12到30之间，其中[51]包含了我们做得不太好的较大的那些。5.5. QAPLIBQAPLIB [11]提供了QAP的集合以及最知名的解决方案。这是QAP最常用的基准，具有来自各种设置的问题集，例如：图形和非结构化数据。在某些情况下，由于问题的复杂性，不清楚最佳已知解决方案是否实际上是最佳我们在一些子集上运行循环α扩展，确保在优化时每2个循环发生一次，并重复三次。如果尺寸>25，我们总是从5000次退火和500次退火中选择最佳解否则，请执行以下操作。 我们得到的相对误差如图所示。7.第一次会议。为从[12，21，25]的实例中，我们的解决方案几乎总是在最佳解决方案的1%对于[21]中的n=16个实例，我们在10种情况中的9种情况下获得了最优解。其他集合包含大小高达30的实例，并提出了更大的挑战，我们的最差结果在最佳结果的15%以内我们在补充材料中报告了我们的精确解6. 结论我们介绍了Q-Match，实验表明，它可以解决实际应用中遇到的尺寸对应问题。这一结论是第一次在文献中利用量子退火的方法。避免显式置换约束和迭代地处理问题允许我们在支持的问题大小和测量全局最优解的概率方面显著优于现有技术的先前量子状态。我们甚至取得了与经典方法相当的结果。我们希望我们的工作能够激发视觉社区中量子退火和相关优化问题的进一步研究鸣谢。这项工作得到了ERC整合者资助4DReply（770784）的部分支持。QPU接入联轴器计算值W~运行时间（毫运行时间相对误差单位：%相对误差单位：%7595引用[1] Dorit Aharonov、 Wim Van Dam 、Julia Kempe 、ZephLandau、Seth Lloyd和Oded Regev。绝热量子计算等价于标准量子计算。SIAM review，50（4）：755[2] 库尔特M.放大图片作者：Anstreicher and Nathan W.布里修斯用凸二次规划松弛法求解二次指派问题。优化方法和软件，16（1-4）：49[3] Mathieu Aubry，Ulrich Schlickewei，and Daniel Cremers.波核签名：形状分析的量子力学在2011年的国际计算机视觉研讨会（ICCV研讨会）上[4] Florian Bernard Christian Theobalt 和 Michael MoellerDs*：二次匹配问题的紧提升自由凸松弛。在计算机视觉和模式识别（CVPR），2018年。[5] 迪米特里·P·伯塞卡斯。网络优化：连续和离散模型。Athena Scientific，1998年。[6] Tolga Birdal，Vladislav Golyanik，Christian Theobalt，and Leonidas Guibas.量子置换同步。在计算机视觉和模式识别（CVPR），2021。[7] Federica Bogo ， Javier Romero ， Matthew Loper ， andMichael J.黑色. Faust：3D网格配准的数据集和评估。在计算机视觉和模式识别（CVPR），2014年。[8] 马 克 斯 · 波 恩 和 弗 拉 基 米 尔 · 福 克Beweis desadiabatensatzes.Zeits chhriftfur¨rPhysik，51（3）：165[9] Edward Boyda ， Saikat Basu ， Sangram Ganguly ，Andrew Michaelis ， Supratik Mukhopadhyay ， andRamakrishna R.尼玛尼部署量子退火处理器检测加州航空影像中的树木覆盖。PLoS ONE，12，2017。[10] Yuri Boykov Olga Veksler和Ramin Zabih通过图形切割快速 近 似 能 量 最 小 化 。 IEEE Transactions on PatternAnalysis and Machine Intelligence （ TPAMI ） ， 23（11），2001.[11] Rainer E.作者：Stefan E. Karisch和Franz Rendl。Qaplib -一个二次分配问题库。Journal of Global Optimization，1997.[12] Rainer E. Burkard 和 Josef 奥弗尔曼 在机械状态下的工作中存在一些问题. Zeits chriftfur¨r OperationsResearc h，1977.[13] 放大图片作者：William G.麦克里迪和艾丹·罗伊。一个实用的启发式寻找图的子。arXiv电子印刷品，2014年。[14] Simona Caraiman和Vasile I.蝠鲼使用量子计算的图像处理 。 在 2012 年 的 系 统 理 论 、 控 制 与 计 算 国 际 会 议（ICSTCC）[15] Gabriele Cavallaro、Dennis Willsch、Madita Willsch、Kris- tel Michielsen和Morris Riedel。在d波量子退火机上用支持向量机集成实现遥感图像分类。IEEE国际地球科学与遥感研讨会（IGARSS），2020年。[16] Andrew M Childs，Edward Farhi，and John Preskill.绝热量子计算的鲁棒性。Physical Review A，65（1）：012322，2001.[17] D-Wave Systems，IncLeap datasheet v10.https：//www.dwavesys.com/sites/default/files/Leap_Datasheet_v10_0.pdf，2021.在线; 2021年2月25日访问。[18] Arnab Das和Bikas K Chakrabarti。量子退火和相关优化方 法 ， 第 679 卷 。 Springer Sci-ence Business Media ，2005.[19] 瓦西尔·S放大图片作者：Sergio V.Isakov，Nan Ding，Ryan Babbush，Vadim Smel