Do quantum linear solvers offer advantage for networks-based system of linear equations?

Abstract

In this exploratory numerical study, we assess the suitability of Quantum Linear Solvers(QLSs)toward providing a quantum advantage for Networks-based Linear System Problems (NLSPs). NLSPs naturally arise from graphs, and are of importance as they are connected to real-world applications. The achievable advantage with a QLS for an NLSP depends on the interplay between the scaling of condition number and sparsity of matrices associated with the graph family. We analyze 50 graph families and identify that within the scope of our study, only 21 of them exhibit prospects for an exponential advantage with the Harrow-Hassidim-Lloyd (HHL) algorithm relative to an efficient classical solver. We call graph families that offer advantage with HHL as good graph families. We also compare the performance of the considered 50 graph families with 7 other QLSs. Furthermore, we report that some graph families graduate from offering no advantage with HHL to promising an exponential advantage with improved algorithms such as the Childs-Kothari-Somma algorithm. We also introduce a unified graph superfamily and show the existence of infinite good graph families in it. Since the runtime expressions for linear solvers involve condition number, which in itself is not easy to compute, ascertaining advantage prospects with quantum linear solvers itself is not an easy problem. Thus, we conjecture the conditions under which one may visually examine a graph family and guess the prospects for an advantage. Finally, we very briefly touch upon some practical issues that may arise even if the aforementioned graph theoretic requirements are satisfied, including quantum hardware challenges.