用递归法优化量子电路综合

7用递归法优化排列的量子电路综合Cynthia Chen加州理工帕萨迪纳，美国cchen6@caltech.edu摘要布鲁诺·施密特EPFL瑞士洛桑bruno. schmitt@epfl.ch作者：Helena Zhang，AliJavadi-Abhar BishopIBMQuantumYorktownHeights，NY，美国{helena.zhang，ali.javadi}@ibm.com我们描述了一个家庭的递归方法的量子计算机上有限的量子比特连接的量子比特排列的综合有两个目标很重要：电路的大小和深度。在每种情况下，我们结合了一个可扩展的启发式与不可扩展的，但准确的合成。ACM参考格式：Cynthia Chen，Bruno Schmitt，Helena Zhang，Lev S.主教，阿里·贾瓦迪·阿巴 尔 .2022年。 使用 递归 优化排 列的 量子电 路综 合 在 第59 届ACM/IEEE设计自动化会议（DAC）（DAC '22）的会议记录中，2022年7月10日至14日，美国加利福尼亚州旧金山。ACM，美国纽约州纽约市，6页。https://doi.org/10.1145/3489517.35306541引言人们坚信量子计算机将能够解决经典计算机无法解决的某些问题[3，14]。通常情况下，研究人员描述量子算法在高层次的抽象：从纯粹的数学描述，以高层次的量子电路-一系列的运营商对量子比特的作用虽然这些高级电路假设所有对所有的连接，但实际上，由于噪声和互连挑战，大多数量子硬件中的量子位并没有完全连接。因此，不是每个量子位对都可以参与相同的门操作。 这些连接性约束称为耦合约束。找到从虚拟指令到允许的物理指令的映射的任务被称为量子电路映射。完成这项任务并不总是可能的，而不适用于额外的运营商的电路。这些额外的运算符通过排列它们在耦合图中的位置来实现对非相邻量子位的门的执行然而，它们的成本在许多应用的总成本中占这项工作的重点是家庭的电路置换量子比特的耦合图。此外，这些置换电路在量子计算基准测试中也很突出[6]。电路的尺寸和深度是评价综合过程质量的两个重要指标。 大小是指门的数量，并且是相关的，因为每个门都是有噪声的，并且许多门可能导致错误累积。深度是指电路中的时间步（或层）的数量 由于量子比特的相干性有限，它们只能在短时间内保留信息。因此，深层电路可以本作品采用知识共享署名国际4.0许可协议进行许可DAC© 2022版权归所有者/作者所有ACM ISBN978-1-4503-9142-9/22/07。https://doi.org/10.1145/3489517.3530654图1：我们的混合方法的高级视图，用于在任意拓扑结构上合成置换。它将一个图和所需的排列作为输入。这些被赋予ROWCOL [15]或LR-Synth，这取决于CNOT或SWAP是否被用作原语。两者都生成部分解，该部分解与通过基于SAT的技术合成的最优解相结合被噪音淹没请注意，在大小和深度优化之间通常存在折衷。用于置换的物理合成的直观过程是在量子位对之间执行SWAP操作。这个问题的大小优化版本称为令牌交换[16]，深度优化版本称为通过匹配路由[1]。 找到这些问题的最佳解决方案需要指数时间。虽然交换量子位是解决这个问题最常用的模型，因为它类似于图形算法，但我们可以通过利用基本的量子门（如CNOT）来改进。 由于置换是F 2上的一类特殊的线性函数，因此它们可以使用一系列XOR运算来计算（即，hocTs）。广泛地说，现有的用于合成置换电路的方法使用SWAP或hocT来优化尺寸或深度有些方法是精确的，但不可扩展，有些是针对某些拓扑结构定制的，有些是通用的算法。在表1和表2中，我们总结了先前的文献，按时间顺序排列，并根据它们是否针对尺寸或深度进行了优化。1.1我们的贡献在这项工作中，我们利用递归算法的综合排列。它们有两个关键优势：首先，它们减少了每个阶段的问题，使高质量的解决方案更容易找到，并且可以与内部优化方法结合使用。DACCynthia Chen，Bruno Schmitt，Helena Zhang，Lev S.Ali Javadi-Abhar Bishop8，描述原始操作拓扑帕特尔分组高斯消去法CNOT完全连接大小布龙兹2原木基辛格GheorghiuSteiner树的高斯消去法CNOT任何中文（ 简体）吴递归消去法CNOT任何2 2施密特可容许启发式A* 搜索交换任何最佳（小尺寸）我们SAT公式CNOT任何最佳（小尺寸）表1：尺寸优化方法的总结。边界是根据该方法所基于的操作来确定的。1个SWAP =3个hocT。描述原始操作拓扑深度界限阿隆图匹配交换树，carbohydrod。，等3张履带式隔板和火柴。交换树3+（log ）2[9]第九届全国政协委员奇偶换位排序（+手动对于特定的排列）CNOT线吴使用1002个锚钉CNOT2D网格（ log施密特SAT公式交换任何最佳（小尺寸）德·布鲁吉埃分而治CNOT完全连接4+8 log2（）322巴帕特分而治逆转任何（我们SAT公式CNOT任何最佳（小尺寸）我们分而治交换任何2μ m+2 logμ m表2：深度优化方法的总结边界是该方法所基于的操作方面的。 1 SWAP = 3 hocT。递归的阶段（图1）。其次，对于深度优化，重要的是尽可能并行化电路，递归方法可以在每个阶段并行化。我们的方法可扩展到数千个量子位，适用于任何量子位连接拓扑，并产生比最先进的方法更好的结果。首先，我们提出了一个SAT编码的问题，它可以找到电路的最佳尺寸或深度使用hocTs。该技术优于先前基于SWAP的最佳求解器[12]，并且可以用于合成任何线性函数，而不仅仅是排列。配备最优解算器（以下简称CNOT-size-optimal、hocT-depth-optimal、SWAP-size-optimal、SWAP-depth-optimal），我们在递归算法中使用它们，并扩展到更大的问题实例。在尺寸上，我们依靠的是一种改良版的Wu et al.[15]，它优于其他面向大小的算法，并适合递归。没有这样的算法存在的深度，所以我们提出LR合成器，一种新的深度优化一般图的分治启发式。ROWCOL是一种递归算法，通过每次从连接图中删除一个非切割顶点/量子位来减少问题我们观察到顶点消除的顺序很重要，并为此进行了优化将ROWCOL与CNOT- size-optimal结合用于递归的内部阶段，算法，这显着优于以前的工作。我们的第二个递归算法LR-Synth是一种新颖的算法，它在每一步中将量子位路由到拓扑的正确一半，然后在拓扑的左右子图上递归。由于我们总是可以将拓扑分为两部分，因此LR-Synth的优点是它可以应用于任何拓扑连接，从而弥补了当前深度优化方法的局限性。我们[12]解算器，用于解算最佳SWAP深度。 我们还将LR-Synth与针对特定拓扑（路径、树和格）存在的最先进的算法进行了比较。总的来说，我们发现LR-Synth实现了接近最佳的电路深度，同时比精确求解器更具可扩展性，适用于任何拓扑结构。我们强调的方法的一般性，因为许多现实的量子体系结构不使用规则的拓扑结构。我们注意到，我们填补了先前工作中的两个空白。首先，虽然存在基于SWAP的尺寸最优和深度最优合成的精确求解器[12]（并且在软件包Tweedledum [11]中可用），但是没有已知的hocT最优合成器由于每个SWAP相当于三个hocT，因此在综合中直接使用hocT可以产生更好的电路。其次，据我们所知，在一般拓扑结构上没有可扩展的深度最小化算法（最近有一个例外[2]，它假设存在快速反转操作，这在某些架构上可能不可用）。最后，我们用我们的精确算法来反驳一个15岁的猜想Kendy等人。 [9]用hocTs来合成反转至少和路径上任何排列一样需要深度密集。2基于SAT的CNOT优化我们制定的问题，找到一个最佳的深度电路的线性矩阵表示可逆函数的布尔可满足性问题的实例在我们的编码中，我们使用两种变量。矩阵变量，矩阵变量，表示是否一个矩阵项（n，n）在深度为0或1LR-Synth与Schmitt→和CNOT门变量，，这表明量子位和量子位之间的CNOT放在深处 。例如，3量子位线性函数合成用递归法优化排列的量子电路综合DAC9×1、2、3、4、5、1，02002年，0二、二100，0⊕���⊕���二、二∑∑+（）下一页•（）下一页·++−���−→一，一1，0一，一������二，一���������0→2二、零������0、1个二，一0，2⊕������一、二将被这样编码，其中3× 3布尔矩阵表示3比特上的线性函数，并且CNOT应用通过对两行进行XOR来变换矩阵������������������������00，00，10，200，00，10，2 00我们的编码使用四种不同类型的子句来约束问题的解对应于一个有效的线性可逆电路：C1. 不包含目标变换的每个深度必须至少有一个CNOT。图2：8Q路径{（���，）∈→→≥1。由hocT-depth-optimal合成。3尺寸优化：Rowcol-HybridC2. 在具有至少一个CNOT的每个深度处，每个量子位只能涉及一个CNOT。3.1算法描述���{���∈→→=1。我们提出并实现了一种混合CNOT电路综合算法，该算法结合了对Wu的ROWCOL算法[ 15 ]的修改其中是相邻的量子位的集合 。C3. 如果在深度上 ，变量a为真，那么 深度为1的第-行 的所有元素必须与前一深度的 第-行的对应元素进行异或 。方法（图1）。在[15]中，非切割顶点被迭代地从图中删除尽管没有讨论选择删除非切割顶点的顺序 我们发现移除顺序对电路大小和深度有重要影响（图3）。 我们用吴的算法？.��� +1= ���⊕ ���Σ可能的非切割顶点顺序以减小电路尺寸。对于每个-→，，，突变，选择最优排序，定义为导致最小CNOT电路大小的排序，深度作为平局决胜局。C4. 如果在深度 和1第 n行具有不同的值，则CNOT变量之一那就一定是真的���中国+1中国���=∑1个，，���∈→SAT求解器只回答给定公式是可满足的还是不可满足的。因此，我们需要将我们的优化目标转化为对SAT求解器的一系列查询在这种情况下，每个查询我们的实现增量地解决了这个问题：首先，我们构建一个公式，使用上述约束对具有指定深度的解决方案进行编码;然后，如果公式不可满足，则通过添加新的变量和约束来增加深度。我们不断增加深度，直到我们找到一个可满足的公式来解码并构建一个线性可逆电路。我们可以使用稍微不同的编码来找到具有最佳大小的可逆CNOT电路 在这种情况下，唯一的区别在于第一种类型的约束：我们不要求深度至少有一个CNOT，而是将数量限制为一个。正如我们将要展示的，这些基于SAT的解决方案可以应用于可扩展的物流，以提高其质量，但是，它们本身也很例如，我们研究了路径上排列的hocT深度最优解，这是Kobel等人的重点的论文[9]。他们强调，逆转至少同样困难，与任何其他排列一样，并且反转可以用深度2×2hocTs合成然而，通过求解所有8量子比特排列的实例，我们发现了一个需要深度为2π+3=19的特定排列，如图2所示，从而反驳了这个猜想。图3：顶点移除顺序对ROWCOL针对8Q路径合成的平均电路大小的影响。由于ROWCOL算法在每次迭代中将问题大小减少一个量子位，因此它适合与精确求解器杂交。 因此，当图只剩下四个量子位时（根据经验选择阈值），我们提前终止启发式，然后在简化图上调用我们的hocT大小最佳求解器以完成电路的合成。（注意，SWAP-size-optimal不是一个选项，因为子问题可能不是排列）。我们将这两种方法得到的电路结合起来，得到最终的结果。3.2结果我们比较我们的方法，以前的三个hocT为基础的方法：“ [8]，“Linear-TF-Synth”by Gheorghiu et al. [7]和Wu等人的“ [15]，在路 径 拓 扑 上 的 所 有 8 量 子位 排列上， 如图 4 所 示。 我们的ROWCOL-Hybrid算法与最佳顶点顺序实现了一个较小的CNOT计数比大小最佳的SWAP为基础的方法为88.8%的所有排列。与此同时，基辛格等人。 [8]，Wu et al. [15]和Gheorghiu et al.[7]第七话（7、6、5、2、3、4、0、1）·公司简介·公司简介DACCynthia Chen，Bruno Schmitt，Helena Zhang，Lev S.Ali Javadi-Abhar Bishop10（）下一页（）下一页∈（）下一页（）下一页∈（）下一页∈（）（）下一页∈（）∈（（）（））（）（）∈[]（）（）≤（）（）（）电路比最佳SWAP为基础的方法分别为12.5%，54.8%和6.6%的所有排列。我们发现这种基于hocT的方法比使用SWAP有了惊人的改进，SWAP看起来很自然地适合排列。虽然我们的方法主要是优化电路尺寸，也有一个改进的电路深度COM，其他三种算法。图4：hocT大小优化方法如何改进SWAP大小优化方法的比较（路径8上的排列）。我们的混合与最优排序方法实现了较小的CNOT计数为88.8%的所有排列。4深度优化：LR-SYNTH由于量子比特相干时间较低，电路深度通常是近期量子实验中最受限制的因素。 现有的深度优化合成方法按指数缩放[12]，假设完全连接[4]，限制于某些拓扑[1，9，17]，或假设非标准的原始操作[2]。 我们提出了一个多项式时间的分治算法，LR合成器，用于在任何有限连接拓扑上合成置换，优化SWAP的深度。我们的算法也可能是独立的兴趣一般网络路由。4.1算法描述给定一个置换图和一个目标图，目标是通过一系列SWAP转换到，尽可能多地并行化SWAP。高级思想如下（见图5）：我们将两个连通的子图划分为大小尽可能接近的子图，然后使用最大匹配将量子位移动到正确的一半。一旦所有的量子位都在正确的一半上，我们就递归地调用每一半上的算法由于左半部分和右半部分是不相交的，因此它们的电路在芯片上并行化完整的算法在算法1中给出，其中， ， 表示顶点之间的最短距离，并且 。第一步是将图划分为两个连通的子图，������������������������������尽可能平衡（步骤1）。 这是平衡连通2-划分问题是NP难的[5]，所以我们使用启发式来执行划分。我们使用一个简单的启发式算法，从每个节点开始执行深度优先搜索，直到遍历了图的一半，每次删除访问过的节点，将其放入搜索框中，同时保留搜索框���������，即图中不���������联系紧密我们发现，这种启发式发现足够的分裂感兴趣的拓扑结构 为了最大化跨分区的并行路由，如果可能的话，我们选择通过移除顶点不相交的边���而产生的分区（������������������������������������假设所有边都在其中������，但不在其中���������������或���������不在其中������），因为如果两个或更多个边共享一个顶点，则该顶点将成为跨分区路由顶点的瓶颈。在没有这样的分区存在的情况下，我们让边缘，形成一个最大的匹配。������������������������������������由于尝试每个分区对于较大的拓扑是不可行的，因此我们采样到100个分区。接下来，我们为每个需要移动到另一半的顶点指定一条路径，该路径由其中一条删除的边指定（步骤8）。有许多可能的方法来解决���������������������������这个问题。 我们的启发式算法���������������������������������通过选择������最小化������������=max{ (���������,���,���),���(��������� ℎ ,���, ���)}+���(���,���)/2,������其中，是最接近（，���）���������������������������的中的未赋值顶点���，，是赋值给，的节点数。���������������������,���,���and������������ℎ������,���,��� are the number ofswaps needed to move��� and分别与去除的边缘连接。 由于这可以并行执行，因此我们采用最大距离。我们添加了术语“路径 ”，因为“路径”和“路径”不能被路由到另一边，直到已经分配给路径“路径”的量子位被路由，所以“路径”，“路径”会惩罚通过一条路径移动太多量子位在分配路径之后，我们重新分配并添加交换，直到所有量子位都通过其分配的路径路由到拓扑的正确一侧（步骤11）。设���为在给定迭代中要交换的潜在边的集合。在每一次迭代中，我们通过将权重分配为1来优先添加交换。3如果交换将顶点移动���到其最终目的地，并且从���到的终端节点���的路径上的所有顶点都已经正确定位，因为进行交换有效地减小了我们使用的拓扑的大小（步骤12）。为了解释步骤13 - 25，我们考虑，Wyndham，������������������������������Wyndham���，其中，穿过移除的边R1，R2布线。对于任何顶点，因此���������������，我们希望在两个客户之间增加一个潜在的互换，和当，，> ，，时 ，（步骤16），因为这将带来���更接近的���������是������，如果，������������������������������如果，������������������������������������， 以及，，， 更接近被移除的边缘在目标图中，这意味着它应该在是路由的，所以我们在这个迭代中不添加（步骤17）。如果在给定迭代中不存在可能的SWAP，则步骤18通过交换 并且 如果存在邻居，则在下一迭代中修复该问题���不位于“”������������中的“”，并且“”比"“更接近”“，因为在随后的迭代中，交换”“和”“将使”“更接近其目标位置。���������������������������������如果���������如果交换使���和���更接近它们各自的路径（步骤19）。如果���已经在正确的一侧���������，那么我们添加������，���因为这将使���更接近其目的地，而不会移动���到错误的一侧（步骤22）。最后，我们交换���到右侧if���������������������������������;否则，在将来的迭代中需要额外的交换来移���回到���������右侧������。 我们优先考虑将顶点带到正确一侧的交换，因为这将允许更多的顶点通过相同的路径路由，所以我们将这些交换的权重定为1。2（步骤23）。在步骤13- 25之后，我们找到一个maxMatching来最小化深度（步骤26）。 在步骤28中，如果 是路径拓扑或环形拓扑，则对于每个边用递归法优化排列的量子电路综合DAC11（）下一页（）下一页∈∃������ 如果和不是在������������������������������������������������������������它们的顺序在中翻转 ，如果添加边仍然导致匹配，则将，添加到���������������������������������这增加了交换，否则将在算法中稍后发生，并利用早期匹配来减少深度。一旦������������������������������清空了顶点集和顶点集，所有顶点都位于拓扑的正确一半在对分区进行采样后，我们选择在最少迭代次数（ 最 低 深 度 ） 中 清 空 分 区 ��������������������������� 的 分 区 ， 并 使 用������������������������������的������状态为平局决胜（步骤32）。最后，我们递归地调用算法on���������������和���������numb������（步骤33，34）。 由于���������������和���������css������包含不相交的顶点，因此这两个调用是并行的。图5：8Q环形拓扑上的算法步骤。在步骤1和2中，有两种可能的路径将量子位从一侧移动到另一侧（黄色和蓝色边缘）。量子比特必须被路由到另一侧的路径具有与它们被分配的路径相同的颜色，并且算法在步骤3和4中递归，直到实现目标图。4.2结果我们通过比较LR-Synth与Tweedledum的SWAP深度最优SAT求解器[ 11，12 ]来对我们的算法进行基准 由于SAT问题的NP完全性质，即使在相对较小的量子比特数下，求解器也不会快速终止某些排列，尽管具体数量取决于拓扑结构。为了节省计算时间和资源，我们运行SAT求解器，直到在典型的个人计算机上平均电路综合时间超过10虽然LR合成器可以应用于任何有限的连接拓扑结构，我们执行我们的基准路径，树，环和网格，常见的当前物理设备。对于线，树和网格拓扑结构，现有的深度优化算法，我们也比较LR合成器。对于环，LR-Synth有许多可能的划分，所以我们算法1：LR-合成数据：（i）置换图样本数，（ii）目标图样本数，（iii）样本S的分割数结果：全部门办法清单，1leftGs，rightGs，removedEdges← partitionGraph;2Swaps← [];3 对于分割i = 1到S，4G←复制.copy; leftG← leftGs[i]; rightG←rightGs[i];removedEdges ← removedEdges[i];⑤左、右 ←���对应的左、右图;���6moveToLeft};;���7moveToRight};���8vertexToPaths ←assignPath;9GL← leftG removedEdges; GR← rightG removedEdges;10lockL← False; lockR← False;11whilemoveToRight+moveToLeft不存在12E ={（u，v，1.3）：（u，v）∈ G s.t. 交换u和v使得所有G的从G到G的端点的顶点在正确的位置};13，对于（u，v）∈ G s. t. u ∈ moveToRight + moveToLeft14（l，r）←vertexToPaths[u];15（lT，rT）←在λ中的对应边;16如果u∈moveToRight且D（GL，u，r）>D（GL，v，r），则17若v∈moveToRight且vertexToPath[v]=（l，r）且D（���k，u，rT）≤D（���k，v，rT）则继续;18，如果锁定L，moveToRight和vertexToPath[v]n（l，r）������和s. t的近邻���������������������������������且D（GL，u，r）>D（GL，b，r）然后E.add（u，v，1）; lockL← False;19如果v∈moveToRight和vertexToPath[v] <$（l，r）然后20（a，b）←vertexToPath[v];21如果D（GL，v，b）>D（GL，u，b）则E.add（u，v，1）;22else ifu=lthenE.add（u，v，1）;23else if（u，v）=（l，r）and v inmoveToLeft andvertexToPath[v]=（l，r）thenE.add（u，v，1.2）;24如果u∈moveToLeft且D（GR，u，l）>D（GR，v，l）则执行与步骤16-23类似的逻辑;月25日结束26maxMatching ← E的最大权重匹配如果maxMatching =0，则lockL← True; lockR← True;28如果G是路径或环，则addToMatching;29对于（u，v）∈maxMatching，将u和v交换到n中;30更新moveToLeft和moveToRight;31日结束32掉期←从最佳分割掉期33如果size（leftG）> 1，则Swaps += LR-Synth（leftG，left左合成器）;34如果size（rightG）> 1，则Swaps += LR-Synth（rightG，right_synth）;35端部36 回报掉期比较随机采样单个分区与选择最佳分区的性能。我们还将LR-Synth与SWAP深度优化求解器混合，类似于ROWCOL-Hybrid的过程。4.2.1路径 我们通过从4Q到100Q的100个随机排列采样，将LR-用递归法优化排列的量子电路综合DAC12Synth与Kendall的奇偶转置排序算法和SWAP深度优化进行比较（图6a）。我们用舒特的DACCynthia Chen，Bruno Schmitt，Helena Zhang，Lev S.Ali Javadi-Abhar Bishop13+（）下一页图6：使用LR-Synth（混合、单个和所有分区）、SWAP深度优化和定制算法（如果存在）合成的置换的四种拓扑的深度比较Kendall算法的实现KALTH和LR-Synth实现了相同大小的电路和相似的深度电路，其平均大小优于SWAP-Depth-optimal，平均深度略差于SWAP-Depth-optimal。SWAP-Depth-optimal的平均电路合成时间在84Q时超过10秒。4.2.2树 我们比较LR-合成器，张的树算法和SWAP-Depth-optimal，通过对每个树大小从4Q到100Q的10个随机树进行采样。我们使用SchouteSWAP-depth-optimal的平均电路合成时间在20 Q时超过10秒。LR-Synth在深度方面的平均表现略好于Zhang。4.2.3戒指 我们比较了LR合成器，采样单个和所有parti- tions，SWAP深度最优，平均从4 Q到100 Q的100个随机排列的结果。LR-Synth对所有分区进行采样的平均电路合成时间在44Q时超过10秒，而SWAP-depth-optimal为28 Q。采样单个分区的平均电路深度和大小与所有分区的平均电路深度和大小相当，而运行时间明显更好。4.2.4网格 由于网格具有明确定义的结构，通过在图的中间进行切割，��� 方向我们对LR-Synth与SWAP-Depth-optimal和Alon的笛卡尔算法进行了基准测试，网格大小为（2，2）到（10，10）。对于每个网格大小，我们采样100个随机排列。与其他拓扑结构相比，网格上的排列产生更小的平均尺寸和深度电路。我们观察到LR-Synth和SWAP-Depth-optimal的这种行为，这是一个直观的结果，因为有更多的路径可以并行化来路由量子位我们还注意到，该混合算法在这种拓扑结构上看到了显着的5结论和未决问题我们提出了两种在有限连接量子计算机上进行综合的算法。 使用修改后的ROWCOL算法混合与我们的最佳尺寸求解器的hocTs，我们表明，使用hocTs合成的排列可以显着超过形式的最佳电路尺寸可实现的SWAP为基础的方法。因此，一个重要的开放问题是，是否有一个深度优化算法的一般拓扑结构使用hocTs和多大的改进，它可以产生。我们提出LR合成器作为一个可扩展的深度优化算法适用于任何拓扑结构。它实现了与针对路径、树和网格量身定制的最先进算法相似的电路深度，并且比最优解算器更好地扩展。LR-Synth可以通过更好的算法来划分图形并选择每个量子位的路由路径来改进多少？最后，路径上置换的最坏情况深度仍然是一个悬而未决的问题。我们已经给出了一个反例来证明反转是最难置换的猜想。最坏情况下的CNOT深度是多少我们推测这是2 ×1，而不是已知上限为3μ m。引用[1] N. Alon，F.R. K. Chung，R.L. 格雷姆一九九三年通过匹配在图上路由排列。在93年的斯托克[2] 放大图片作者：Aniruddha Bapat，Andrew M.Childs，Alexey V.戈尔什科夫，塞缪尔·金，埃德-斯高特和赫里希·夏斯特里2021年量子路由与快速逆转。量子5（8月）2021），533.https://doi.org/10.22331/q-2021-08-31-533[3] 伊森·伯恩斯坦和乌迈什·瓦齐拉尼一九九七年。量子复杂性理论 SIAMJournalon computing 26，5（1997），1411-1473.[4] Althée Goubault de Brugière ， Marc Baboulin ， Benošt Valiron ， SimonMartiel，and Cyril Allouche.2021年减少线性可逆量子电路的深度IEEETransactions on Quantum Engineering2（2021），1-22。http：//doi.org/10.1109/TQE.2021.3091648[5] 扬卡·克莱比科娃1996.图的最大平衡连通划分问题的告知。过程Lett. 60，5（1996），225-230. http：//doi.org/10.1016/S0020-0190(96)00175-5[6] Andrew W.Cross ， Lev S. 放 大 图 片 作 者 ： Sarah Sheldon ， PaulD.Nation，and Jay M.甘贝塔2019年。使用随机化模型电路验证量子计算机物理评论A100，3（2019年9月）。https://doi.org/10.1103/physreva.100.032328[7] Vlad Gheorghiu ， Sarah Meng Li ， Michele Mosca ， and PriyankaMukhopadhyay.2021. 减少NISQ结构上Clifford+T电路的CNOT计数arXiv：2011.12191[quant-ph][8] Aleks Kissinger和Arianne Meijer van de Griend。2019年。拓扑约束量子存储器的CNOT电路提取arXiv：1904.00633[quant-ph][9] 塞缪尔·凯布尔，大卫·莫尔顿，和劳伦·史密斯林。2007年远距离计算芝加哥理论计算机科学杂志13（02 2007）。[10] Ketan N Patel，Igor L Markov，and John P Hayes.2008年的优化综合线性可逆电路 量子信息Comput. 8，3（2008），282-294.[11] 布鲁诺·施密特。2021. 二百五https://github.com/boschmitt/tweedledum上下载。[12] Bruno Schmitt，Mathias Soeken，and Giovanni De Micheli.2020年。用于 令 牌 交 换 的 符 号 算 法 2020 年 IEEE 第 50 届 多 值 逻 辑 国 际 研 讨 会（ISMVL）。28比33[13] 艾迪·舒特2019. 弧https://gitlab.umiacs.umd.edu/amchilds/arct上下载。[14] P.W. Shor 一九九四年量子计算的演算法：离散型演算法与因子分解。第35届计算机科学基础年会论文集。124-134.https://doi.org/10.1109/SFCS.1994.365700[15] Bujiao Wu ， Xiaoyu He ， Shuai Yang ， Lifu Shou ， Guojing Tian ， JialinZhang，andXiaoming Sun.2019年。拓扑超导处理器上CNOT电路的优化arXiv：1910.14478[quant-ph][16] Katsuhisa Yamanaka，Erik D Demaine，Takehiro Ito，Jun Kawahara，MasashiKiyomi，Yoshio Okamoto，Toshiki Saitoh，Akira Suzuki，Kei Uchizawa，and TakeakiUno. 2015年。交换图表上的标记标记理论计算机科学586（2015），81[17] 张露欣一九九七年。树上匹配路由的最优界第八届ACM-SIAM离散算法年会论文集。