Quantum query complexity of graph connectivity

Details Quantum query complexity of graph connectivity Quantum query complexity of graph connectivity

2003-03-27

arxiv.org/abs/quant-ph/0303169v3

Physics

Quantum Physics

Scientific paper

Harry Buhrman et al gave an Omega(sqrt n) lower bound for monotone graph properties in the adjacency matrix query model. Their proof is based on the polynomial method. However for some properties stronger lower bounds exist. We give an Omega(n^{3/2}) bound for Graph Connectivity using Andris Ambainis' method, and an O(n^{3/2} log n) upper bound based on Grover's search algorithm. In addition we study the adjacency list query model, where we have almost matching lower and upper bounds for Strong Connectivity of directed graphs.

Affiliated with

Also associated with

No associations

Rating

Quantum query complexity of graph connectivity 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 Quantum query complexity of graph connectivity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum query complexity of graph connectivity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-639147