Leipold Hannes, Spedalieri Federico M
Information Sciences Institute, University of Southern California, Marina del Rey, CA, 90292, USA.
Department of Computer Science, University of Southern California, Los Angeles, CA, 90089, USA.
Sci Rep. 2022 Jul 8;12(1):11691. doi: 10.1038/s41598-022-14804-8.
We present a very general construction for quantum annealing protocols to solve Combinational Circuit Fault Diagnosis problems that restricts the evolution to the space of valid diagnoses. This is accomplished by using special local drivers that induce a transition graph on the space of feasible configurations that is regular and instance independent for each given circuit topology. Analysis of small instances shows that the energy gap has a generic form, and that the minimum gap occurs in the last third of the evolution. We used these features to construct an improved annealing schedule and benchmarked its performance through closed system simulations. We found that degeneracy can help the performance of quantum annealing, especially for instances with a higher number of faults in their minimum fault diagnosis. This contrasts with the performance of classical approaches based on brute force search that are used in industry for large scale circuits.
我们提出了一种用于解决组合电路故障诊断问题的量子退火协议的非常通用的构造方法，该方法将演化限制在有效诊断的空间内。这是通过使用特殊的局部驱动来实现的，这些驱动在可行配置空间上诱导出一个转换图，对于每个给定的电路拓扑结构，该转换图是规则的且与实例无关。对小实例的分析表明，能隙具有一般形式，并且最小能隙出现在演化的最后三分之一阶段。我们利用这些特征构建了一种改进的退火调度，并通过封闭系统模拟对其性能进行了基准测试。我们发现简并性有助于量子退火的性能，特别是对于在最小故障诊断中具有较多故障数量的实例。这与工业中用于大规模电路的基于蛮力搜索的经典方法的性能形成对比。
