Quantum query complexity of minor-closed graph properties

Details Quantum query complexity of minor-closed graph properties Quantum query complexity of minor-closed graph properties

2010-11-05

arxiv.org/abs/1011.1443v2

Proc. 28th Symposium on Theoretical Aspects of Computer Science (STACS 2011), Leibniz International Proceedings in Informatics

Physics

Quantum Physics

v1: 25 pages, 2 figures. v2: 26 pages

Scientific paper

10.4230/LIPIcs.STACS.2011.661

We study the quantum query complexity of minor-closed graph properties, which include such problems as determining whether an $n$-vertex graph is planar, is a forest, or does not contain a path of a given length. We show that most minor-closed properties---those that cannot be characterized by a finite set of forbidden subgraphs---have quantum query complexity \Theta(n^{3/2}). To establish this, we prove an adversary lower bound using a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. On the other hand, we show that minor-closed properties (and more generally, sparse graph properties) that can be characterized by finitely many forbidden subgraphs can be solved strictly faster, in o(n^{3/2}) queries. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-455065