Quantum algorithms for approximating the effective resistances in electrical networks

The theory of electrical network has many applications in algorithm design and analysis. It is an important task to compute the basic quantities about electrical networks, such as electrical flows and effective resistances, as quickly as possible. Classically, to compute these quantities, one basically need to solve a Laplacian linear system, and the best known algorithms take Õ(m) time, where m is the number of edges. In this paper, we present two quantum algorithms for approximating the effective resistance between any two vertices in an electrical network. Both of them have time complexity polynomial in logn, d, c, 1/φ and 1/ε, where n is the number of vertices, d is the maximum degree of the vertices, c is the ratio of the largest to the smallest edge resistance, φ is the expansion of the network, and ε is the relative error. In particular, when d and c are small and φ is large, our algorithms run very fast. In contrast, it is unknown whether classical algorithms can solve this case very fast. Furthermore, we prove that the polynomial dependence on the inverse expansion (i.e. 1/φ) is necessary. As a consequence, our algorithms cannot be significantly improved. Finally, as a by-product, our second algorithm also produces a quantum state approximately proportional to the electrical flow between any two vertices, which might be of independent interest. Our algorithms are based on using quantum tools to analyze the algebraic properties of graph-related matrices. While one of them relies on inverting the Laplacian matrix, the other relies on projecting onto the kernel of the weighted incidence matrix. It is hopeful that more quantum algorithms can be developed in similar way.