0000000000354167
AUTHOR
Ben W. Reichardt
Span programs and quantum algorithms for st-connectivity and claw detection
We introduce a span program that decides st-connectivity, and generalize the span program to develop quantum algorithms for several graph problems. First, we give an algorithm for st-connectivity that uses O(n d^{1/2}) quantum queries to the n x n adjacency matrix to decide if vertices s and t are connected, under the promise that they either are connected by a path of length at most d, or are disconnected. We also show that if T is a path, a star with two subdivided legs, or a subdivision of a claw, its presence as a subgraph in the input graph G can be detected with O(n) quantum queries to the adjacency matrix. Under the promise that G either contains T as a subgraph or does not contain T…
Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
Consider the problem of evaluating an AND-OR formula on an $N$-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time $N^{1/2+o(1)}$. In particular, approximately balanced formulas can be evaluated in $O(\sqrt{N})$ queries, which is optimal. The idea of the algorithm is to apply phase estimation to a discrete-time quantum walk on a weighted tree whose spectrum encodes the value of the formula.
Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection
We introduce a span program that decides st-connectivity, and generalize the span program to develop quantum algorithms for several graph problems. First, we give an algorithm for st-connectivity that uses O(n d^{1/2}) quantum queries to the n x n adjacency matrix to decide if vertices s and t are connected, under the promise that they either are connected by a path of length at most d, or are disconnected. We also show that if T is a path, a star with two subdivided legs, or a subdivision of a claw, its presence as a subgraph in the input graph G can be detected with O(n) quantum queries to the adjacency matrix. Under the promise that G either contains T as a subgraph or does not contain T…
Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions
For any AND-OR formula of size N, there exists a bounded-error N1/2+o(1)-time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximately balanced," formulas can be evaluated in O(radicN) queries, which is optimal. It follows that the (2-o(1))th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.