量子计算中的点集对应问题及其应用

arg minq∈Bn qTPq,(1)(2)In their seminal paper, Farhi et al. [26] have shownthat the adiabatic principle (2) can be used for solvingNP-complete optimisation problems and laid the founda-tion for adiabatic quantum computing. Several years later,Aharonov et al. [2] theoretically showed the equivalence be-tween classical quantum computing and quantum anneal-ing models. As of 2019-2020, general-purpose quantumcomputers accessible for research purposes and applicationscontain up to 20 qubits [19]. In contrast, the latest quantumannealers support up to 210 qubits [21]1. Nevertheless, due91820一种用于点集对应问题的量子计算方法0弗拉迪斯拉夫∙戈利亚尼克 克里斯蒂安∙泰奥巴尔特马克斯∙普朗克计算机科学研究所 萨尔兰德计算机科学校园0摘要0现代绝热量子计算机（AQC）已经被广泛应用于解决各个科学领域中的困难组合优化问题。目前，在计算机视觉领域中只有少数几个AQC的应用被证明是成功的。我们回顾了AQC并推导出一种适用于在AQC上执行的点集对应问题的新算法。我们的算法具有次二次计算复杂度的状态准备。通过模拟抽样，我们展示了成功的变换估计和点集对齐的例子，并进行了系统的实验评估。最后，我们分析了解的差异和相应的能量值。01. 引言0自从80年代初提出以来[8, 42,27]，量子计算机引起了物理学家和计算机科学家的广泛关注。在过去的三十年里，量子计算硬件和算法方面取得了令人瞩目的进展[39, 30, 60, 57, 41, 19, 25, 48, 64,47]。量子计算机并不普遍比传统机器更快，但它们可以本地执行依赖于量子并行性的算法，即能够同时在指数级的超级叠加内存状态上执行操作[58]。为了利用这些优势，需要精心设计的算法。如今，利用量子效应进行计算的动机也得到了促进，因为经典计算范式正接近其极限，而量子效应在制造和使用传统CPU时变得不可忽视。因此，替代性范式，如大规模并行计算设备，已经出现。虽然通用门量子计算技术尚未达到成熟，但现代绝热量子退火器（AQA）已经能够解决困难的现实世界组合优化问题[15, 14, 23,48]。通用门量子计算和AQA的主要区别在于后者可以解决形式化为二次无约束二进制优化问题（QUBOP）的目标。0图1：不同的2D点集（鱼[46]、量子位、汉字和作曲家）与我们的QA方法对齐。对于每一对点集，左边显示初始错位，右边显示配准结果。QA是第一种可以在绝热量子计算机上执行的变换估计和点集对齐方法。0在他们的开创性论文中，法里等人[26]已经证明了绝热原理（2）可以用于解决NP完全的优化问题，并为绝热量子计算奠定了基础。几年后，阿哈罗诺夫等人[2]在理论上证明了经典量子计算和量子退火模型之间的等价性。截至2019-2020年，可供研究和应用的通用量子计算机最多包含20个量子比特[19]。相比之下，最新的量子退火器支持多达210个量子比特[21]1。然而，由于0如果一个量子力学系统处于一个时间依赖的哈密顿量的基态，并且这个哈密顿量的参数变化足够缓慢，那么在演化过程中系统将继续保持在基态（有关量子概念请参见表1）。01 在该系统上可用的逻辑量子比特的数量要低一个数量级，因为大多数量子比特用于错误纠正。91830由于设计和实际限制，目前的量子退火器无法实现基于门模型的量子算法，如Shor的质因数分解[60]或Grover的搜索算法[30]。动机和贡献。考虑到AQA在计算科学的几个领域中的最近成功应用[41，48，64]，我们有动力研究AQA在计算机视觉中的实用性以及新硬件上可能解决的问题。关于量子退火器的绝大多数可用材料要么面向物理学家，要么缺乏技术细节和清晰度。我们的目标是填补这一空白，介绍读者进入现代AQA，并提供所有概念和背景，以理解、分析、模拟和设计可能在现代AQA上运行的计算机视觉量子算法，并解释结果。我们考虑计算机视觉中的点集对应问题，这在计算机视觉中有各种应用。它们的目标是在输入之间找到最优的刚性变换[33，13，46，65]。虽然变换估计假设已知匹配，但点集对齐更加通用，并且还针对对应关系的恢复。我们考虑两个输入，即一个固定的参考点集和一个正在进行刚性变换的模板。因此，我们的目标是设计一种在AQA上可能运行的点集对齐的量子方法，并展示它相对于经典对应物的优势。因此，我们调整了刚性点集对齐的最新进展，并制定了一个全局多重链接能量泛函，不需要任何中间对应更新[29]。在引力方法（GA）[29]中，当具有两个相互作用的粒子群的系统的引力势能（GPE）局部最小时，达到最佳对齐。从GA出发，我们为相关的QUBOP（1）构建了权重矩阵P，该矩阵在优化过程中始终有效。同时，我们还针对一种可在经典硬件上实现且能够解决实际问题的方法，参见图1。总结一下，本文的主要贡献是：0•对于计算机视觉问题，提供现代量子退火器的自包含和详细介绍，包括量子物理和计算的概念（第2节），现代绝热量子退火器（第3节），包括D-WAVE（第3.2节），以及量子计算的先前和相关工作（第4节）。0•第一个可以在即将推出的量子退火器上运行的变换估计（第5节）和点集对齐（第6节）的量子方法（第6.2节）。0•在模拟环境中对所提出方法进行实验分析，使用多个数据集（第7节）。0量子概念经典对应物0量子位（状态 | 0 � 和 | 1 � ）比特（状态 0 和 1）（时间相关）哈密顿能量泛函本征态某个能量态基态全局最优能量态量子系统演化优化过程量子退火 [26] 模拟退火 [38]0表1：计算机视觉中的量子概念及其对应物。02. Preliminaries, Definitions and Notations0在本节中，我们向读者介绍量子计算的基础知识。有关AQA特定的概念以及在计算机视觉的经典优化理论中的对应和解释，请参见表1。量子位。量子计算涵盖了可以在量子力学系统上执行的任务[52]。量子叠加和纠缠是量子计算机中的两种形式的并行性。量子位是经典位的量子力学等效物。量子位| φ � - 以Dirac符号表示 - 可以处于状态| 0 �，| 1�或两个状态的任意叠加状态，用| φ � = α | 0 � + β | 1�表示，其中α和β是（通常是复数的）概率幅，满足| α | 2 + | β | 2 =1。在量子计算中，状态| 0 � + | 1 � √02 用  | + �表示的态经常用于量子比特寄存器的初始化。量子比特的状态在整个计算过程中保持隐藏，并在测量时才显现出来。如果量子比特被纠缠，测量其中一个会影响另一个的测量结果 [ 58]。在测量过程中，量子比特的状态不可逆地坍缩到基态  | 0 �或  | 1 �中的一个。有效的量子比特物理实现要求非常低的温度。否则，热涨落会破坏它，并导致测量到的量子比特状态的任意改变。一个可能的量子比特的物理实现是一个具有自旋的电子，即其固有磁矩 [ 52 ,  62]。电子的自旋可以被操纵并带到自旋向下、自旋向上或两者的叠加态。一个具体的实验实现方案是将磷 31 P的原子嵌入到一个附着在晶体硅 28 Si 栅格上的晶体管中 [ 36 ,45 ,  66 ]。31 P的核心带有一个由电子补偿的正电荷。晶体管中的电子束填充到自旋向下和自旋向上态的能级之间的能级。要改变 31 P-28Si量子比特的状态，需要将频率等于原子共振频率的微波脉冲施加到它上面。新的状态  | φ �取决于暴露的持续时间。晶体管用于测量 31 P-28 Si量子比特的状态。如果 31 P的额外电子隧道进入电子束，晶体管中测量到正电荷，表示自旋向上态（例如，  | 1 � ）。图 2-(a)可视化了一个所谓的布洛赫球的量子比特。每个量子比特既可以处于叠加态，也可以与其他量子比特纠缠。因此，量子叠加是计算在所有可能的输入上同时进行的属性，这可能导致指数级的量子比特并行性。当纠缠时，量子比特的状态不能独立地描述。薛定谔方程。在通用的或门模型中，变化通过应用于量子比特的一系列酉变换来表示。这是一个有用的实际简化，虽然每个量子力学系统的演化可以更精确地用连续的薛定谔方程描述，常见的表示法如下：xyz+ + + +...+......11010...s = 0:s = 1:...... [0;1]s+(a)(b)− i ddt |φ(t)⟩ = ˆH(t) |φ(t)⟩.(3)2n×n2nh1 I2n×2nh2 I2n×2n...hn I2n×2nn2n×2n,(6)91840退火0图2：(a)：布洛赫球的量子比特的示意图。自旋向上或  | 1 �  位于北极，自旋向下或  | 0 �  位于南极。态  | 0 �+ | 1 � √0以相等的概率幅度测量  | 1 �  和  | 0 �值的点在地球上是等距离于两个极点的。布洛赫球面上的一个点对应于一个有效的纯态  | φ �  =  α | 0 �  +  β | 1 � 。 (b)：绝热量子退火（AQA）的示意图。在开始时，所有量子比特都被初始化为状态  | + �。退火完成后，量子比特的状态被测量并返回。测量后，变量的状态是经典的。0与其他量子比特纠缠在一起。因此，量子叠加是计算在所有可能的输入上同时进行的属性，这可能导致指数级的量子比特并行性。当纠缠时，量子比特的状态不能独立地描述。薛定谔方程。在通用的或门模型中，变化通过应用于量子比特的一系列酉变换来表示。这是一个有用的实际简化，虽然每个量子力学系统的演化可以更精确地用连续的薛定谔方程描述，常见的表示法如下：0为了简化起见，我们在这里用  | φ �  表示时间  t  的  n个量子比特的状态，ˆ H ( t )是一个哈密顿量，它在这种情况下是一个  2 n × 2 n的厄米矩阵。因此，量子系统的离散时间演化由一个酉变换给出。哈密顿量。哈密顿量 ˆ H  是一个  n个量子比特系统的能量算符。它定义了系统的能谱，或者在我们的情况下，所有可能解的空间。系统的基态是其能量最低的本征态。找到一个哈密顿量的基态等价于找到问题的最优解。哈密顿量的期望值  � ˆ H �提供了给定量子比特配置的瞬时能量。在对应问题中，  � ˆ H�  是点集对齐的定量特征。我们用  ∆( ˆ H )  表示 ˆ H的能级间隙，即基态能量和第二低本征态能量之间的差异。能级间隙影响退火速率，并且在量子退火算法的设计和评估中非常重要。泡利矩阵。一个  n个量子比特系统的任意哈密顿量可以用泡利矩阵的张量积的线性组合表示，表示为：0σx = 0 1 1 00, σy = 0 −ii 00, σz = 1 0 0 −10. (4)0Pauli矩阵是2×2的Hermitian矩阵和幺正矩阵。与单位矩阵σ0 =I2×2一起，它们构成了C2×2的一组基。σx将测量概率翻转为|0�和|1�，而σz |0� = |0�，σz |1� =−|1�。伪布尔函数。伪布尔函数是n个布尔变量x的实值向量值函数，表示为F(x)：Bn→RM，其中M是实值输出的数量。量子退火。量子退火是一种基于量子效应（叠加、纠缠和隧穿）的启发式组合优化方法，用于寻找全局最优解[11,35]。特别地，它用于寻找Ising哈密顿量的基态[34,56]，该哈密顿量编码了目标计算问题，参见图2-(b)。量子退火是模拟退火[44, 38]的量子对应。从叠加态[|+�] �n（这是n个处于|+�状态的量子比特的简写，参见(9)）开始，系统根据(3)在外部时变磁场（横向场）的作用下演化。当外部场逐渐消失时，系统达到Ising模型的基态[34]。根据(2)，如果外部磁场变化足够缓慢，系统在整个优化过程中以很高的概率保持接近基态。利用(2)的量子退火系统称为绝热量子计算机（AQC）。QUBOP是可以映射到当前AQC实现的最常见问题形式。03.现代绝热量子计算0绝热量子计算是一种依赖于量子力学的绝热定理（2）的量子退火形式[17]。从初始默认哈密顿量ˆHI的基态开始，AQC系统绝热地演化到问题哈密顿量ˆHP的基态，该哈密顿量编码了问题的解[26]。在绝热量子退火（AQA）的情况下，问题哈密顿量ˆHP由Ising模型给出[34]：0ˆHP =0j ∈ V hjσzj +0(j, k) ∈ EP Jj,k σzj � σzk, (5)0其中Kronecker积�，hj表示外部局部磁场，Ji,j表示粒子之间的成对连接。V是粒子的集合，EP是图的边（粒子内部链接）的集合。式（5）采用了物理学中常见的符号表示法。在显式表示法中，式（5）右侧的第一项为0ˆHj∈VP =0�0� �0�0�0σz � I � ... � I I � σz I0... � � ... � σz0�0�0T �0� � � ��0�0����0�0����Bxσxj ,(8)[|+⟩]⊗n =�|0⟩ + 1⟩√�⊗.(9)91850其中没有下标的I是一个2×2的单位矩阵。0第二项H(j, k) ∈ EPP(5)可以用类似的方式表示，涉及到张量积中σz的配对，取决于晶格的连接性。理论上，每个粒子都可以与整个量子比特集合中的任何其他粒子相互作用。实际上，耦合限制在局部邻域内（见第3.2节）。因此，（5）描述了一个由N个相互作用的自旋-½粒子组成的系统，受到分布式磁力的影响，而在展开形式中，ˆHP是一个2n×2n的矩阵。寻找Ising模型的基态是一个NP难问题[7]。在基态中，使Ising能量EIsing最小化的所有粒子的自旋构型为：0E Ising = 0ihi si+�0i,j J i,j si sj , (7)0其中si∈{1,−1}表示自旋-1/2粒子的两种可能自旋测量结果。03.1. 量子系统演化0在经典计算机上解决NP难问题，如QUBOP，需要指数级的输入大小时间。AQC的主要思想是将QUBOP(1)映射到Ising模型(5)，并通过允许系统按照绝热原理(2)演化来进行优化。一旦退火完成，量子比特寄存器将以很高的概率表示编程问题的解[26]（参见本文的补充材料中关于退火速率准则的内容）。系统的初始哈密顿量始终初始化为状态0ˆHI = −�0其中Bx>0表示指向x方向的磁场。(8)的基态是一个具有相等归一化概率振幅的态|0�和|1�的对称叠加态，即02n0这个初始态(9)可以通过向所有量子比特辐射相同持续时间和波长的微波来构造。从数学上讲，(9)是通过应用Hadamard变换H=1√0�到n个|0�量子比特0(8)的最低能量EGS=−nBx在所有量子比特指向磁场反平行方向时达到，即σxj|sj�=|sj�。在AQC过程中，初始哈密顿量ˆHI演化为问题哈密顿量ˆHP，有很高的概率达到ˆHP的基态[26]。哈密顿量之间的插值可以写成0ˆH = [1 − s]ˆHI + sˆHP , (10)0其中s∈[0;1]表示从s=0开始退火到s=1时的相对时间单位。问题哈密顿量和系统的最终状态取决于目标函数f(x)或量子比特之间的权重矩阵P[1]。退火完成后，测量每个量子比特的状态，结果与编程问题的解具有很高的概率相对应。在这个阶段，所有二进制变量的状态都是经典的，不再是量子的。为了在系统演化过程中保持在基态，必须仔细选择退火速率。绝热条件(2)是从量子系统的时变微扰理论中推导出来的。当每个时间间隔T内系统中平均能量输入小于基态和第一激发态之间的最小能量差时，就实现了绝热条件。这个陈述在[4]中进行了量化，它推广了原始绝热定理[17]的周期驱动情况，详细信息请参见我们的补充材料。03.2. 量子退火器D-WAVE0D-WAVE依赖于其指定形式的绝热准则，目前支持最多≈2000个量子比特[22]。它反映了量子处理器物理实现的最新技术水平。将系统置于叠加态相对较便宜，并且D-WAVE上的每个计算都始于与问题无关的ˆH I(8)。量子比特可以与有限数量的其他量子比特相互作用，并且可以定义量子比特的相等性和纠缠约束[22]。可以从chimera图中看到可能的相互作用，该图以示意方式描述了量子处理器的布局[22,16]。与此同时，通过内部转换，物理实现的连接性可以模拟具有任意连接性的QUBOP[16]。缺点是在最坏情况下，需要二次增加变量的数量。具有N个量子比特的完全连接的层图需要N2个量子比特进行处理。有些QUBOP无法映射到chimera图，而有些问题可以以多种方式映射[54]。04. 之前和相关的工作0通用量子计算机。通用量子计算机的范式起源于早年对个别量子系统进行控制的尝试[61,52]。后来，将控制扩展到多个量子系统引起了物理学家的兴趣，承诺在量子物理学中促进发现[52]。当时，人们注意到在经典计算机上模拟量子力学系统需要指数级的时间[42,27]。“你能用一种新型的计算机——量子计算机——做到吗？”[27]02 以模拟量子力学效应ments, i.e., R =r1,2r2,2r2,1r2,291860“Can you do it 2 with a new kind of computer – aquantum computer?” [27]是R.Feynman的一句著名的引文，它在随后的几年里引发了对量子计算机的研究。所谓的“无克隆定理”[55,63]属于最早的发现，对量子信息理论和量子计算产生了强烈的影响。如今，量子计算机不仅可以用于实现其主要目标，即为不同科学领域的量子力学系统进行模拟，还可以比经典计算机更快地解决其他计算问题，如平衡函数决策问题[24]、用于复杂性分析的量子图灵机[12]、素数分解和离散对数[60]、数据库搜索[30]、图匹配[3]、数据分类[57]和主成分分析[41]。与之相关的量子通信和量子密钥分发已经在实际中得到广泛应用[10, 9,59]。使用量子类比的经典方法。受量子力学效应的启发，包括遗传和进化算法的变体[31,32]、非刚性网格分析[5]和图像分割[6]等多种技术被应用于传统计算机。计算机视觉中的量子退火器。目前只有少数关于AQC在图像处理、机器学习和计算机视觉中的理论结果和应用被人们所知。Neven等人[50]展示了如何将图像识别表示为QUBOP。[51]中讨论了使用AQC进行12×12图像的图像分类。O’Malley等人的方法可以学习面部特征并重现面部图像集合[53]。Boyda等人提出了一种使用AQC方法从航空图像中检测树木区域的方法[18]。还有一些方法针对分类、降维和深度神经网络的训练[49, 37,1]。这些工作的并非所有理论发现都可以在真实的AQC硬件上进行测试。尽管如此，我们认为探索这一理论并突出即将到来的硬件在计算机视觉任务中的优势是至关重要的。05. 量子变换估计0在本节中，我们介绍了我们的QA用于变换估计。输入是一个参考点集[xn]∈X∈RD×N和一个模板点集[yn]∈Y∈RD×N，n∈{1,...,N}。N是两个点集中的点的数量，D是点的维度。我们假设已解决了平移问题，点集的质心重合，并且点是对应的。05.1. 2D中的变换估计0为了在量子退火器上解决变换估计问题，我们应该避免对Y应用均匀采样的旋转。旋转群的元素是非交换的，不可能将基本旋转的乘法表示为QUBOP。相反，我们建议将变换矩阵表示为线性的0基本元素的组合。请记住，对于任何旋转矩阵，R−1=RT。2D中的旋转由四个元素组成0�。此外，我们可以创建一个0对于所有可能的R值，我们可以将其表示为二进制变量，并编码加法元素的影响。相反，考虑二维中R的幂级数。每个这样的矩阵都有一个对应的形式为的反对称矩阵0S = θM, M = 0 -1 1 00矩阵，(11)0其中θ是实数。根据Cayley-Hamilton定理，S^2 + θ^2I =0，这导致R的以下幂级数的指数映射：0R = exp(S) =0cos(θ)I + sin(θ)0θ0S = cos(θ)I + sin(θ)M. (12)0根据(12)我们可以看出，R由一个以cos(θ)加权的单位矩阵和以sin(θ)加权的M组成。如果基础元素类似于指数映射的加法元素I和M，我们可以更强地约束结果R。我们可以看到r_1,1与r_2,2纠缠在一起，r_1,2与r_2,1纠缠在一起。最终，我们需要更少的基础元素，优化过程将更快完成，并且该方法也可以在经典计算机上实现和测试。因此，我们的基础Q= {Q_k}对于R是由K = 20个元素组成的复合基础：Q_k =ωC ∈ R^2×2，�ω ∈ {0.5, 0.2, 0.1, 0.1, 0.05}，0�C ∈ {I, M, -I, -M}. (13)0由于我们希望找到最小化对应点(x_n,y_n)之间距离的R，我们将每个模板点与负号−y_n相乘，并将结果堆叠到Φ中，其中每个基元Q_k都与二进制变量编码。相反，考虑二维中R的幂级数。每个这样的矩阵都有一个对应的形式为的反对称矩阵0Φ =0矩阵0x^T_1 x^T_2 ... x^T_N −[Q_1y_1]^T −[Q_1y_2]^T ... −[Q_1y_N]^T0−[Q_2y_1]^T −[Q_2y_2]^T ... −[Q_2y_N]^T0... ... ... ... −[Q_Ky_1]^T −[Q_Ky_2]^T ... −[Q_Ky_N]^T0矩阵0(14)0接下来，我们将(1)中的权重矩阵设置为0P = ΦΦ^T, (15)0并且最终的QUBOP为0arg min q ∈ B 21 q^TΦΦ^Tq. (16)0总共需要21个量子比特来解决二维AQC上的变换，其中q的第一个量子比特固定为|1�。通过量子退火解决(16)并测量q，我们可以获得一个经典位串ˆq。然后通过解嵌入来获得结果（可能是近似的）R，如下所示：0R =0k = 1ˆq_k+1Q_k. (17).�010100000001000100000001010µym µxn ∥R ym + t − xn∥2 ,(23)918705.2. 三维变换估计0在三维中，反对称矩阵可以表示为0S = θM, M =0m_1,1 m_1,2 m_1,3 m_2,1m_2,2 m_2,3 m_3,1 m_3,2m_3,30矩0 =00 a b -a 0 c-b -c 00矩0 ,0(18) 其中θ、a、b和c是实数，且a^2 + b^2 + c^2 =1。在三维情况下，Cayley-Hamilton定理表明−S^3−θ^2S = 0。具有幂级数的三维R的指数映射如下所示：0R = exp(S) = I + sinθ0θ0S + (1 - cosθ)0θ^20S^2 =0I + sinθM + (1 - cosθ)M^2. (19) 接下来，矩阵 M可以分解如下：0M = a00 1 0 -1 0 00 0 00矩阵0矩阵 M0+ b00 0 1 0 0 0-1 0 00矩阵0矩阵 M0+ c0� 0 0 0 0 0 0 -1 00�0�0� �� � Mc0（20）关于M，我们可以看到0• {m1,2;m2,1}，{m1,3;m3,1}和{m2,3;m3,2}是相互依赖或纠缠的，0• mi,j ∈ [-1; 1]，0• M = -MT，Ma = -MTa，Mb = -MTb和Mc =-MTc，即它们是反对称的，且0• M2 =0�v-1de dv-2fe fv-30是对称的负半-0是定符号的，其中{v-1,v-2,v-3} ∈ R-，{d,e,f} ∈ R。03D旋转的基础由单位矩阵I，Ma，Mb，Mc以及M2的基础组成：0Md =0�0�0�，Me =0�0�0�，Mf =0�0�0�。0（21）因此，我们在3D中旋转的基础Q3D = {Q3Dk}是由K= 80个元素组成的复合基础：�Q3Dk = ωC3D ∈ R3×3，�ω∈ {0.5，0.2，0.1，0.1，0.05}，0�C3D ∈0M d，-M d，M e，-M e，M f，-Mf}�。（22）类似于（14）-（17），通过量子退火获得3D情况下的最终QUBOP和非嵌入（即解码QUBOP的解），其中q ∈B81（q0保持不变为|1�，并且Qk在（17）中被Q3Dk替换）。06.量子点集配准0在点集配准中，输入的点集具有不同的基数，并且点之间的对应关系通常是未知的，即[x n] ∈ X ∈ R D × N和[y m]∈ Y ∈ R D × M，其中m ∈{1，...，M}。N和M分别是参考和模板中的点数，而D是点的维数。点集对齐的目标是恢复旋转R（R-1 =RT，det（R）=1）和平移t，将Y对齐到X。我们假设平移在预处理步骤中通过将点集的质心重合来解决。点集对齐可以通过在ICP方式中找到一些点匹配并估计给定对应关系的变换来交替求解AQC上的QUBOP。这将导致形式为（16）的QUBOP序列。为了将对齐表示为单个QUBOP，我们必须找到一个无需对应关系的能量函数，当在AQC上一次性最小化时，会得到最佳对齐。最近的文献中已经展示了所需的能量函数形式[29]。06.1.基于粒子动力学的对齐0Barnes-Hut刚性引力方法（BHRGA）[29]是一种最近的点集对齐方法，其具有单一的能量函数，在整个优化过程中保持不变。BHRGA是一种全局多重链接方法，即所有的 y m与所有的 x n相互作用。在[29]中，通过最小化相应粒子系统中的相互引力势能（GPE）E来对齐点集，该粒子系统在X引起的力场中。0E（R，t）= �0�0其中µym和µxn分别表示ym和xn的质量。在没有施加边界条件的情况下，粒子的初始质量为单位质量。在[29]中，（23）通过Levenberg-Marquardt算法[40，43]进行优化，并且当系统的GPE在局部最小时达到最优。没有2D树的加速，该方法具有二次复杂度，（23）涉及所有可能的模板和参考点之间的相互作用。现在，我们可以以与第5节类似的方式推导出QUBOP，用于变换估计。但是，请注意，基础（13）和（22）允许仿射变换和缩放。因此，我们将隐式地优化0E(R, t, s) = �0n µ y m  µ x n  ∥ R y m s  +  t  −  x n ∥2  ，(24)0其中标量s是模板的缩放。如[28]所证明，允许在全局多重链接点集对齐中进行缩放会导致模板收缩为一个单点的概率非常高。为了解决这个问题，可以使用先前的对应关系，或者将点交互限制在局部邻域[28]。在我们的QA中，我们选择了第二种解决方案，允许使用在第5节中详细说明的旋转基（13）和（22）。最终，用于点集对齐的Φ ∈R(K+1)×(D)(L(1)+L(2)+...+L(N))矩阵编码点之间的相互作用，如下所示：xTn[Q1ynL(n)]T−[Q2yn1 ]T−[Q2yn2 ]T. . .−[Q2ynL(n)]T............−[QKyn1 ]T−[QKyn2 ]T. . .−[QKynL(n)]T,(26)TEK1020304050e2D0.0230.0260.0410.0780.170.3σ2D0.0120.0130.0120.0120.0120.013eR0.0580.0620.0830.220.470.764σR0.0410.0440.0410.0360.0310.03The current generation of D-WAVE annealers does notsupport the precision of weights in P necessary for ourmethod [22]3. It is foreseeable that future generations willenable a higher accuracy for couplings. We thus implementand test QA with an AQC sampler on a conventional com-puter (Intel i7-6700K CPU with 32GB RAM). All quanti-tative tests are performed with 21 binary variables corre-sponding to the size of the Q basis in 2D.We report two error metrics, i.e., the alignment errore2D and the transformation discrepancy eR, together withtheir standard deviations denoted by σ2D and σR, respec-91880要解决这个问题，可以使用先前的对应关系，或者将点交互限制在局部邻域[28]。在我们的QA中，我们选择了第二种解决方案，允许使用在第5节中详细说明的旋转基（13）和（22）。最终，用于点集对齐的Φ ∈R(K+1)×(D)(L(1)+L(2)+...+L(N))矩阵编码点之间的相互作用，如下所示：0Φ = � Φ 1 Φ 2 . . . Φ N �，(25)0其中Φn，n ∈ {1,...,N}，的形式如下：0其中Qk如（13）或（22）所示，分别用于2D和3D情况。Φ1，Φ2和ΦN编码每个xn和相应的L(n)�M模板的点之间的相互作用，用上标{yn1，yn2，...，ynL(n)}表示。请注意，后者构建了{y1，y2，...，yM}的N个不同基数L(n)，平均为L。如果不同的xn与相同的ym交互作用，则可以仅计算Φn的子列�[Q1ym]T[Q2ym]T...[QKym]T�T一次并重用。用Φn表示的点集对齐的最终QUBOP如下所示（26）：0arg min q ∈ B K +1  q T ΦΦ T q. (27)0总共，K + 1 = 21和K + 1 =81个量子比特在2D和3D情况下需要在AQC上对齐点集。变换估计和点集对齐在相同维度上需要相同数量的量子比特，差异在于构建P的复杂度（参见第6.2节）。请注意，如果同一模板必须对齐到多个参考点，相应的Φ可以通过重用�[Q1ym]T[Q2ym]T...[QKym]T�T获得。0（只需计算一次）。q的第一个量子比特必须固定为|1�，因为每列的第一个元素包含一个参考点，在整个优化过程中必须处于活动状态。解嵌入类似于变换估计的情况，参见第5节。06.2. 准备复杂度 P = ΦΦ T0为了准备Φ，需要进行O(KDNξ)和O(KDN¯Lξ)次操作，分别用于变换估计和点集对齐。ξ表示将ym与加性基Qk的一个元素相乘的操作次数。为了获得最终的P，我们需要对Φ进行转置并将Φ与Φ T相乘，最坏情况下，变换估计需要O(K2DN)次操作，点集对齐需要O(K2DN¯L)次操作。与朴素方法相比，矩阵乘法还有稍快的算法[20]。0表2：在随机初始错配下，QA的准确性，用于变换估计（“TE”）和点集对齐（K > 1）。07. 实验评估0∥ X ∥ HS（∥∙∥HS表示Hilbert-Schmidt范数）衡量对齐形状与参考形状的一致性，并需要地面真实对应关系。变换差异定义为e R = �� I − RR T ��HS，其中R是恢复的旋转。它衡量恢复的变换与有效刚性变换的相似程度。使用两个互补的指标是必要的，因为低e R 不自动意味着准确的配准。另一方面，低e 2 D不量化恢复变换的刚性程度。数据集和概念验证。我们使用四个2D数据集，即鱼[46]、量子位、汉字和作曲家，基数从91（鱼）到7676（作曲家）不等，见图1的定性配准结果。对于点集，最多有几千个点，模拟时间τ P < 1秒。对于�7.7k，τ P增长到20.178秒（增加了�10^4倍）。当n =30时，模拟时间已经达到了�2.5天。更多的二进制变量允许在基础Q中有更多的元素，从而实现更准确的对齐。请注意，即使在80个量子位上，即n =80的问题上，AQC上的退火也需要大约100毫秒。在合理的时间内，即使在传统超级计算机上，也无法进行n =80的模拟。初始错配和点链接。我们测试了我们的方法在随机初始错配角度θ和不同大小的点链接区域下恢复变换的准确性。我们在鱼数据集的θ范围[0;2π]中生成500个随机变换，并使用QA解决它们，对于每个K ∈ {1, 10, 20,30}。结果总结在表2中。我们看到对于所有测试的K，e 2 D 与e R 相关。对于K =30，即对应于模板点的三分之一，两个指标仍然相对较低。我们还研究了点相互作用区域或K的选择如何影响变换恢复的准确性，并绘制了e 2 D 和e R作为K的函数，对于几个初始错配角度θ，见图3-A。根据奇异性定理[28]，通过全局多重链接对齐（这里，K =91）导致模板收缩为单个点，这在实验中观察到。接下来，我们在范围[0;2π]内系统地改变初始错配角度θ，以π/36的角度步长，报告e 2 D 和e R作为θ的函数，对于K ∈ {1, 10, 20, 30, 40,50}。这个测试揭示了由θ引起的变换之间的差异，这是由于所选择基础M的组合和表达能力引起的，见图3-B。QA对θ几乎是不敏感的，这是每个点集对齐方法的理想属性。对噪声的敏感性。我们系统地向模板添加均匀分布的噪声，并测试所提出的QA对数据中的异常值的鲁棒性，因为实际数据通常包含异常值。最高的模板噪声比率为50%。每个噪声比率和每个K的每个指标都是在50次运行中平均的，见图3-C。σ R 和σ 2 D都不超过0.057和0.03。我们观察到随着噪声水平的增加，对齐误差和获得的变换之间的差异都增加。然而，对于较小的K，即使噪声比率较大，指标似乎也不会显著影响。谱间隙分析。谱间隙∆( ˆ H)是基态能量和第二低能态之间的差异。每个问题都有一个固有且独特的∆( ˆ H)。尽管对谱间隙的严格分析超出了本文的范围，但我们对QA的能量景观、能量值的差异以及一个示例问题的相应配准进行了几个定性观察。在图4中，我们绘制了se-03代目当前支持9位浮点数11019283746556473829100.511.511019283746556473829100.20.40.60.81CoCoCoCoCoCo= 00.791.572.363.143.934.715.500.20.40.60.800.791.572.363.143.934.715.500.10.20.30.440 500 510152025303540455000.050.10.150.20 510152025303540455000.020.040.060.08noise ratio, % (template)noise ratio, % (template)1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2500.010.1110100Column BColumn CColumn D1 5 9 13 17 21 2516111621900110013001500170019002100230025002700energy-decreasing transitionenergy-decreasing transitionenergyenergyK = 1K = 3091890K0A