An important family of span programs, st-connectivity span programs, have been used to design quantum algorithms in various contexts, including a number of graph problems and formula evaluation problems. The complexity of the resulting algorithms depends on the largest positive witness size of any 1-input, and the largest negative witness size of any 0-input. Belovs and Reichardt first showed that the positive witness size is exactly characterized by the effective resistance of the input graph, but only rough upper bounds were known previously on the negative witness size. We show that the negative witness size in an st-connectivity span program is exactly characterized by the capacitance of the input graph. This gives a tight analysis for algorithms based on st-connectivity span programs on any set of inputs. We use this analysis to give a new quantum algorithm for estimating the capacitance of a graph. We also describe a new quantum algorithm for deciding if a graph is connected, which improves the previous best quantum algorithm for this problem if we're promised that either the graph has at least kappa>1 components, or the graph is connected and has small average resistance, which is upper bounded by the diameter. We also give an alternative algorithm for deciding if a graph is connected that can be better than our first algorithm when the maximum degree is small. Finally, using ideas from our second connectivity algorithm, we give an algorithm for estimating the algebraic connectivity of a graph, the second largest eigenvalue of the Laplacian.
An important family of span programs, st-connectivity span programs, have been used to design quantum algorithms in various contexts, including a number of graph problems and formula evaluation problems. The complexity of the resulting algorithms depends on the largest positive witness size of any 1-input, and the largest negative witness size of any 0-input. Belovs and Reichardt first showed that the positive witness size is exactly characterized by the effective resistance of the input graph, but only rough upper bounds were known previously on the negative witness size. We show that the negative witness size in an st-connectivity span program is exactly characterized by the capacitance of the input graph. This gives a tight analysis for algorithms based on st-connectivity span programs on any set of inputs. We use this analysis to give a new quantum algorithm for estimating the capacitance of a graph. We also describe a new quantum algorithm for deciding if a graph is connected, which improves the previous best quantum algorithm for this problem if we're promised that either the graph has at least kappa>1 components, or the graph is connected and has small average resistance, which is upper bounded by the diameter. We also give an alternative algorithm for deciding if a graph is connected that can be better than our first algorithm when the maximum degree is small. Finally, using ideas from our second connectivity algorithm, we give an algorithm for estimating the algebraic connectivity of a graph, the second largest eigenvalue of the Laplacian.
Span programs are a model of computation that have been used to design quantum algorithms, mainly in the query model. It is known that for any decision problem, there exists a span program that leads to an algorithm with optimal quantum query complexity, however finding such an algorithm is generally challenging. We consider new ways of designing quantum algorithms using span programs. We show how any span program that decides a function f can also be used to decide “threshold” versions of the function f, or more generally, approximate a quantity called the span program witness size, which is some property of the input related to f. We achieve these results by relaxing the requirement that 1-inputs hit some target exactly in the span program, which could potentially make design of span programs significantly easier. In addition, we give an exposition of span program structure, which increases the general understanding of this important model. One implication of this is alternative algorithms for estimating the witness size when the phase gap of a certain unitary can be lower bounded. We show how to lower bound this phase gap in certain cases. As an application, we give the first upper bounds in the adjacency query model on the quantum time complexity of estimating the effective resistance between s and t, Rs,t(G) . For this problem we obtain O(ε3/21nRs,t(G)) , using O(logn) space. In addition, when μ is a lower bound on λ2(G) , by our phase gap lower bound, we can obtain an upper bound of O(ε1nRs,t(G)/μ) for estimating effective resistance, also using O(logn) space.
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.
We introduce a new quantum algorithm for computing the Betti numbers of a simplicial complex. In contrast to previous quantum algorithms that work by estimating the eigenvalues of the combinatorial Laplacian, our algorithm is an instance of the generic Incremental Algorithm for computing Betti numbers that incrementally adds simplices to the simplicial complex and tests whether or not they create a cycle. In contrast to existing quantum algorithms for computing Betti numbers that work best when the complex has close to the maximal number of simplices, our algorithm works best for sparse complexes. To test whether a simplex creates a cycle, we introduce a quantum span-program algorithm. We show that the query complexity of our span program is parameterized by quantities called the effective resistance and effective capacitance of the boundary of the simplex. Unfortunately, we also prove upper and lower bounds on the effective resistance and capacitance, showing both quantities can be exponentially large with respect to the size of the complex, implying that our algorithm would have to run for exponential time to exactly compute Betti numbers. However, as a corollary to these bounds, we show that the spectral gap of the combinatorial Laplacian can be exponentially small. As the runtime of all previous quantum algorithms for computing Betti numbers are parameterized by the inverse of the spectral gap, our bounds show that all quantum algorithms for computing Betti numbers must run for exponentially long to exactly compute Betti numbers. Finally, we prove some novel formulas for effective resistance and effective capacitance to give intuition for these quantities.
Span programs form a linear-algebraic model of computation, with span program “size” used in proving classical lower bounds. Quantum query complexity is a coherent generalization, for quantum algorithms, of classical decision-tree complexity. It is bounded below by a semi-definite program (SDP) known as the general adversary bound. We connect these classical and quantum models by proving that for any boolean function, the optimal “witness size” of a span program for that function coincides exactly with the general adversary bound. A consequence is an optimal quantum algorithm for evaluating “balanced,” read-once formulas over any finite boolean gate set. For example, the gate set may be taken to be all functions {0, 1} → {0, 1} with k ≤ 1000. A formula is a tree whose nodes are associated to functions from the gate set. The notion of balance is technical, but it includes layered formulas. A previous quantum algorithm optimally evaluates formulas for which an optimal span program is given for each constant-size gate. However, span programs have been found only by hand. The SDP automates this procedure, and its value surprisingly always matches the lower bound. Other implications of the SDP include an exact composition rule for the general adversary bound, and that the general adversary bound upper-bounds the sign degree. The connection can also be seen as half of a universality result for span programs. For any boolean function, there exists a span program with witness size at most the function’s quantum query complexity. Conversely, solutions to the SDP give span programs, and therefore also new quantum algorithms—beyond evaluating formulas. Subsequent work has bounded the query complexity by the witness size, thus implying that the general adversary bound is tight.
Span programs form a linear-algebraic model of computation that is studied to prove classical lower bounds. Quantum query complexity is a coherent generalization for quantum algorithms of decision-tree complexity. It is characterized by a semidefinite program known as the general adversary bound. We connect these classical and quantum models by proving that for any boolean function, the optimal “witness size” of a span program equals the general adversary bound. Therefore, span program witness size and quantum query complexity are equivalent measures. In particular, quantum algorithms can be designed based on span programs.