Quantum query complexity of minor-closed graph properties

Authors Andrew M. Childs, Robin Kothari



PDF
Thumbnail PDF

File

LIPIcs.STACS.2011.661.pdf
  • Filesize: 0.82 MB
  • 12 pages

Document Identifiers

Author Details

Andrew M. Childs
Robin Kothari

Cite AsGet BibTex

Andrew M. Childs and Robin Kothari. Quantum query complexity of minor-closed graph properties. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 661-672, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/LIPIcs.STACS.2011.661

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 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.
Keywords
  • quatum query complexity
  • quantum algorithms
  • lower bounds
  • graph minors
  • graph properties

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail