2026-07-21T23:33:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3052 2024-03-06T10:33:48Z ddc:004 open_access

Quantum query complexity of minor-closed graph properties Childs, Andrew M. Kothari, Robin quatum query complexity quantum algorithms lower bounds graph minors graph properties 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrew M. Childs and Robin Kothari 2011 Is Part Of LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2011.661 urn:nbn:de:0030-drops-30521 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.661 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode