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.
Quantum interior point methods (QIPMs) promise polynomial speed-ups over classical solvers for linear programming by outsourcing the solution of Newton linear systems to quantum linear solvers (QLSAs). However, asymptotic speed-ups do not necessarily translate to practical advantages on realistic problem instances. In this work, I evaluate whether practical advantage of a standard hybrid QIPM pipeline can already be excluded relative to the classical open-source solver HiGHS on a broad and diverse collection of LP instances spanning eight problem families, including public benchmark libraries, such as MIPlib, and relaxations of combinatorial optimisation problems. Following the hybrid benchmarking paradigm initiated by Cade et al., I derive rigorous lower bounds on the quantum runtime under a series of highly benevolent assumptions and compare them against classical runtimes. I equip the QIPMs with the best-performing functional QLSA, the Chebyshev-based method, as identified by Lefterovici et al., and evaluate two Newton system formulations proposed by Mohammadisiahroudi et al.: the modified normal equation system and the orthogonal subspace system. The exclusion analysis yields a consistent negative picture: across all instances and for any realistic quantum cycle duration, the quantum runtime lower bounds already exceed the classical runtimes, establishing that these hybrid QIPMs will offer no practical advantage over good classical solvers for realistic linear programming instances.
Quantum linear solvers (QLSs) can offer the potential for exponential quantum advantage in solving quantum chemical problems, but its assessment hinges on determining the condition number (
κ) scaling, which itself is computationally challenging. While a recent work applied the Harrow-Hassidim-Lloyd (HHL) algorithm to single-reference linearized coupled cluster equations (SRLCC), the validity of the HHL-SRLCC framework is restricted to weakly correlated regimes. A general treatment requires a formulation that can access strongly correlated regions. We thus begin by extending the QLS-SRLCC framework to its multi-reference form, which is based on the internally contracted multi-reference LCC method (QLS-icMRLCC). We then analyze
κ scaling using three complementary diagnostics that range from explicit computations to use of indirect structural indicators: (i) direct calculations of
κ, (ii) scaling of the ratio of maximum to minimum diagonal entries of an A matrix, and (iii) structural analyses of the A matrices based on a recently proposed conjecture, which we adapt to the QLS-LCC problem. The three approaches yield consistent predictions, indicating a polylogarithmic
κ scaling in system size. This finding, when combined with our arguments on sub-linear scaling of sparsity, supports the prospects of exponential advantage using QLSs for the LCC problem. Finally, numerical calculations on potential energy curves of model systems containing up to four atoms recover the ground state energies with errors relative to benchmark classical methods not exceeding 0.009
%.