A Quantum Algorithm for Computing All Diagnoses of a Switching Circuit
This addresses fault diagnosis in computing systems, offering a novel quantum-based method that is incremental in applying quantum computing to an existing domain.
The paper tackles the problem of diagnosing faults in switching circuits by introducing a quantum algorithm that computes all possible diagnoses simultaneously using superposition, achieving less than 1% error in fault probability estimation on benchmark circuits.
Faults are stochastic by nature while most man-made systems, and especially computers, work deterministically. This necessitates the linking of probability theory with mathematical logics, automata, and switching circuit theory. This paper provides such a connecting via quantum information theory which is an intuitive approach as quantum physics obeys probability laws. In this paper we provide a novel approach for computing diagnosis of switching circuits with gate-based quantum computers. The approach is based on the idea of putting the qubits representing faults in superposition and compute all, often exponentially many, diagnoses simultaneously. We empirically compare the quantum algorithm for diagnostics to an approach based on SAT and model-counting. For a benchmark of combinational circuits we establish an error of less than one percent in estimating the true probability of faults.