Quantum-inspired Boolean states for bounding engineering network reliability assessment

摘要

Significant methodological progress has taken place to quantify the reliability of networked systems over the past decades. Both numerical and analytical methods have enjoyed improvements via a host of advanced Monte Carlo simulation strategies, state space partition methods, statistical learning, and Boolean functions among others. The latter approach exploits logic to approximate network reliability assessments efficiently while offering theoretical error guarantees. In parallel, physicists have made progress modeling complex systems via tensor networks (TNs), particularly quantum many-body systems. Inspired by the representation power of quantum TNs, this paper offers a new approach to efficiently bound all-terminal network reliability (ATR). It does so by exactly solving a related network Boolean satisfiability counting problem (or #SAT(NET)), represented as a TN, by counting configurations in which all network nodes are connected to at least a neighbor. Our #SAT(NET )counting outperforms state-of-the-art approximate and exact counters for the same problem as shown for challenging two-dimensional lattice networks of increasing size. While the over-counting from #SAT NET increases exponentially relative to the number of configurations that satisfy ATR problems (or #RELAT), the bias is predictable for ideal networks, such as lattices, and our upper bound is guaranteed with 100% confidence. This bound also cuts through the upper bound from other analytical methods for the ATR problem, such as recursive decomposition algorithms (RDA)-a desirable feature when exact or approximate methods with error guarantees fail to scale. Clearly, our goal is not to solve the general stochastic network reliability problem, which remains a #P problem in the computational complexity hierarchy (i.e., a counting version of non-deterministic polynomial time [NP] problems for which there is no known polynomial time algorithms to find their solutions). Instead, we present a novel bounding technique for network reliability, which relies on exactly counting configurations for our network satisfiability problem by using quantum computing principles. We offer a proof for the counting bound to hold in a connectivity ATR sense, and illustrate trends with cubic and lattice networks. Overall, the proposed method provides an alternative to available system reliability assessment approaches, and opens directions for future research, especially as discoveries in logic, algebraic projections, and quantum computation continue to accrue.