A Hybrid Classical/Quantum Algorithm to Estimate Network Violation Probabilities

Abstract

The emergence of Quantum Computing has resulted in a slate of quantum algorithms that can solve a wide variety of algorithmic and computational problems faster than any classical computer. How we can apply these various quantum algorithms to practical problems in computing is still an ongoing area of research. In this work, we present a ''hybrid classical/quantum'' algorithm that uses quantum counting to solve a network verification problem involving the estimation of probabilities. We present a detailed cost analysis of our algorithm, showing that under certain assumptions it outperforms standard verification methods.