可逆电路的误差检测特性

ermany10Array 14 (2022) 1001650开放获取文章（http://creativecommons.org/licenses/by/4.0/）。0ScienceDirect提供的内容列表0Array0期刊主页：www.elsevier.com/locate/array0可逆电路的误差检测特性0Lukas Burgholzer a , � , Robert Wille b , c , Richard Kueng a0c  Software Competence Center Hagenberg GmbH (SCCH), 奥地利0文章信息0关键词：新兴技术可逆逻辑 误差检测 仿真量子计算0摘要0在这项工作中，我们考虑通过仿真进行可逆电路架构的误差检测。我们严格证明了可逆性将这种简单的误差检测协议的性能提高到了相当大的程度。一个随机生成的输入被保证能够揭示一个可逆错误，其概率仅取决于错误的大小，而不取决于电路本身的大小。实证研究证实了这种行为通常也适用于多个错误。总之，可逆电路提供了减少掩盖效应的特性——这是与不可逆电路架构形成鲜明对比的一个理想特性。01. 引言0错误检测是电气工程和计算机科学中的一个基本问题。给定一个具有�个输入和�个输出的电路� 1（黄金规范），任务是决定给定的电路实现�2（待验证设计）是否在逻辑层面上描述了相同的功能。存在许多方法来解决这个重要且具有挑战性的问题。在这项工作中，我们专注于只需要对两个电路进行仿真运行的误差检测协议——而不是明确利用关于两个电路结构的知识的形式验证技术[1-6]。这是一个严重的限制，但原则上仅使用仿真就足以解决这个任务。如果两个电路是等价的，它们具有相同的输入-输出行为。反之，假设它们在功能上是不同的。那么，至少存在一个输入字符串，使得这两个电路产生不同的输出。用公式表示：0� ��  ∈ {0 ,  1} �，使得� 1 ( �� )  ≠  � 2 ( �� ) . (1)0这样的输入成功地检测到了� 1 与�2之间的差异，并作为电路等价性的反例。然而，问题在于如何找到反例（1）。如果我们只允许对两个电路进行仿真，即将它们视为黑匣子，那么我们就无法得到如何选择有希望的输入字符串的可行建议，我们可能会随机生成输入：��  �  Unif ( {0,  1} � )，即，我们为每个输入值翻转一个无偏的硬币（��  = ( � � ,  …  , � 1 )，其中…  , � 1  �  � 且Pr [ �  = 0] = Pr[ �  = 1] =1∕2）。随后，我们用这个输入对两个电路进行仿真并检查0� 通讯作者。电子邮件地址：lukas.burgholzer@jku.at（L. Burgholzer），robert.wille@tum.de（R. Wille），richard.kueng@jku.at（R.Kueng）。1 https://www.cda.cit.tum.de/research/quantum/。0它们是否产生相同的输出：� 1 ( �� ) ? =  � 2 ( ��)。如果输出不同，我们已经找到了一个反例。这两个电路不能是等价的。但如果输出相同，则测试是无法确定的。在这种情况下，我们必须用新的（随机生成的）输入重复这个过程，直到我们找到一个反例（非等价）或者耗尽了所有  2 �个可能的输入（等价）。遗憾的是，后者可能是一个非常真实的可能性。这两个电路� 1 与� 2可能仅在一个输入上有所不同，而通过（随机）机会迅速找到这个输入的可能性极小。更糟糕的是，经典电路可以非常有效地掩盖甚至‘‘小’’错误。对于� =8，这在图1中有所体现。由逻辑AND门级联实现的功能� =  � �  �  …  �  � 1（理想电路�1）受到了第二层中的一个位翻转错误（错误的实现�2）的影响。很容易检查出在所有2 8 =256个输入字符串中只有4个能够检测到这个差异。掩盖是使用仿真技术进行误差检测的一个严重问题。不需要恶意意图就可以愚弄随机生成的输入。电路可能自己就能做到。不用说，这个问题几十年来一直为人所熟知。基于随机输入（单独）的误差检测通常不如其他更复杂的技术。今天的最新技术是由基于约束的刺激生成技术[7-11]、模糊测试[12]等所主导。但积极的一面是，使用随机选择的输入进行误差检测是基于最小的假设，即能够将两个电路作为黑匣子进行仿真。此外，这是直观的，个别仿真运行易于执行且速度快。0https://doi.org/10.1016/j.array.2022.1001652021年7月31日收到；2022年2月15日修订后收到；2022年4月1日接受Array 14 (2022) 1001652Theorem 1. Suppose that a general reversible circuit is affected by a singlereversible error of size 𝑘 and fix 𝛿 ∈ (0, 1) (confidence). Then, at most⌈log(1∕𝛿)2𝑘−1randomly selected inputs suffice to witness this error withprobability (at least) 1 − 𝛿.0L. Burgholzer等0图1. 在经典电路中的错误检测很困难：假设由一系列逻辑AND门实现的布尔函数 � = � 8 � … � � 1受到第二层中的单比特翻转错误（红色）的影响。只有256种可能的输入字符串中的4种可以检测到此错误。0图2.主要严格贡献的插图：使用均匀随机输入完全暴露给定可逆电路中的任何单个可逆错误。这两种情况完全等价（“无掩盖”）。在较低的情况下，正确区分的概率取决于错误的大小 � ，而不是总线的总数。02. 结果摘要：可逆电路中的错误检测0随机输入通常不是在经典电路中检测错误的可行策略。即使是单个“小”错误也可能极其难以检测（掩盖）。也许令人惊讶的是，如果考虑逻辑功能的可逆实现，这种黑暗的画面会明显变得明亮起来。顾名思义，可逆电路是可以通过运行电路的反向来撤销其操作的电路。更正式地说， � 位可逆电路实现对所有 2 �位字符串集合的置换。这特别意味着输入和输出位数必须相同（ � = �）。尽管存在这些限制，可逆电路是通用的，即， �位上的任何逻辑函数都可以由可逆电路实现[13]，并且有有效的映射技术可供使用[14-16]（尽管此实现可能需要严格多于 �位）。取反（NOT）、异或（CNOT）和Toffoli门（CCNOT）是简单可逆功能的例子。从逻辑门的角度看，CCNOT也是通用的。每个可逆电路都可以仅由Toffoli门构建[13]。0总之，可逆电路与经典（不可逆）电路具有很强的相似性，但也有一些显著的额外特征。其中最重要的是可逆性本身，这0与经典（不可逆）电路相比，可逆电路具有一些显著的额外特征。其中最重要的是可逆性本身，这意味着信息不能轻易泄漏。在这里，我们展示了这对于使用随机输入进行错误检测有深远的影响。更确切地说，0(i) 可逆电路永远无法掩盖单个可逆错误（严格的）0结果取决于其大小，即受影响的位数，而不是0(ii) 仅检测单个可逆错误的概率取决于其大小0（经验研究，请参见图3和第4节中的讨论）0(iii) 多个可逆错误通常更容易检测0前两个见解是数学陈述，仅涉及单个错误。它们很容易从可逆性和均匀随机输入字符串的基本属性中得出。有关详细信息，请参阅第3节，有关说明性漫画，请参阅图2。当结合使用时，它们暗示了使用随机输入检测单个错误的以下置信度界限。0对于 � = 1 - 电路内的任何单比特翻转错误（NOT）0-这个声明可以进一步改进（见定理2），并且实际上变得确定：已经可以保证单个（随机）输入能够确定地检测到这个错误。我们强调，这个声明是真实的，无论线的数量和电路的大小如何。在可逆电路内部，简直不可能隐藏一个单比特翻转。这种行为与不可逆电路结构截然不同。在那里，甚至可能需要顺序2�个随机输入才能检测到单个比特翻转错误，例如参见图1。0-这导致最佳情况（独立错误）和最坏情况（严重掩盖）行为的差异行为截然不同。为了更好地理解多个错误的典型行为，我们求助于数值模拟。这些模拟表明（接近）最佳情况行为：未能检测到�个可逆错误的概率在�中呈指数抑制，参见图3。有关其他模拟结果和详细信息，请参见第4节。0请注意，最近已经针对0-量子计算领域（与可逆电路有许多相似之处）已经提出了一个基于模拟的验证方案，该方案在[17]中得到了提出，并在[18]中得到了完善。类似的理论结果已在[19]中提出。03. 单个错误的严格理论03.1. 可逆电路和错误模型0我们将在具有�个输入位（和�0输出位）。高层次的数学抽象已经足以推导出强大的结论。一个�位可逆电路实现了所有2�位字符串的置换�∶{0，1}�→{0，1}�。反转电路，即将其向后运行，产生了唯一的撤销原始电路的置换��∶{0，1}�→{0，1}�：0� � ◦ �  =  � ◦ � � = id，其中id(��)=��对于所有��∈{0，1}�是0恒等置换（“什么也不做”）。这一定义特征足以推导出我们证明策略的三个基本性质。0电路�1，�2，�3∶{0，1}�→{0，1}�和一个�位字符串��∈{0，1}�。那么，0（i）输出等价性不受组合影响：0�1(��)=�2(��)�（�3◦�1）(��)=(�3◦�2)(��)0（ii）均匀分布的不变性：0（iii）非平凡作用：假设�1≠id。那么，至少有两个位0字符串，使得�1(��)≠��。0所有2�位字符串的置换。0（i0服务等价性：�=�′当且仅当�(�)=�(�′)对于任何可逆电路�。该断言可通过设置�=�1(��)，�′=�2(��)和�=�3来得出。30阵列14（2022）1001650L. Burgholzer等人。0图3.多个错误的典型累积效应（对数图）：随机注入可逆错误的数量�（�轴）与在具有4000个门的通用20位可逆电路中检测错误行为所需的平均随机输入数量（�轴）之间的关系。不同颜色表示增大大小�的最坏情况错误。实线跟踪理论最佳情况行为（独立错误，见下面的方程（5））。对于较小的�，该图突出显示了典型（菱形）和最佳情况（实线）行为之间的出色一致性。0图4。（单个）错误模型和兼容电路分解：理想可逆电路（蓝色）受到单个可逆错误（红色）的破坏。错误位置导致理想和损坏的电路分解成匹配的组成部分：�=�2◦�1（理想）和��=�2◦�◦�1（损坏）。0（ii0对每个2�位串的权重。排列位串不会影响权重，进而也不会影响均匀分布本身。0（iii）不变位串的数量（��∈{0，1}�∶�1（��）=��）为0等于底层排列的不动点的数量。2�个元素的非平凡排列最多可以有2�−2个不动点（换位）。□0以产生另一个（更大）电路：（�2◦�1）（��）=�2（�1（��））对于输入��∈0{0，1}�（“组合”）。反方向也是可能的（“分解”），而且可以说更有趣。电路图提供了一个已经建立的工具，可以精确地做到这一点。它们将一个可能复杂的电路分解成一系列更简单的构建块。我们在一个相当高的层次上使用电路分解来推理可逆电路中的单个可逆错误。假设一个�位可逆电路�受到可逆错误�的影响，产生一个功能上不同的电路��。然后，该错误的位置在电路中暗示着一个兼容的分解成三部分：0（i）�1∶{0，1}�→{0，1}�描述了原始功能直到错误位置之后（“未来”）。0（ii）�∶{0，1}�→{0，1}�捕捉错误作为附加电路0所有�位上的层（“现在”）0（iii）�2∶{0，1}�→{0，1}�描述了原始功能从错误位置之前（“过去”）。0错误位置之后（“未来”）。0总之，0�� = � 2 ◦ � ◦ � 1，而� = � 2 ◦ � 1，（2）0我们参考图4进行视觉说明。03.2.随机输入的无掩码0现在我们已经准备好提出和推导所有构建块0这项工作的主要概念结果。它基于单个随机输入���Unif（{0，1}�），解决了任意可逆电路中检测单个可逆错误的概率（2）。0命题1（无掩码）。固定�=�2◦�1（理想电路）和��=0� 2 ◦ � ◦ �1（单个，可逆错误）。然后，检测到这种差异的概率与错误�有关，而与实际电路无关。更确切地说，0Pr [  � � ( �� )  ≠  � ( �� ) ] = Pr [ � ( �� )  ≠  ��]，0其中概率是针对所有2�个可能的输入字符串的均匀分布。0证明。这个声明是可逆电路架构的两个基本特性的直接结果。应用引理1（i）去除�2的影响0Pr [  � � ( �� ) =  � ( �� ) ] = [ � 2 ◦ � ◦ � 1 ( �� ) =  � 2 ◦ � 1 ( �� ) ]0= Pr [ � ( �1(��)) =  �1(��)]，0请注意，根据引理1（ii），���Unif（{0，1}�）意味着�1（��）�Unif（{0，1}�）。□0尽管很容易证明，命题1指出了显著的差异0可逆电路和不可逆电路之间的差异。如图2所示，前者无法隐藏来自随机抽样输入的错误（“无掩码”）。0我们强调，对输入字符串进行均匀随机选择0至关重要的是要得出这样一个强有力的结论。仅仅可逆性就足以忽略电路  � 2的最后部分（在错误发生后）4Pr [𝐸(⃗𝑥)⃗𝑥 = Pr̃𝐸(𝑥𝑘, … , 𝑥1)(𝑥𝑘, … , 𝑥1)2𝑘 .□Pr̃𝑅(⃗𝑥𝑖) = 𝑅(⃗𝑥𝑖)exp −𝑁∕2𝑘−1Pr̃𝑅(⃗𝑥1) = 𝑅(⃗𝑥1) = Pr 𝐸(⃗𝑥1) = ⃗𝑥11 − 2−(𝑘−1).Pr[{ ̃𝑅(⃗𝑥𝑖) = 𝑅(⃗𝑥𝑖)}]=Pr̃𝑅(⃗𝑥𝑖) = 𝑅(⃗𝑥𝑖)0Array 14 (2022) 1001650L. Burgholzer 等0已经发生）。可逆电路总是将（不）相等的比特字符串映射到（不）相等的比特字符串。相比之下，电路  � 1 的第一部分（在错误发生前）可以影响具体的输入  ��  ∈{0 ,  1} � 。但如果  ��  被随机抽样，那么  � 1 ( �� )将是一个不同的，但仍然是随机的比特字符串。均匀分布在可逆变换下是特殊的。电路  � 1 可能影响每一个具体的输入，但它不会影响底层分布。03.3. 只有错误大小很重要0我们已经看到，均匀随机输入可以发现单个0在一般可逆电路中检测可逆错误。根据  Proposition 1，发现差异的概率仅取决于错误，而不取决于底层电路结构。0我们说一个错误  �  ∶ {0 ,  1} � →  {0 ,  1} �  如果它只0以非平凡的方式影响  �  位。剩下的  �  −  �  位根本没有受到影响。我们参考  图 2对这个总结参数进行直观说明。直观上，我们会期望‘‘大’’错误比‘‘小’’错误更容易被检测出来，并且线的数量  �起着积极的作用。然而，以下简单的陈述表明，在最坏情况下检测错误的概率随着错误大小  �  指数抑制，但与实际位数  �  无关。0引理 2  ( 只有错误大小很重要 ) .  假设  �  ∶ {0 ,  1} � →  {0 ,  1} �0是以非平凡的方式影响  �  位的可逆错误，而  ��  � Unif({0 ,  1} � )。然后，0Pr [ � ( �� )  ≠  �� ] ≥  2 −( �−1) .0证明。假设，没有失一般性，错误  �  只影响最不显著的  �  位，即，  � ( �� ) =  � ( …  , � 1 ) = ( � � ,  …  , � � +1 , � � , …  , � 1 ) ，其中  ( � � ,  …  , � 1 ) = �� ( � � �  是可逆的，它的0限制 � �  ∶ {0 ,  1} � →  {0 ,  1} � 到  �  个相关位必须也是可逆的。此外， � �  ≠  id，因为  �  是非平凡的。引理 1  (iii) 随后暗示着 ��  必须至少影响  �  位大小的 2个比特字符串。最后，我们利用了  ��  = ( � � ,  …  , � 1 ) �0Unif({0 ,  1} � )  意味着最不显著的  �  位也是均匀分布的： ( � � ,  …  ,� 1 ) � Unif({0 ,1} � ) 。因此，0这个概率上界实际上是尖锐的。最坏情况下的可逆错误检测的性能保证与（均匀）随机输入有关。0大小为  �  的错误恰好对它们所作用的  2 � 可能的  � -比特输入中的 2个进行排列。这种行为的具体示例是  NOT  ( �  = 1 ), CNOT  ( �  = 2 ),  CCNOT  ( � = 3 ) ，以及更一般地，对  �  位（一般  � ）进行  ( �  − 1) -重控制  NOT门的数值模拟如  图 3  所示，是基于在随机电路位置注入这种最坏情况错误。03.4. 检测单个可逆错误的一般置信上界0我们现在拥有建立严格的排列的所有必要成分-0可靠性错误检测的性能保证与（均匀）随机输入有关。以下陈述限制了可能需要的均匀随机输入的数量，以检测大小为  �  的单个可逆错误。0定理2. 固定  �  =  � 2 ◦ � 1  （理想电路），��  =  � 2 ◦ � ◦ � 1  （单一、可逆错误），并01 ≤ � ≤ �0定理1 是这一观察的简化结果：0图5. 多个错误的部分简化：使用均匀随机输入进行模拟只能部分暴露多个错误。第一个错误（ � 1）之前和最后一个错误（ � 3 ）之后的所有内容都可以安全地忽略，但中间部分（ � 2）确实很重要。不同的电路结构可能导致截然不同的错误检测概率。0定理2 的证明。对于  �  = 1  （一个随机输入），该断言很容易从  Proposition 1  和0设置  �  =  � log(1∕ � )2 � −1 � 提供了一个具体的重复次数，以确保我们以（至少）1−  � 的概率检测到差异。0通过使用各个输入位串  �� 1 ,  …  , �� �都是独立采样的假设，这个上界很容易扩展到一般的  �-情况。独立事件的联合概率因子化，我们得出：01 ≤ � ≤ �0� ∏0≤ ( 1− 2−( �0定理2 中提供的上界很简单，但不够精确（在0应用  1+ � <  exp( � ) 适用于所有  �  ∈  R  （指数函数的凸性）, 其中  �  = −2 −( �−1) 完成了论证。□0等式  1+ �  ≤  exp( � )从来没有达到过极限）。因此，它总是低估了实际的置信水平。这种差异在小错误尺寸  � 时最为显著。极端情况是单个  NOT  错误（ �  = 1 ）。对于 �  = 1，等式（3）中的上界变为（确切地）零。由于逆否命题，每个可能的输入位串都保证可以检测到隐藏在电路中的单比特翻转错误。0在前一节中，我们已经建立了强有力的理论支持0虽然我们可以安全地忽略第一个错误之前和最后一个错误之后的电路贡献，但中间的电路不能被忽略，参见  图5。错误和中间电路部分之间的关系决定了观察到整体错误的可能性。0对于多个错误来说，通常不再是一个选择。0可逆电路。为了获得指导性的直觉，我们首先将两种极端情况孤立出来并讨论。独立错误（最佳情况，参见0在本节中，我们分析了通用错误积累效应0L. Burgholzer 等人Array 14 (2022) 1001655L. Burgholzer et al.0图6. 两个错误的最佳情况：错误中的一个，比如  � 2 ，与相关的电路部分  � 2交换。重新排序使我们能够将这两个错误视为单个有效错误 � �  =  � 1 ◦ � 2。此外，  � 1 和  � 2影响不相交的位集合（独立性），� � 很好地分解为两个不相交的部分： Pr [  � � ( �� )  ≠  � ( �� ) ] = Pr [  � � ( �� )  ≠  ��] ≥ 1 − (1 − 2 −( � −1) ) 2（二次改进）。0第4.1节）和最大掩盖（最坏情况，参见第4.2节）的行为实际上是截然不同的。随后的数值研究表明，典型的错误累积效应通常紧随最佳情况的轨迹：多个错误通常比单个错误容易得多。04.1. 最佳情况行为：交换和独立错误0多个错误（�≥3）和不同大小将会很简单。图6为潜在的最佳情况行为提供了宝贵的指导。假设错误中的一个，比如�2，可以在不影响中央电路部分�2的情况下被引入：�2◦�2=�2◦�2。如果电路和错误以这种方式交换，我们就可以将两个错误分组到一个单一层中，并有效地将问题简化为我们已经了解的单一错误情况：0��=�3◦�2◦�2◦�1◦�1=(�3◦�2)◦(�2◦�1)◦�1。0唯一剩下的问题是：使用单个随机输入无法检测到累积错误�2◦�1的概率是多少？如果两个错误是独立的，即它们分别作用于�位的不同集合，那么这个失败概率是最小的。一个均匀随机输入��∈Unif({0，1}�)就可以确保失败概率因子分解为：0Pr[(�2◦�1)(��)=��]=0�=1 Pr[��(��)=��]≤（1−2−（�−1））2。0这个论证很容易扩展到多个错误（�≥3）。取补集可以确保0Pr[ ��(��)≠�(��)]=1−Pr[��◦�◦�1(��)=��]0≥1−（1−2−（�−1））�，（4）0只要所有�个错误与电路交换（第一个等式）并且分别作用于�位的不同子集（第二个不等式）。Rel.（4）突显了（最佳情况）错误检测的概率随着错误数量�的增加而显著增加。直观上，这是有道理的：更多的错误应该更容易检测到。这一观点对于需要检测�个大小为�的最佳情况错误所需的随机输入数量�具有重要意义。为了确定它们，将单次模拟运行视为有偏硬币投掷是很有启发性的：我们以概率�=Pr[��2(��)≠�2(��)]（‘‘正面’’）来检测差异，以概率1−�=Pr[��2(��)=�2(��)]（‘‘反面’）来未能检测到它。当试图检测差异时，我们输入新生随机输入，直到找到不匹配。这相当于投掷有偏硬币直到出现‘‘正面’’。达到这个目标所需的预期硬币投掷次数是1∕�（几何分布）。结合Rel.（4），这个类比使我们得出结论，我们期望需要0�（↓）期01−（1−2−（�−1））�（最佳情况）（5）0随机输入以检测�个交换和独立的大小为�的错误。这个界限是尖锐的。如果每个�个错误都是大小为�的最坏情况错误，例如一个（�−1）-重叠控制NOT门，那么它就等于这个界限。0图7.两个错误的最坏情况：两个位翻转错误（�=1）影响一个控制线的（�−1）-重叠控制NOT门。这些错误与相关电路部分�2不交换。恰恰相反：大小为�=1的两个错误产生了大小为�=（�−1）的有效错误��。更糟糕的是，这样一个（�−2）-重叠控制NOT错误极难检测到：Pr[ ��(��)≠�(��)]=Pr[ ��(��)≠��]=4∕2�（掩盖）。0我们用对Rel（5）的简化解释来结束本节。0对于较小的�（与2（�−1）相比），该声明与�（↓）期望≈2�−1∕�相当，这也可以在图3中观察到：0实线在�相对较小时（相对于2（�−1））与此估计相当，根据最佳情况的假设，检测�大小的�错误比检测相同大小的单个错误容易�倍。04.2. 最坏情况：反对易错误和屏蔽0我们预计最坏情况的错误积累应该发生在0错误和相关电路部分根本不对易（“反对易”）。如果是这种情况，检测错误的概率可能在比特总数上呈指数级下降。我们通过一个例子来说明这一点，该例子在图7中有所说明：�1和�2是位翻转错误（�=1），影响第一个比特，而�2∶{0，1}�→{0，1}�是一个（�−1）-倍控制非门。很容易检查到0�2◦�2◦�1 = ��◦�2，0其中��是一个（�−2）-倍控制非门，作用于除了第一个比特之外的所有比特（�=�−1）。这是几乎最大尺寸的单个最坏情况错误。命题1和引理2断言0Pr[  ��(��) ≠ �(��)] = Pr[  ��(��) ≠ ��] = 402�.0这种成功概率在比特总数上呈指数级下降，我们预计需要总共0�(↑)期望≥2（�−2）（最坏情况）（6）0随机输入以检测差异。对于更多的错误（�≥3）和/或更大的错误大小（�≥2），甚至可能发生更糟糕的错误积累效应。但是Rel.（6）几乎是最糟糕的情况。它与区分任何一对可逆电路的绝对最坏情况相差只有两倍，参见引理1（iii）。04.3. 实证研究0与之相比，多错误情况更加复杂，因为0错误（位置）和基础电路几何形状之间的相互作用开始变得重要。我们已经看到，这导致了最佳情况（对易错误，子节4.1）和最坏情况（反对易错误，子节4.2）之间明显不同的行为。具体的问题实例落入这些极端情况之间的广泛范围。在本节中，我们使用数值方法来描述典型行为。0我们研究可逆电路中大小为�的可逆错误的影响0具有�条线。对于给定的线数�，我们构造具有�≈�（�2）任意多控制非0门。在注入大小为�的错误时，我们总是考虑（�-1）-倍控制非门，这代表了最坏情况的行为。60数组14（2022）1001650L. Burgholzer等人0图8.理论结果的确认：在具有�=20（左图）和�=40（右图）条线的电路中，检测大小为�的单个可逆错误所需的模拟（�-轴）的散点图。不同的颜色表示�∈{1，2，3，4，5}的不同值。这在实验上证实了模拟的分布不取决于线数，而所需模拟的数量随着错误大小的增加呈指数级增长。0图9. 最坏情况和平均情况误差的比较：执行模拟（�-轴）与累积分布函数（cdf）以检测� = 1，2，4，6可逆错误，大小为� =5（�-轴）。红色曲线对应于注入最坏情况错误，而蓝色曲线勾画了相同大小的随机生成错误的cdf。这表明，平均情况错误需要的模拟远少于最坏情况。0如第3.3节所讨论的那样。毫无损失，我们假设这些错误在几何上是局部的，即它们只影响相邻的线路。所有实验都以不同的随机种子重复了10,000次，以确保充分的统计均匀性。首先，我们确认了第3节中开发的理论的有趣方面。为此，我们考虑注入单个大小为�的错误，并计算检测此错误所需的模拟次数。结果如图8所示。与经典直觉相反，检测到大小为�的单个可逆错误的概率(1)完全独立于所考虑的电路，(2)在错误大小�上呈指数衰减，即，0错误越小，其影响越大。这与定理2完全一致。平均而言，所需的模拟确切地遵循了预测的2�−1轨迹，没有明显的变化。此外，当模拟电路�=�2◦�1和��=�2◦�◦�1时，结果的分布与仅模拟错误�本身时相同。下一组数值实验将我们引入更有趣的领域。即，多错误情况。我们已经在介绍中预告了结果，并在图3中总结了它们。平均输入数量突出显示了观察到的行为与第4.1节讨论的最佳情况的出色一致性。7[17]0数组14（2022）1001650L. Burgholzer等人0对于更多错误的最佳情况与此最佳情况的偏差可以通过错误的累积效应来解释，这些错误不是独立作用的(见第4.2节)。0最后但并非最不重要的是，我们强调到目前为止的理论0和经验结果一直依赖于最坏情况的假设:每个注入的大小为�的错误是一个(�−1)倍的控制非门。在最后一系列评估中，我们分析了在选择随机错误时进行一定数量的模拟后的成功概率。更确切地说，每个大小为�的错误是一个随机选择的门序列，并附加约束，即没有任何�个相关线路保持不受影响(这样的情况最多会产生(�−1)的错误)。我们期望这种错误模型更准确地捕捉典型行为。结果如图9所示，并突出显示了随机(蓝色)和最坏情况(红色)错误之间的显著差异。这一点一点也不令人惊讶。大小为�的随机错误倾向于分解为几个独立的贡献，并随机输入检测它们的概率相应地分解，见Sub. 4.1。这种分解导致在(非常)少的模拟运行中增加了错误检测概率。05. 结论0在这项工作中，我们展示了可逆电路的影响0对电路中检测错误的概率的范式的影响。我们严格的分析表明，与经典/不可逆电路相反，可逆电路永远无法掩盖单个错误，而仅依赖于错误的大小，而与周围电路无关。经验评估表明，在多个错误的情况下，检测概率非常接近理论最佳情况。最后，我们观察到，如果放弃最坏情况错误的假设，检测这些错误的概率会进一步增加。0CRediT作者贡献声明0Lukas Burgholzer:  调查，软件，验证，撰写 -0原始草案，可视化。 Robert Wille:概念化，融资获取，撰写-审阅和编辑，监督。 Richard Kueng:方法论，正式分析，撰写-原始草案，监督，项目管理。0竞争利益声明0本文的任何作者均未透露与本文可能存在的潜在或明显的冲突。0可能被认为与本工作存在潜在冲突的相关冲突。有关完整的披露声明，请参阅https://doi.org/ 10.1016/j.array.2022.100165。0致谢0作者要感谢J. Küng通过启发式讨论0这项工作得到了欧洲研究理事会在欧盟的Horizon2020研究和创新计划（资助协议编号101001318）的资助，是慕尼黑量子谷的一部分，得到了巴伐利亚州政府从HightechAgenda Bayern Plus的资金支持，并得到了BMK、BMDW和上奥地利州在FFG管理的COMET计划框架内的支持。0本工作得到了欧洲研究理事会的资助0[1] Disch S, Scholl C. 使用增量式组合等效检查0参考文献0[2] Marques-Silva Ja, Glass T. 使用满足条件的组合等效检查0SAT求解、输出排序和复位。在：亚洲和南太平洋设计自动化会议。2007年，第938–43页。0[3] Molitor P, Mohnke J. 数字电路的等效检查：基础0能力和递归学习。在：欧洲设计、自动化和测试。1999年。0[4] Jha S, Lu Y, Minea M, Clarke EM. 使用抽象BDD进行等效检查0原理、方法。斯普林格；2010年。0[5] Clarke EM, Grumberg O, Kroening D, Peled DA, Veith H. 模型检查。MIT0在：计算机设计国际会议。1997年。0[6] Biere A, Cimatti A, Clarke EM, Zhu Y. 无BDD的符号模型检查0出版社；2018年0[7] Yuan J, Pixley C, Aziz A. 基于约束的验证。斯普林格；2006年。[8] Biere A, Kunz W. SAT和ATPG：形式硬件的布尔引擎0在：用于系统构建和分析的工具和算法。1999年，第193–207页。0[9] Wille R, Große D, Haedicke F, Drechsler R. 基于SMT的刺激生成0验证。在：CAD国际会议。2002年，第782–5页。0[10] Kitchen N, Kuehlmann A. 用于受限随机模拟的刺激生成0systemc验证库。在：规范和设计语言论坛。2009年。0[11] Gent K, Hsiao MS. RTL的快速多级测试生成。在：IEEE年度0在：CAD国际会议。2007年，第258–65页。0[12] Laeufer K, Koenig J, Kim D, Bachrach J, Sen K. RFUZZ：覆盖导向的模糊0VLSI研讨会。2016年，第553–8页。0[13] Toffoli T. 可逆计算。在：自动机、语言和编程，卷0在FPGA上对RTL进行测试。在：CAD国际会议。2018年。0[14] Zulehner A, Wille R. 使其可逆：非可逆的有效嵌入085。斯普林格；1980年，第632–44页。0[15] Maslov D, Dueck GW. 具有最小垃圾的可逆级联。IEEE0功能。在：设计、自动化和测试。2017年。0[16] Zilic Z, Radecka K, Kazamiphur A. 从可逆电路技术映射0集成电路和系统CAD交易2004;23(11):1497–509。0[17] Burgholzer L, Wille R. 用于等效检查的模拟的力量0不可逆规格。在：欧洲设计、自动化和测试。2007年。0量子计算。在：设计自动化会议。2020年。0[18] Burgholzer L, Kueng R, Wille R. 用于验证的随机刺激生成0量子电路。在：亚洲和南太平洋设计自动化会议。2021年。0[19] Linden N, Wolf Rd. 轻量级检测大量错误中的少量大错误0一个量子电路，arXiv:2009.08840，2020年。