量子计算（QC）被认为是计算领域的下一个重大进展，在组合优化等多个领域具有巨大潜力。在这一领域，量子计算能够以与传统方法根本不同的方式解决问题，从而可能带来显著优势。
尽管潜力巨大，但我们目前仍处于“噪声中等规模量子（NISQ）”[1]时代，这意味着该技术仍处于早期发展阶段，并面临硬件限制。这些限制包括量子比特（qubits）的质量不佳，导致不良行为，以及处理器中量子比特和耦合器（量子比特对之间的连接）的数量较少。尽管存在这些限制，人们仍在深入研究这一范式的软件和算法方面。许多研究旨在克服这些限制，充分发挥当前NISQ时代量子计算机的潜力。相关研究领域包括设计结合经典和量子处理器的混合方法[2]、[3]、[4]，以及错误校正和错误缓解技术[5]、[6]。
在各种类型的量子计算机中，门模型（gate-model）和量子退火（quantum annealing）最为突出。本研究聚焦于后者。量子退火基于Farhi等人最初提出的绝热量子计算（adiabatic quantum computing）原理[7]。绝热量子计算首先将量子系统初始化到一个易于准备的基态，然后在其时间依赖的哈密顿量（Hamiltonian）的演化过程中逐渐达到最终形态，其中所需计算的状态被编码为基态。通过足够缓慢的演化过程，根据绝热定理，系统最终状态为所需基态的概率很高。量子退火通过放宽对缓慢演化的要求来改进这一方法，这种放宽程度取决于具体问题，可能非常复杂。这种放宽使得执行时间加快，但达到基态的概率相应降低。
构建量子退火器的模型有多种，例如基于Rydberg原子[9]、陷阱离子[10]或超导磁通量子比特[11]的模型，其中后者是目前最被认可的类型。此外，多家公司正在开发自己的设备，如NEC、Qilimanjaro和D-Wave Systems。
在文献中，参考的量子退火器是D-Wave Systems开发的那些，它们专门用于通过采样给定哈密顿量的低能量状态来解决伊辛模型[12]。因此，这些退火器放弃了通用量子退火的计算通用性。然而，伊辛模型在数学上等同于解决二次无约束二进制优化（QUBO）问题，许多组合优化问题可以表述为QUBO问题[13]，进而转化为伊辛模型[14]。
本研究全面分析了“次级嵌入”问题，这是一个图论问题，旨在将伊辛模型的变量映射到量子退火处理器上。其动机在于观察到D-Wave处理器在处理硬件原生问题和具有通用拓扑结构的实际优化问题时的性能差异。具体而言，当量子退火器解决与其架构相匹配的问题时，其性能可与某些经典求解器相媲美，从而无需进行次级嵌入[15]、[16]。然而，当应用于伊辛模型拓扑结构非硬件原生的优化任务时，量子退火器产生的解决方案质量明显低于经典求解器[17]、[18]。这种差异凸显了次级嵌入问题在量子退火中的重要性。
此外，变量映射不仅至关重要，而且解决起来也非常复杂。挑战在于处理器的连接性有限，使得任何伊辛模型的映射都非平凡。实际上，硬件连接性越低，问题被平凡映射到硬件上的可能性就越小。例如，考虑一个伊辛模型，其中一个变量与其他16个变量相互作用，而硬件量子比特仅与15个量子比特相连。这种差异使得变量与量子比特之间的一对一映射变得困难，需要使用多个量子比特来表示一个变量。
在这种情况下，解决次级嵌入问题同时尽量减少嵌入所需的量子比特数量至关重要。使用更多量子比特会增加解的空间，而考虑到处理器中的噪声及其随机性，也会提高错误率。然而，为任何伊辛模型找到一个能在任何处理器上实现且量子比特数量最少的嵌入方案是一个NP难问题。
需要注意的是，只要量子退火处理器不具备全连接性，次级嵌入问题就将一直属于这一复杂类别。由于基于超导的处理器具有二维特性，构建全连接硬件极为困难[19]，因此这种情况在未来很可能持续存在。
由于次级嵌入问题的复杂性，必须采用启发式方法来解决它。文献中标准的次级嵌入算法是Minorminer[20]，该方法由Cai等人于2014年提出[20]，采用贪婪算法逐步构建嵌入，并在每一步最小化表示每个变量所需的量子比特总数。Minorminer可在D-Wave问题解决平台[12]上使用，作为将通用问题嵌入不同类型处理器的标准方法。除了Minorminer，D-Wave还提供了另一种专门用于嵌入完全连接问题的方法Clique Embedding（CE，Boothby等人[21]）。该算法能在多项式时间内为给定大小的完全连接实例生成嵌入。
除了D-Wave提供的方法外，还有多个独立研究团队提出了其他替代方案，包括：
•在[22]中，研究人员提出了Layout-Aware Embedding方法，该方法利用问题中变量的“位置信息”来指导映射过程。这些位置信息可以是问题的固有特征，也可以通过图论节点放置算法计算得出。通过这种方法获得初始嵌入后，再使用Minorminer算法进行优化。
•在[23]中，提出了两种用于寻找初始嵌入的算法，随后由Minorminer使用。第一种方法称为Clique-Based Minorminer，它利用D-Wave的CE方法对部分变量进行嵌入，而剩余变量未分配给量子比特。第二种方法称为Spring-Based Minorminer，类似于[22]中介绍的布局感知嵌入算法。它使用调整后的Fruchterman-Reingold弹簧算法来计算问题中变量和相互作用的布局，然后利用该布局信息将变量分配给量子比特并构建初始嵌入。
•在[24]中，研究人员提出了Probabilistic-Swap-Shift-Annealing方法，该方法受到模拟退火原理的启发。它首先生成一个初始嵌入，然后通过概率决策逐步改进嵌入质量。
•在[25]中，作者引入了虚拟硬件层的概念，该层将二分图（biclique graph）的预计算嵌入到硬件中，使用户只需计算二分图的嵌入而无需处理原始拓扑图。这种方法基于图论中的奇数循环分解概念，比直接将嵌入到硬件中更高效。
•在[26]中，使用整数规划工具重新表述并解决了次级嵌入问题。
尽管一些替代次级嵌入方法在特定问题实例上表现出与Minorminer相当甚至更优的性能（如各自原始研究所述），但Minorminer仍然是最广泛采用和标准化的方法。这主要是因为它是D-Wave Ocean SDK中的默认嵌入算法[4]。因此，我们的研究重点关注Minorminer，因为它代表了当前最先进和实际应用中最常用的方法。这一选择使我们能够在最能反映当前使用情况的条件下评估性能。
本研究的目标有两个：
1.揭示次级嵌入问题对量子退火最终性能的关键影响，即Minorminer生成的嵌入质量与量子退火器产生的最终解质量之间的关联。本文通过理论和实验结果深入探讨了这种影响。
2.认识到嵌入质量的重要性后，本文详细研究了Minorminer算法生成高质量嵌入的有效性。研究包括对Minorminer在Erd?s-Rényi图上的性能进行全面实验评估[27]，并与CE方法进行了比较，后者被视为最坏情况基准，因为假设完全连接实例的嵌入需要比低密度实例更多的量子比特。
本文的其余部分组织如下：下一节提供背景信息。第3节展示了研究的实验结果。首先，它评估了嵌入质量与问题最终解质量之间的关系。其次，对Minorminer的能力和性能进行了实验评估。第4节总结了主要结论和进一步的工作方向。
