量子置换同步：基于量子算法的计算机视觉同步问题解决方案

13122量子置换同步Tolga Birdal1，Vladislav Golyanik2，Christian Theobalt2LeonidasGuibas11斯坦福大学2马克斯普朗克信息学研究所，SIC摘要我们提出了QuantumSync，第一个量子算法解决同步问题的背景下，计算机视觉。特别是，我们专注于置换同步，其中涉及解决非凸优化问题的离散变量。首先，我们制定成一个二次无约束二进制优化问题（QUBO）的同步。虽然这样的表述尊重问题的二元性质，但确保结果是一组排列需要额外的注意。因此，我们：（i）展示如何将置换约束插入到QUBO问题中，以及（ii）在当前一代绝热量子计算机D-Wave上解决受约束的QUBO问题。由于量子退火，我们保证了高概率的全局最优性，同时对能量景观进行采样以产生置信度估计。我们在绝热D-Wave计算机上实现的概念证明表明，量子机器为解决普遍但困难的同步问题提供了一种有前途的1. 介绍计算机视觉文献提供了大量高效和有效的方法来处理来自广泛使用的2D和3D相机的丰富信息我们处理的许多算法都擅长处理单帧或图像序列，如视频[82，34，13]。通常，场景可以由多个相机从不同的、通常未知的视点观察。到目前为止，如何在不遵守任何特定顺序的情况下一致地组合所获得的多视图提示仍然是一个悬而未决的问题[44]。同步[91，42，92]是对上述问题提出的解决方案之一抽象地说，它涉及在连接多个视点的图上分布差异，使得估计在所有考虑的节点上是为此，同步化同时将成对的局部信息平均为全局信息[48，54，4，12]。 本程序 是大多数最先进的多视图的基础部分，两位作者对这项工作的图1. QuantumSync概述。QuantumSync将置换同步公式化为QUBO，并将其逻辑实例嵌入到量子计算机上。在运行多次退火后，它选择能量最低的解作为全局最优解。重建和多形状分析管道[85，23，25]，因为它在尊重参数的几何形状的同时大大提升了全局约束满足。事实上，大多数多视图一致性推理问题都可以表示为某种形式的同步[107，15]。在本文中，我们的重点是置换同步，其中图的边缘标记的置换矩阵表示之间的对应关系，无论是两个二维图像或两个三维形状。具体地说，我们试图找到一个绝对排序为每个帧的每个点，所有相应的点到同一个bin排序。不幸的是，这个问题根据定义涉及组合非凸优化，对于该组合非凸优化，在针对经典冯诺依曼计算机的标准公式下，获得全局最小值是难以处理的。这种困难促使学者们寻求连续松弛，对于连续松弛，可以找到好的局部最优解[14，16]或封闭形式解[6，57，5]。然后，理想情况下，我们希望避免这种近似，并使用手头的原始约束集。这正是我们建议在这项工作中要做的。因为在经典计算机上，我们不能说我们的离散问题的全局最优性保证，所以我们将注意力转向一个新的处理器家族，即，量子计算机Qubo制剂次要嵌入溶液量子退火解嵌入逻辑问题13123量子计算机是利用量子效应（诸如量子超置、纠缠、隧穿和上下文）来解决众所周知困难的问题（即，NP-hard）在经典计算机上。许多量子算法已经证明了改进的计算复杂性，最终达到了预期的优势[7]。目前，我们看到了量子计算机的第一次实际应用，这要归功于可编程的量子处理单元（QPU），可供研究界使用，如D-Wave [2]或IBM [1]。由于新一代计算机提供了一个完全不同的计算范式，直接移植经典的问题公式是远远不够的。事实上，我们经常需要完全修改手头的问题[49]。本文给出了如何用量子计算机友好的二次非约束二元优化（QUBO）来QUBO优化二进制变量，而不是排列，因此，我们需要确保在优化过程中遵守排列约束。为此，我们将所有的约束转化为线性约束，并将它们合并到QUBO中.最后，我们将我们的问题嵌入到一个真正的量子计算机中，并表明它很有可能实现最低能量的解决方案，即全局最优解（见图1）。我们的贡献如下：1. 第一，据我们所知，以绝热量子计算机（AQC）可消耗的形式表述经典同步;2. 我们展示了如何将置换作为线性约束引入QUBO问题;3. 我们数值验证了我们的配方在模拟实验中的有效性，以及在一个真正的AQC（第一次，在D-Wave的优势1。1）、4. 我们进行广泛的消融研究，这种新的计算方式。我们获得了高度可能的全局最优解，达到以下任一值：(i)八个视图和每个视图三个点，（ii）七个视图和四个点，或（iii）五个视图和三个点。我们首次在具有5k量子位的AQC上进行实验，并与经典方法进行了广泛的评估和比较。我们的方法也可以被归类为第一种方法的量子匹配的多个点集。虽然我们是第一个在量子硬件上实现同步的人，但我们的评估和测试是概念的证明，因为真正实用的量子计算仍然是一个飞跃。2. 相关工作同步。当涉及到将图像/形状集合上的函数统一起来时，从比率集合中一致地恢复绝对量的艺术，同步，现在是事实上的选择[85，23，25]。这个问题现在研究得很好，的算法。首先，在不同的应用中出现了大量关于群结构的工作[48，47，16，5，4，56，54，4，100，28，96，98，6，9]。 一些亲-定解是封闭形式[6，5，72，4]或最小化鲁棒损失[53，27]。其他解决可证明性[83]和全局最优性[21]。还考虑了贝叶斯处理或不确定性量化[97，14，12，16]以及低秩矩阵分解[10]。最近的算法倾向于将同步纳入深度学习[58，43]。这项工作涉及同步对应集，也称为置换同步（PS）[81]。这个子领域也吸引了大量的关注：低秩公式[104，101]，凸规划[55]，多图匹配[86]，分布优化[55]或黎曼优化[16]。所有这些方法都试图以这样或那样的方式处理同步问题的内在非凸性。不幸的是，在经典计算机上解决我们的问题是出了名的困难。据我们所知，我们是第一个通过绝热量子计算这一新范式来解决这一问题的人。量子计算。自20世纪80年代以来，量子计算已经成为一个活跃的研究领域，无论是从硬件[30，61，36，102，73，111，65，68，66]和算法侧[89，90，17，49，38，51，99，52，31、3、70、87、75、37、108、94]。与经典方法相比，量子方法提供的加速已经在应用数论[89，17，99，37]，线性代数[51，52，67，95，94]，机器学习[3，70，108]和物理系统模拟[106，79，11，62，59]等领域得到了证明。量子退火（QA）[60，22]和Farhi等人 [38]提出的绝热量子演化算法，推动了绝热量子计算机（AQC）的发展。在过去的十年中，该技术已经成熟，并在D-Wave的帮助下可以远程访问以进行测试和研究[32]。D-Wave AQC [33]最近的基准测试表明，对于具有大而高的障碍的能量景观，量子退火可以实现与在单核上运行的模拟退火[63]相比高达8个数量级的速度提升。AQC也已成功应用于交通流优化，同时优于经典方法[75]。量子计算机视觉。在文献中已经提出了几种用于计算机视觉问题的量子方法，包括图像识别算法[76]，分类[20，78]和通过低秩矩阵分解的面部特征学习[80]。最近，D-Wave已被应用于物体检测中的冗余物体去除[69]。虽然文献[84]中已经知道非最大值抑制的QUBO公式，但在[69]中已针对D-Wave 2X进行了改进，其解决方案优于几种经典方法。点的量子方法13124IJJ集合对齐[45，46]解决了与我们相关的问题。它用基元逼近仿射空间中的旋转矩阵，基元可根据测量的位串求和。然而，该公式不能容易地扩展到多视图的情况下，不支持置换约束。相比之下，我们的方法解决了多路匹配问题，并且我们成功地将其部署在真正的AQC Advantage 1上。1.一、我们对赋值约束的使用也是新的。与此同时，Benkner等人提出了类似形式的置换矩阵约束。[88]这是一个非常好的例子。以前的一些Stol- lenwerk等[93]解决AQC上的航班分配问题。图同构问题的公式化可以包括置换[110，41]。在[110]中，为图中相同度数的每个顶点对分配了一个单独的变量，这随后导致了QUBO。置换也可以转换为一个表，其中二进制条目作为惩罚项添加到目标哈密顿量[41]。3. 材料和技术背景3.1. 同步我们将多视图配置建模为连通无向图G =（V={1，2，. . . ，n}，E <$[n] × [n]），其中|E|= m且若（i，j）∈ E则（j，i）∈ E。 每个顶点vi∈ V（例如，图像）与域Di相关联（例如，有序点）。每个边（i，j）∈ E用函数fi ，j标记：Di → D j（例如，通信）。我们将边相关的实体称为相对实体，将节点（顶点）相关的实体称为绝对实体。因此，我们恰当地称{fi ，j}i，j为相对映射。在本节中，我们定义并解释图1之后的必要概念二、本节中给出的定理的证明可以在我们的补充材料中找到定义1（路径、周期和循环）。 我们将路径定义为有序的、唯一的索引序列p={（i1，i2），（i2，i3），· · ·，（in−1，in）}∈ P沿G连通图2. （左）我们考虑的一般设置的标记和说明，（右）循环一致性与路径不变性。定义3（周期一致性）。我们称图G在C上是圈相容的，如果fc=f∈C，其中C是所有圈的集合[50]。有向图的循环一致性的概念被称为路径不变性[107]，与图1所示的循环一致性不同二、 在本文中，我们进一步假设这些映射属于一般线性群，并且是同构的，即，fji=f −1。备注1. 取决于图形拓扑，圈的数目可以是顶点数目的指数。因此，单纯地根据Dfn保证大型图的一致性。3、迅速变得棘手。Guibas et al. [50]的目的是满足一个子集的循环C<$C（基地）的一致性，其中强制一致性沿这些循环诱导一致性沿所有循环的输入图G。然而，由于这些循环一致性基的有效选择[105]是一个正在研究的问题，我们使用可用的组结构：定理1（构造的循环一致性）。当re（D，n）形成具有运算π的群时，可以通过对所有i和j满足以下约束来一致的顶点标记{fi：V<$→Di}ifi，j= fi<$f −1。（二）vi1 到vin. 它被称为一个循环，如果另外的路径跟踪j返回到起始节点。最后，在[4]之后，我们表示一个圈c∈ C是G的零圈，如果沿着c的函数的合成导致恒等变换：fc=f1，2<$f2，3·· ·<$f（n−1），n<$fn，1=f<$，（1）因此，等式（2）被称为循环一致性约束。定义4（同步）。同步是在给定比率{fi，j}i，j的集合的情况下找到G的一致标记的过程，确保G的循环一致性：其中f∈（x）=x，f ∈ x∈D1是恒等映射，fc表示复合函数. 直观地说，c是一条非空路径，其中唯一重复的顶点是第一个和最后一个argmin{fk}kΣ（i，j）∈Ed（f∈i，j，fi，j）.（三）顶点。 请注意，f<$i，j=fi<$f−1是估计的比率，d（·）是一个群，（例如，f1，2f2，3f2，3f1，2），并符合《公约》的规定。特定距离度量。定义2（k-循环）。 我们把一个顶点映射到自身的函数称为1-圈：fi，i= f。类似地，一个2-循环将是fc= fi，j<$fj，i，依此类推[77，57]。备注2. 仔细观察这个问题，发现它是非凸的，因为组合，但凸时，顶点fj是固定的，在优化fi。其实如果路径1周期地图（空）周期顶点路径不变性循环一致性13125nJJnnfi被认为是固定的，则该问题类似于在度量d（·）下的平均。对于不同的i，我们需要计算不同的平均值，同步通常被称为多重平均[40，54，26，53]。定理2（规范自由度）。DFN中的问题。4是受自由选择的参考或规格[8，26]。换句话说，方程（3）的解集可以通过公共fg任意变换，即 fi<$fi<$fg，同时仍然满足一致性约束。在实践中，通过将其中一个顶点标签设置为恒等式来固定规范：f1=f。定义5（置换矩阵）。置换矩阵被定义为稀疏的平方二进制矩阵，其中每列或行仅包含单个非零项：Pn：={P∈ {0，1} n×n：P1n= 1n，1<$P = 1<$}.（四）其中1n表示n维1向量。每个P∈Pn是全置换矩阵，且Pi j=1意味着到AQA AQA将s和Q分别解释为量子位偏置和耦合，并将它们转换为退火期间施加在量子位上的QPU上的局部磁场，即，量子力学计算系统的自由演化。通过优化n个量子位的隐藏1状态来执行最佳x的搜索，并因此将其解嵌入和测量为经典位串。然后将后者传递到解解释步骤，该步骤在原始问题的上下文中对它们进行解码。在退火之前，所有n个量子比特都在初始哈密顿量H1的基态中初始化，该初始哈密顿量H 1容易实现为具有相等测量概率的叠加。|0或|每个量子位1个量子位。哈密顿量是定义系统能谱的算子，并解释为计算问题-所有可能的解决方案的空间。AQA执行一系列退火，在此期间，在局部磁场的影响下，HI不断地向问题哈密顿量HP变化。该瞬时哈密顿量H可以表示为：点i被映射到元素j。注意，P= P−1。 我们还将m个置换的乘积流形记为Pm。H（τ）=[1−τ]HI+τHP 、（六）定义6（相对排列）。 我们定义置换矩阵为相对映射，如果置换矩阵是两个群元素（i→j）的比（或差）：Pij= PiP.定义7（置换同步问题）。对于一组冗余的比率测量{Pi j} ， 置 换 同 步 [81] 试 图 恢 复 {Pi} ， 其 中 i=1，. . . ，N，使得满足等式（2）：Pij= PiP−1。如果输入数据被噪声破坏，则该一致性将不保持，并且为了恢复绝对排列{Pi}，某种形式的一致性误差被最小化。3.2. 绝热量子计算当代AQC可以在以下形式的一组伪布尔函数上求解QUBO：arg minx Qx+sx，（5）x∈Bn其中Bn表示长度为n的二元向量集，Q∈Rn×n是实对称矩阵，s是实n维向量.（5）是一个常见的问题，已知在经典计算机上是NP-困难AQA使用遵守量子力学定律的量子比特进行操作与经典位相反，量子位|φ可以在状态之间连续地转换|0>和|1π（经典态0和1的等价物）满足方程|φ=α|0>+ β|1π，概率幅满足|α|2个以上|β|2= 1。针对非QUBO形式的问题的AQA算法首先必须将问题为QUBO（5），其根据逻辑量子位和它们之间的权重（s和Q）来定义逻辑问题则是次要的-嵌入式的其中局部时间变量τ∈[0; 1]在退火时间t期间从0转变到1（例如，20µs）。根据量子力学的绝热定理[19]，假设t足够长并且尽管问题的能量景观高度非凸，系统在退火结束时将可能保持在HP这是由于叠加、纠缠和隧穿的量子效应。叠加使得能够同时对所有可能的量子位状态进行优化;它允许在由n个量子位跨越的2n 在量子计算过程中，会产生纠缠态，即，多个量子比特的状态不能相互独立地描述隧道能够通过屏障过渡（几何解释）。关于AQC基础的更全面的概述，请参见[60，38，2]以及Secs。2和3 [45]。4. 量子同步假设一个多视图配置，其中在m个视图中的每个视图中给我们n个点。视图i中的点通过置换Pij与视图j中的点相关（参见第2节）。3.1）。Pij通常是针对边集合E中的每一对独立地获得的，因此是有噪声的。在[16]之后，我们将置换同步视为概率推理问题，其中我们将对以下量感兴趣：1. 最大后验概率（MAP）：X=arg max log p（X|P）（7）X∈Pmn1在这个意义上说，α，β不能被揭示（测量假设）和非破坏性复制的|不可能（无克隆定理[103]）13126我我JF其中log p（X|P）=+−βCUP−XX2，真的对于离散变量，当Q′不为正定义时，（i，j）∈E ijiJF并且=+表示直到加法常数的相等2. 全后验分布：p（X|P）n（P，X）.这里，X表示所寻找的排列的整体，并且类似地，P是所有指定的成对排列的集合MAP估计值通常更容易获得在实践中很有用。另一方面，来自完整后验的样本可以提供重要的附加信息，例如不确定性。毫不奇怪，后者是一个更困难的任务，特别是考虑到我们的问题的离散性每个AQC算法都包括问题编码、次嵌入、采样和解的解释，如第2节所述。3.2.在下文中，我们将描述问题编码和等式（5）中的Q4.1.作为QUBO的我们首先将等式（7）中的同步损失重写为对于绝热优化更友好的二次分配问题（QAP），并且稍后将置换作为线性约束插入到公式中。提案1. Frobenius范数下的置换同步可以用QUBO来表示：Σ这是NP-困难整数二次问题的一个变种lem.我们将展示如何使用最近的量子计算机来获得全局最小值。制定的QUBO同步。的方程（11）中的问题具有额外的困难，置换乘积流形上的具体组合优化问题。用不同的矩阵选择替换置换会导致不同的松弛，例如：（i）正性允许半定规划[57]，（ii）正交性允许谱解[72]，（iii）双重随机松弛可以允许黎曼优化[16] 。 然 而 ， 所 有 这 些 方 法 都 必 须 遵 循 到 离 散Permutohedron上的投影步骤，通常被视为分配问题，并通过著名的匈牙利算法求解。QUBO使我们能够以全局最优的方式在没有连续松弛的情况下解决这个问题，通过根据我们所掌握的二进制变量B重新表述等式（11argmin x<$Q′x.（十二）x∈B排列作为线性约束。二进制变量x∈ B是乘积置换的超集。 换句arg min{X∈P}<$P ij− XiX<$$>2= arg minx<$Q′x。{X∈P}换句话说，方程（11）的解不需要导致置换。一旦对应于每个节点的矩阵被执行，in（i，j）∈EIn- 是的我们建议鼓励解决方案朝着一套这里，x=[·· ·x·· ·]且xi=vec（Xi），其中vec（·）充当矢量化器。Q′则是以下形式的矩阵IP11 IP12···IP1m通过引入线性约束Ax = b来优化置换，使得优化遵循置换的定义：如等式（4）中的行和列总和为1。给定xi=vec（Xi），这意味着bi=1，IΣ⊤ΣQ′=−... .- 是的（八）.Ai=第一章1.（十三）- 是 的...1美元I Pm1 I Pm2· · · I Pmm证据这些步骤是直观的遵循和扩大证明包括在补充材料：简 单 地 说 ， 矩 阵 Ai 的 组 合 如 下 ： 在 行 j 中 ，1≤j≤n，1被放置在列（j−1）·n+1到（j）·n中。在j > n的行j中，对于p ∈ {0，.，n − 1}。执行ΣX = arg minP-XX2（九）所有个体xi2X∈Pmn（i，j）∈E伊日JFΣx∈Rn×m，我们构造了一个n2×2n块对角矩阵A= diag（A 1，A 2，. . . ，Am）。=arg min 2N2n−2X∈PmnΣ（i，j）∈Etr（XjXPij）（10）在QUBO中引入线性约束。现在，我们通过引入等式约束来扩展我们的公式=arg min−X∈Pmn（i，j）∈Evec（Xi）vec（Xj）Ax= b的最优化。2号提案 约束最小化：= argmin x<$Q′x.（十一）X∈Pmn这个问题的Hessian由Q′本身给出因此，当Q′是正定的时，该问题是凸的，可以用邻域点法或信赖域法等算法求解.不确定问题可以通过有效集方法来解决，如果变量被放松到argmin xQ′xs.t.Ax= b（14）x∈B可以变成（不受约束的）QUBOarg minx Qx+sx，（15）x∈B其中Q=Q′+λA<$A且s=−2λA<$b。13127表1.在Willow数据集上进行评估穷举EIGALSLIFTBirkhoffD-Wave（我们的）Q′和Q都是稀疏矩阵。 我们提供了它们的稀疏模式和Prop的证明。2在我们的补充。最后，我们将修改后的QUBO（Q，s）映射到D-Wave上。图3.一个来自Willow Object Classes的随机汽车示例[29]。现有技术的方法MatchEIG [72]、MatchALS [109]、Match-Lift [57]、MatchBirkhoff [16]以及通过列举所有可能的置换获得的解析解在我们所有的评估中，我们报告的位编码、采样和解释。 我们通过让第一个矩阵为单位矩阵来固定规范：X1 =I.一旦QuantumSync终止，测量的位串可以直接解释为重新排序为m − 1个n × n维矩阵后的解排列。 为了解释后面的景观，我们建议使用相同的量子退火从许多低能态中采样。进一步详情载于补编。5. 实验和评价真实数据集。 去展示量子计算机- 作为解决具有挑战性的多视图匹配问题的一种有前途的方法，我们提取了四个类别（鸭子、汽车、酒瓶、摩托车）的Willow对象类[29]，每个类别由40个RGB图像组成，在野外采集（见图3）。这些图像受到显著的姿势、光照和环境变化的影响。因此，在每个图像上手动注释十个关键点我们使用这些关键点中的前四个我们遵循[101]并使用Alexnet [64]在Ima-geNet [35]上预训练，从一组以注释地标为中心的227×227然后通过匈牙利算法[74]匹配Conv4和Conv5层的特征映射响应以初始化同步。由于数据是手动标注的，因此地面实况相对图是已知的。合成数据集。为了对我们的方法进行受控评估，类似于[16]，我们生成由m = |V|节点和|E|= m（m −1）条边。 在每个节点i处，我们生成n个点，这些点可通过置换Pij映射到节点j处的n个其他点。因此，所有置换矩阵Pi或Pij是总和，即， 尺寸为n × n。虽然图默认是完全连接的，但在某些实验中，我们随机删除某些边以具有完全性C，其中0。55·105次退火）。我们在我们的补充中展示了示例性的嵌入对真实数据集的评估。首先，我们对D-Wave进行了同步实际数据的测试.选项卡. 1显示了我们为不同类别获得的最佳（最低能量）解决方案的准确性，以及所有类别的平均值。可以看出，虽然量子解决方案不是最好的，但它肯定与精心设计的方法相当，0.950.90.850.80.75汽车鸭摩托车酒瓶图4.来自量子退火机的样品有助于提高溶液质量或报告不确定性。车鸭子摩托车酒瓶平均0.84± 0.104 0.91± 0.115 0.82± 0.10 0.95± 0.096 0.88± 0.1040.810.083 0.86± 0.102 0.77± 0.059 0.87± 0.107 0.83± 0.0880.84±0.0950.90± 0.102 0.81± 0.078 0.94± 0.092 0.87± 0.0920.84±0.1020.90± 0.103 0.81± 0.078 0.94± 0.092 0.87± 0.0940.84±0.0940.90± 0.107 0.81± 0.079 0.94± 0.093 0.87± 0.0930.84±0.1040.90± 0.104 0.81± 0.0800.93±0.095 0.87± 0.096单最佳2最佳3-最佳4-最佳5-最佳6-最佳13128n10.950.90.850.80.751(a) 精度与噪声穷举匹配EIG匹配ALS匹配Lift匹配BirkhoffmatchQuantum（我们的）0.05 0.1 0.15 0.20.25(b) 精度与完整性10.950.90.851(c) 精度与问题大小102030405060708090100(d) 准确性与完整性（有噪声）150010005000（一）2520N=3N=415N=51050（b）第（1）款20015010050034（c）第（1）款86540.980.952 4 6 82 4 6 8Nm0.960.940.920.90.5 0.6 0.7 0.80.90.850.80.750.5 0.6 0.7 0.8图6.对于不同的n和增加的视图数量m，（a）绘制映射问题所需的量子位数;以及（b）在x= 3时。0，显示了在Advantage 1上嵌入问题所需的最大链长度。1.一、 （c）绘制平均数-图5.对合成数据集的评价（n = 4，m = 4）。此外，在理论上，它享受多项式加速。请注意，穷举解决方案在此数据集上执行得最好。这进一步鼓励了关于制造更好的量子计算机的研究，以缩小真实和机器计算的最优值之间的差距。后面的解释。虽然不是真正的贝叶斯推断，但量子退火可以提供来自能量景观或哈密顿量的样本例如，样本可以用于将置信度与解决方案相关联，或者可以用于像主动学习这样的场景为了评估样本的可用性，我们不是查看最低能量解决方案，而是查看先前真实数据评估的k-最低能量解决方案我们联合处理它们，并通过将它们替换为所有样本中最频繁的错误位来纠正错误位。图4示出了在真实基准上，随着k值的增加，准确度也增加。这验证了来自量子退火器的不同样本可以在探索能量景观时提供信息，即，后定义在Sec.四、对合成数据集的评估。我们现在询问我们的量子方法的各种特性，量子同步。我们的结果绘制在图中。五、首先，我们检查在增加噪音下的行为图图5（a）示出了所有方法都可以处理低噪声状态。不断增加的噪音同样影响了我们测试的方法我们的方法虽然不比任何方法优越，但也不相上下。图5（b）显示QuantumSync受到增加的问题大小（mn2）的显著影响。 这可能表明了当前量子计算机最重要的局限性，即， 我们只能可靠地处理尺寸64的问题<。请注意，这也是我们真正的子Willow数据集的大小其余的图（c，d）显示了连通性（图完整性）对解决方案质量的影响 噪声（σ = 0。1）稀疏图会导致严重的问题。参数选择。我们现在评估，与我们的合成数据的帮助下，如何解决方案和它的概率变化w.r.t.链强度χ和λ。两个参数在200个样本中测量的最优解的BER，对于不同的n和m对（平均50次重复）。导致链条断裂，但在许多情况下，可以通过多数表决解决。最初的试验实验帮助我们确定χ=3。0且λ=2。5作为最优参数，在我们的实验中保持不变。请注意，在第二节中，在经典计算机上对λ进行的消融研究。5.2也表明λ >2。0作为（n，m）的范围的合适值。选项卡. 图2突出显示了在n=3，m=3和n=4，m=4的检验中改变χ对优势1的影响。1.一、我们报告了目标问题的逻辑量子位数nl，将问题嵌入AQCnph所需的物理量子位数，嵌入的平均最大链长l和导致200个样本中的最优解的平均退火次数。每个X的每个测试重复50次。表2.该表总结了对于n= 3，m= 3（第一行）和n= 4，m=4（第二行），改变链强度X对200个测量的最优解的数量的影响nl/nph/l=1=2=3=4=518/48/3. 2120 9±48。8187. 8±11。5180 9±11。两千一百五3±19。九点八五。3± 23。6第48/325/9号决议所设委员会50的情况。1±0。309 .第九条。9±10。08十七岁3±14。0六、1±7。771 .一、42 ±2。72不同的问题大小和较小的嵌入。接下来，我们系统地分析了哪些问题规模可以成功地嵌入到Advantage系统的Pegasus拓扑结构上1.1 并且以超过200个样本的高概率全局最优地求解在可以在D-Wave上成功求解的n和m的每个配置中，我们报告了对应于全局最优值的平均测量次数及其在50次重复中的标准差，每次退火200次。我们还在相同的实验中分析了小嵌入，并报告了嵌入中使用的物理量子位的平均数量，最大链长及其50次运行的标准差。图6显示了实验结果。我们看到，随着逻辑量子比特数量的增加，嵌入所需的物理量子比特数量以及最大链长也会增加（图6-（a），（b））。 对于n=3强烈影响的概率来衡量最优解，m=3时，比例为c=nphL2002年。65岁 它增加到选项。χ太高保持链在过程中不断裂，退火，但对溶液产生不利影响。 x太低c14. 5，n=5，m=5。这并不奇怪，由于较长的量子比特链增加了链的概率，发生次数13129二进制置换(c)二进制约束的精度w.r.t.(a) 二进制的能量与置换变量04540-2035-403025-6020-801510-1005-12000 1 2 3 4 511(b) 最低能量之间的差距Exp -1实验-2实验3Exp -4实验-5实验-6实验-70 1 2 3 4 5-48-50-52-54-56-58-60-62-64(a) 约束对能量的影响二元约束置换0个0. 1个0.20.30.40.50.60.70.8个单位互换比率10.950.90.850.80.750.70.65(b) 精度与噪声0个0. 1个0.20.30.40.50.60.70.8个单位互换比率0.90.80.70.60.50.950.90.850.80.750.70.65图8.噪声对优化二元变量或置换矩阵切。（a）当解被限制为二进制变量或置换矩阵时的能级。（b）这两个限制解所达到的精度。0.40 1 2 3 450.60 1 2 3 4 5和b），对于各种各样的λ-选择，图7.用一类问题的穷举法研究了这一问题，sical计算机 我们解决了七个随机合成问题，其中n= 3，m= 1，|V| =3，σ= 0。2通过搜索二进制变量（二进制）或置换矩阵（perm.）为了全局最优。我们显示：（a）两种情况下获得的能量，（b）（a）中最低能量之间的差距（绝对差），（c）作为二进制约束的正则化子（λ）的函数的正确猜测位的比率，（d）中的相同图。(c) 但对于置换矩阵。 注意，由于噪音太大，全局最优值并不总是与地面实况相同。中断，并因此降低了测量最优解的总概率图图6-（c）示出了对于变化的n和m，200个中的最佳测量的数量。 我们看到，我们的QuantumSync可以解决n=3，m=8的情况，并且有概率在单个退火ρ=4中测量最优解。39%; n=4，m=4，ρ=12。n=5，m=4，ρ1%。同时，对于n=3，m= 7的问题，ρ >62%。请注意，某些问题由于其大小而无法映射到D-Wave，因此我们无法报告这些问题的统计数据5.2. 经典计算机上的烧蚀研究现在，我们研究的全球最小值的经典计算机上的问题，我们设计了7个随机的问题的情况下，是全球可解的标准硬件。因此，我们选择n=3，m=| V|=3且C=1（全连通图）。对于这样一个小的尺寸，我们可以并行搜索的全局最优的二元变量和置换矩阵。请注意，虽然后者是合理的（实际的）搜索空间，但AQC只能在前者上进行优化。因此，我们有兴趣量化两者之间的差距，并验证我们的公式确实允许QUBO求解器实现手头问题的全局最优解。如何选择正则化系数λ？系数λ是我们算法中最重要的超参数之一，因为它平衡了数据项与置换惩罚。因此，我们研究它的行为。图 7表明，在σ = 0的七个实验中。2，而两种解决方案之间的最低能量可以不同（a通过二进制优化和置换优化可以非常具有可比性（cvsd）。只要λ不小（例如，< 2），我们观察到几乎相同的性能。这个肯定的结果促使我们满足于一个单一的值λ=2。5、我们所有的评价（包括SEC）5.1）。置换约束有效吗？ 由于D-Wave不能在排列上搜索，而只能在二进制变量上搜索，所以我们有兴趣看看我们的排列性正则化是否真的有效。为了研究这一点，我们设计了随机实验（n=3，m=3），增加噪声（交换比），其中GT是已知的。然后，我们形成的约束Q矩阵，并解决它通过穷举搜索的经典计算机上。平均超过七个实验，图。8表明：（i）对于低噪声状态，在一般二元变量B或排列P上的优化是无关紧要的，并且总是可以找到全局最优值，（ii）对于较高的噪声水平，虽然获得的能量似乎不同，但最终精度非常相似。因此，我们得出结论，注入置换约束到Q的提议是有用的，并使之有可能使用二进制变量，而不是置换。这证明了为什么像D-Wave这样的绝热计算机可以获得全局最优解。6. 结论我们介绍了QuantumSync，第一个量子同步方法我们特别关注排列组，并展示了如何为绝热计算机制定这样的问题。然后，我们使用尖端的量子硬件来解决具有全局保证的现实问题我们的前瞻性实验表明，量子计算硬件已经达到了可以应用于现实世界问题的水平，具有很大的潜力来改进已知的经典方法。我们相信，我们的技术可以激发新一代更好的出租车相关和其他计算机视觉问题，我们希望看到更多的工作在该领域在不久的将来。致谢。这项工作得到了ERC Grant 4DReply（770784）、Vannevar Bush学院奖学金、斯坦福-福特联盟的资助以及亚马逊AWS和Snap公司的礼物的支持。(d)准确的烫发。限制条件w.r.t.%正确位%正确位%正确位13130引用[1]Ibm q 体 验 。 https ： //quantum-computing.ibm.com。于2021年1月17日访问。[2]d 波 量 子 处 理 装 置 的 技 术 说 明 。https://docs.dwavesys.com/docs/latest/doc_qpu.html。于2021年1月17日访问。[3]埃斯玛·艾默，吉勒·巴拉德，塞巴斯蒂安·甘布斯。无监督学习的量子加速。Machine Learning，90（2）：261[4]Federica Arrigoni和Andrea Fusiello。计算机视觉中的同步问题及其封闭解。国际计算机视觉杂志（IJCV），2019年。[5]Federica Arrigoni，Eleonora Maset，and Andrea Fusiello.对 称 逆 半 群 中 的 同 步 国 际 图 像 分 析 与 处 理 会 议（ICIAP），第70-81页，2017年[6]Federica Arrigoni，Beatrice Rossi，and Andrea Fusiello.se中多视图的谱同步（3）。SIAM Journal on ImagingSciences，9（4）：1963[7]Frank Arute ， Kunal Arya ， Ryan Babbush ， DaveBacon ， Joseph C. 放 大 图 片 作 者 ： Bardin ， RamiBarends，Rupak Biswas，Sergio Boixo，Fernando G. S.L.作者：David A. Buell等人，《使用可编程超导处理器的量子霸权》。Nature，574（7779）：505[8]瓦迪姆·别洛夫论规范引力的经典和量子理论中的几何和对称性。arXiv：1905.06931，2019。[9]Florian Bernard ， Johan Thunberg ， Peter Gemmar ，Frank Hertel，Andreas Husch，and Jorge Goncalves.通过变换同步的多对准的解决方案。在计算机视觉和模式识别（CVPR）中，第2161-2169页[10]Florian Bernard，Joha