D6.6 Divide and quantum open source software
Sebastiaan Brand, Alfons Laarman · Zenodo (CERN European Organization for Nuclear Research) · 2022
Fault trees are a type of model which captures how small failures in probabilistic systems can propagate and ultimately lead to a critical system failure. An important component of fault tree analysis is finding small subsets of events which can cause a critical failure (often called “cut sets”). Finding these small cut sets is important because they often correspond to the most likely way a system will fail. In this deliverable we provide an open source implementation of a procedure which computes minimal cut sets from fault trees by translating the problem to a satisfiability (SAT) problem. This SAT formula can then either be solved with a classical SAT solver, or with a quantum algorithm: specifically Grover’s algorithm for amplitude amplification. The solutions found by both methods are the same, but the quantum algorithm allows for a quadradic speedup in time complexity. Additionally, for quantum computers which have too few qubits to handle the entire problem instance, a divide and conquer approach can theoretically be used to split the problem up and obtain smaller quantum speedups (Rennela, Brand, Laarman, & Dunjko, 2021). The main component of this deliverable is the open source library itself, which can be found online here: https://github.com/NEASQC/ft-2-quantum-sat. In section 2 of this document we give an overview of problem of finding cut sets, and how the library solves this problem.