Analyzing large sparse electrical networks is a fundamental task in physics, electrical engineering and computer science. We propose two classes of quantum algorithms for this task. The first class is based on solving linear systems, and the second class is based on using quantum walks. These algorithms compute various electrical quantities, including voltages, currents, dissipated powers and effective resistances, in time poly(d, c,log(N), 1/λ, 1/e), where N is the number of vertices in the network, d is the maximum unweighted degree of the vertices, c is the ratio of largest to smallest edge resistance, λ is the spectral gap of the normalized Laplacian of the network, and e is the accuracy. Furthermore, we show that the polynomial dependence on 1/λ is necessary. This implies that our algorithms are optimal up to polynomial factors and cannot be significantly improved.
Analyzing large sparse electrical networks is a fundamental task in physics, electrical engineering and computer science. We propose two classes of quantum algorithms for this task. The first class is based on solving linear systems, and the second class is based on using quantum walks. These algorithms compute various electrical quantities, including voltages, currents, dissipated powers and effective resistances, in time poly(d, c,log(N), 1/λ, 1/e), where N is the number of vertices in the network, d is the maximum unweighted degree of the vertices, c is the ratio of largest to smallest edge resistance, λ is the spectral gap of the normalized Laplacian of the network, and e is the accuracy. Furthermore, we show that the polynomial dependence on 1/λ is necessary. This implies that our algorithms are optimal up to polynomial factors and cannot be significantly improved.
Over the last decade, a large number of quantum algorithms have been discovered that outperform their classical counterparts. However, depending on the main techniques used, most of them fall into only three categories. The first category uses quantum Fourier transform to achieve super-polynomial speedup in group-theoretical problems. The second category uses amplitude amplification to achieve polynomial speedup in search problems. The third category simulates quantum many-body systems. Finding a new class of quantum algorithms has proven a challenging task. This dissertation explores several new approaches to developing quantum algorithms. These approaches include span programs, electrical flows and nonsparse Hamiltonian simulation. We demonstrate their power by successfully applying them to some useful problems, including tree detection, effective resistance estimation and curve fitting. All of these algorithms are time-efficient, and some of them are proven to be (nearly) optimal.Span program is a linear-algebraic computation model originally proposed to prove circuit lower bounds. Recently, it is found to be closely related to quantum query complexity. We develop a span-program-based quantum algorithm for the following variant of the tree containment problem. Let T be a fixed tree. Given the ntimesn adjacency matrix of a graph G, we need to decide whether G contains T as a subgraph, or G does not contain T as a minor, under the promise that one of these cases holds. We call this problem is the subgraph/not-a-minor problem for T. We show that this problem can be solved by a quantum algorithm with O(n) query complexity and tildeO(n) time complexity. This query complexity is optimal, and this time complexity is tight up to poly-logarithmic factors. Electrical network theory has many applications to the design and analysis of classical algorithms. Its connection to quantum computation, however, remains mostly unclear. We give two quantum algorithms for approximating the effective resistance between two given vertices in an electrical network. Both of them have time complexity polynomial in logn, d, c, 1/phi and 1/epsilon, 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, phi is the conductance of the network, and epsilon is the relative error. Our algorithms have exponentially better dependence on n than classical algorithms. Furthermore, we prove that the polynomial dependence on the inverse conductance is necessary. As a consequence, our algorithms cannot be greatly improved. Finally, as a by-product, our second algorithm also produces a quantum state encoding the electrical flow between two given vertices in a network, which might be of independent interest. Our algorithms are developed by using quantum tools to analyze the algebraic properties of graph-related matrices. While the first one relies on inverting the Laplacian matrix, the second one relies on projecting onto the kernel of the weighted incidence matrix. It is hopeful that more quantum algorithms could be designed in similar way. Curve fitting is the process of constructing a (simple continuous) curve that has the best fit to a series of data points. It is a common practice in many fields of science and engineering, because it can help us to understand the relationships among two or more variables, and to infer the values of a function where no data are available. We propose efficient quantum algorithms for estimating the best-fit parameters and the quality of least-square curve fitting. The running times of our algorithms are polynomial in logn, d, kappa, nu, chi, 1/Phi and 1/epsilon, where n is the number of data points to be fitted, d is the dimension of the feature vectors, kappa is the condition number of the design matrix, nu and chi are some parameters reflecting the variances of the design matrix and response vector, Phi is the fit quality, and epsilon is the tolerable error. Our algorithms have exponentially better dependence on n than classical algorithms. They are designed by combining the techniques of phase estimation and density matrix exponentiation for nonsparse Hamiltonian simulation.
Given an undirected, weighted graph, with n vertices and m edges, and two special vertices s and t, the problem is to find the shortest path between them. We give two bounded-error quantum algorithms with improved runtime in the adjacency list model that solve the problem on special classes of graphs defined via pathfinding probabilities of classical random walks and the electrical network framework. Firstly, we give a simple quantum algorithm based on sampling edges from a graph via the quantum flow state and running a classical algorithm on the sampled edges. It runs in O~(l2m) expected time and uses O(logn) space on graphs where the shortest s-t path is also a minimum resistance s-t subgraph. Our main algorithm can be thought of as a divide and conquer version of this approach and works on a special class of graphs where classical loop-erased random walk has a probability q>0.537 of finding the shortest s-t path. In such cases the quantum algorithm outputs the shortest s-t path with high probability in O(ℓm) expected time and O(logn) space, where l is the length (or total weight, in case of weighted graphs) of the shortest s-t path. This algorithm can be parallelised to O~(lm) circuit depth when using O(llogn) space. With the latter we partially resolve with an affirmative answer the open problem of whether a path between two vertices can be found in the number of steps required to detect it.
Quantum walks provide a versatile framework for quantum algorithms across a wide range of applications. We develop efficient classical simulation methods for Szegedy quantum walks that avoid explicit construction of the full unitary evolution operator. Unlike previous approaches restricted to a particular walk formulation, our framework is built from fundamental update and reflection operators, enabling the simulation of a broader class of Szegedy walk formulations. We further extend these methods to phase-estimation-based algorithms coupled to the walk, including implementations suitable for large sparse graphs. The resulting methods achieve optimal O(N2) complexity for dense graphs with N nodes. For sparse graphs, the computational cost scales linearly with the number of edges, which is O(N) in many cases. We implement the framework in the Python package SQWLib and illustrate its capabilities through simulations of representative algorithms, including quantum simulated annealing and quantum search on graphs. These results provide a practical tool for studying Szegedy-walk-based algorithms numerically beyond purely analytical treatments.
Quantum walks provide a natural framework to approach graph problems with quantum computers, exhibiting speedups over their classical counterparts for tasks such as the search for marked nodes or the prediction of missing links. Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. It is known that such can be simulated efficiently if the underlying graph is row-sparse and efficiently row-computable. While this is sufficient for many applications, it limits the applicability for this class of algorithms to study real world complex networks, which, among other properties, are characterized by the existence of a few densely connected nodes, called hubs. In other words, complex networks are typically not row-sparse, even though the average connectivity over all nodes can be very small. In this work, we extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse. Hopefully, our results may lead to new applications of quantum computing to network science.
We present an efficient general method for realizing a quantum walk operator corresponding to an arbitrary sparse classical random walk. Our approach is based on Grover and Rudolph's method for preparing coherent versions of efficiently integrable probability distributions \cite{GroverRudolph}. This method is intended for use in quantum walk algorithms with polynomial speedups, whose complexity is usually measured in terms of how many times we have to apply a step of a quantum walk \cite{Szegedy}, compared to the number of necessary classical Markov chain steps. We consider a finer notion of complexity including the number of elementary gates it takes to implement each step of the quantum walk with some desired accuracy. The difference in complexity for various implementation approaches is that our method scales linearly in the sparsity parameter and poly-logarithmically with the inverse of the desired precision. The best previously known general methods either scale quadratically in the sparsity parameter, or polynomially in the inverse precision. Our approach is especially relevant for implementing quantum walks corresponding to classical random walks like those used in the classical algorithms for approximating permanents \cite{Vigoda, Vazirani} and sampling from binary contingency tables \cite{Stefankovi}. In those algorithms, the sparsity parameter grows with the problem size, while maintaining high precision is required.