Span Programs, Electrical Flows, and Beyond: New Approaches to Quantum Algorithms

Abstract

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 $n times n$ 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 $tilde{O}(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 $log{n}$, $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 $log{n}$, $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.