Evaluating Quantum Algorithms: Closing the Gap between Theory and Practice

Motivated by its unique capabilities, quantum computation has gained significant attention over the last decade with numerous models and algorithms proposed for dealing with engineering challenges. The field of risk and reliability has also seen a growing interest in this area, with studies exploring Quantum Machine Learning for remaining useful life, Quantum Optimization for condition monitoring in civil structures, and Quantum Inference for enhancing Bayesian network models, to name a few. However, a common limitation across these works is the lack of thorough comparisons between the proposed quantum algorithms and their state-of-the-art classical counterparts. This critical gap must be addressed not only to evaluate the field's current state reliably but also to guide its development toward the most promising paths for achieving a quantum advantage. There are two key challenges to addressing this gap. First, quantum computation operates on fundamentally different principles than traditional computing, making direct comparisons - such as using the number of iterations - often infeasible. Second, large-scale, error-corrected quantum computers are not yet available, so machine-to-machine comparisons are also not yet possible. In this paper, we detail a novel methodology to evaluate quantum algorithms against their classical counterparts. Our technique is based on a simple observation: quantum computers do not extend the operations that a classical computer can perform. Instead, they have the potential to make them more efficient. As such, when large problems are considered, they ought to present a shorter runtime than classical algorithms to surpass, in any sense of the word, a classical algorithm. We validate the proposed methodology by applying it to an exciting application of quantum computation within the field of system reliability: the identification of minimal cut sets via the leverage of the Grover algorithm and Quantum Amplitude Amplification.

Keywords: Quantum computation, Performance evaluation, Grover algorithm, Quantum amplitude amplification, Minimal cut set identification.