Span program is a linear-algebraic model of computation originally proposed for studying the complexity theory. Recently, it has become a useful tool for designing quantum algorithms. In this paper, we present a time-efficient span-program-based quantum algorithm for the following problem. Let $T$ be an arbitrary tree. Given query access to the adjacency matrix of a graph $G$ with $n$ vertices, we need to determine 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 the subgraph/not-a-minor problem for $T$. We show that this problem can be solved by a bounded-error quantum algorithm with $O(n)$ query complexity and $\tilde{O}(n)$ time complexity. The query complexity is optimal, and the time complexity is tight up to polylog factors.
Span program is a linear-algebraic model of computation originally proposed for studying the complexity theory. Recently, it has become a useful tool for designing quantum algorithms. In this paper, we present a time-efficient span-program-based quantum algorithm for the following problem. Let T be an arbitrary tree. Given query access to the adjacency matrix of a graph G with n vertices, we need to determine 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 the subgraph/not-a-minor problem for T. We show that this problem can be solved by a bounded-error quantum algorithm with O(n) query complexity and O~(n) time complexity. The query complexity is optimal, and the time complexity is tight up to polylog factors.
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.
Quantum query complexity measures the number of input bits that must be read by a quantum algorithm in order to evaluate a function. Hoyer et al. (2007) have generalized the adversary semidefinite program that lower-bounds quantum query complexity. By giving a matching quantum algorithm, we show that the general adversary lower bound is tight for every boolean function. The proof is based on span programs, a linear-algebraic computational model without inherent dynamics. Span programs correspond to solutions to the dual semi-definite program, and to bipartite graphs. The analysis shows that properties of eigenvalue-zero eigenvectors of the graphs in fact imply an “effective” spectral gap around zero We thus develop a quantum algorithm for evaluating span programs. It follows that span programs, measured by witness size, and quantum algorithms, measured by query complexity, are equivalent computational models, up to a constant factor. The result efficiently characterizes the quantum query complexity of a read-once formula over any finite gate set. It also implies that the quantum query complexity of the composition f ◦ (g, . . . , g) of two boolean functions matches the product of the query complexities of f and g, without a logarithmic factor for error reduction. The algorithm alternates a fixed reflection with input queries. Originally introduced for solving the unstructured search problem, this structure is therefore a universal feature of quantum query algorithms. We give a second algorithm for evaluating span programs that has the further potential to be time-efficient. Subsequent applications have derived nearly time-optimal quantum algorithms for evaluating many read-once formulas. Span programs may have promise for developing more quantum algorithms.
Span programs are an important model of quantum computation due to their tight correspondence with quantum query complexity. For any decision problem f, the minimum complexity of a span program for f is equal, up to a constant factor, to the quantum query complexity of f. Moreover, this correspondence is constructive. A span program for f with complexity C can be compiled into a bounded error quantum algorithm for f with query complexity O(C), and vice versa. In this work, we prove an analogous connection for quantum time complexity. In particular, we show how to convert a quantum algorithm for f with time complexity T into a span program for f such that it compiles back into a quantum algorithm for f with time complexity O(T). While the query complexity of quantum algorithms obtained from span programs is well-understood, it is not generally clear how to implement certain query-independent operations in a time-efficient manner. We show that for span programs derived from algorithms with a time-efficient implementation, we can preserve the time efficiency when implementing the span program. This means in particular that span programs not only fully capture quantum query complexity, but also quantum time complexity. One practical advantage of being able to convert quantum algorithms to span programs in a way that preserves time complexity is that span programs compose very nicely. We demonstrate this by improving Ambainis's variable-time quantum search result using our construction through a span program composition for the OR function.
It has recently been shown that starting with a classical query algorithm (decision tree) and a guessing algorithm that tries to predict the query answers, we can design a quantum algorithm with query complexity O( √ GT where T is the query complexity of the classical algorithm (depth of the decision tree) and G is the maximum number of wrong answers by the guessing algorithm [ 3 , 14 ]. In this article, we show that, given some constraints on the classical algorithms, this quantum algorithm can be implemented in time Õ (√ GT ). Our algorithm is based on non-binary span programs and their efficient implementation. We conclude that various graph-theoretic problems including bipartiteness, cycle detection, and topological sort can be solved in time O(n 3/2 log 2 n ) and with O(n 3/2 ) quantum queries. Moreover, finding a maximal matching can be solved with O(n 3/2 ) quantum queries in time O(n 3/2 log 2 n ), and maximum bipartite matching can be solved in time O(n 2 log 2 n ).
The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph H is present in an input graph G, has been the subject of considerable study. However, even for relatively simple subgraphs, such as paths and cycles, a complete understanding of their query complexities remains elusive. In this work, we consider several variants of path- and cycle-containment problems in the adjacency matrix model, where we search for paths or cycles of constant length k. We compare the settings where the graphs are directed or undirected, where the goal is to detect or find the existence of a path/cycle, and where the path/cycle we are looking for has length exactly k, or at most k. We also consider several promise versions of these problems, where we suppose that the input graph has a certain structure. We characterize the relative difficulty of these variants of the path/cycle-containment problems, by relating them to one another using randomized reductions, and grouping them into equivalence classes.
When we restrict our attention to path-containment problems, we get a dichotomy result. Some of the path-containment problems can be solved using a linear number of queries, and all the others are equivalent to one another (and additionally to several cycle-containment problems) under randomized reductions, up to constant overhead. For the latter equivalence class, we prove a novel quantum-walk-based algorithm that achieves query complexity O(n3/2−αk), where αk∈Θ(c−k) and c=3+17/2≈1.33, beating the previous best upper bound O(n3/2) on its query complexity. We also provide a conditional lower bound based on the graph-collision problem, which implies that this equivalence class does not admit linear-query quantum algorithms unless graph collision admits an O(n) query algorithm.
Quantum algorithms for graph problems are considered, both in the adjacency matrix model and in an adjacency list-like array model. We give almost tight lower and upper bounds for the bounded error quantum query complexity of Connectivity, Strong Connectivity, Minimum Spanning Tree, and Single Source Shortest Paths. For example, we show that the query complexity of Minimum Spanning Tree is in Θ(n3/2) in the matrix model and in Θ(nm) in the array model, while the complexity of Connectivity is also in Θ(n3/2) in the matrix model but in Θ(n) in the array model. The upper bounds utilize search procedures for finding minima of functions under various conditions.