Quantum query complexity of minor-closed graph properties

2010/11/30 by Andrew M. Childs, Robin Kothari · 1 citation
Physics and Astronomy · Computer Science · #quant-ph #cs.CC #cs.DS

paper · pdf · doi:10.4230/lipics.stacs.2011.661

published as Proc. 28th Symposium on Theoretical Aspects of Computer Science (STACS 2011), Leibniz International Proceedings in Informatics 9, pp. 661-672 · v1: 25 pages, 2 figures. v2: 26 pages

arxiv created 2011/05/19 · arxiv updated 2011/05/20

Abstract

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 Θ(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.

Cited by

• Quantum algorithms for path and cycle containment problems