Physics – Quantum Physics
Scientific paper
2012-03-12
Physics
Quantum Physics
18 pages, 4 figures
Scientific paper
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 as a minor, we give O(n)-query quantum algorithms for detecting T either a triangle or a subdivision of a star. All these algorithms can be implemented time efficiently and, except for the triangle-detection algorithm, in logarithmic space. One of the main techniques is to modify the st-connectivity span program to drop along the way "breadcrumbs," which must be retrieved before the path from s is allowed to enter t.
Belovs Aleksandrs
Reichardt Ben W.
No associations
LandOfFree
Span programs and quantum algorithms for st-connectivity and claw detection does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Span programs and quantum algorithms for st-connectivity and claw detection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Span programs and quantum algorithms for st-connectivity and claw detection will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-489271