文章基本信息

标题：Quantum query complexity of minor-closed graph properties
本地全文：下载
作者：Andrew M. Childs ; Robin Kothari
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2011
卷号：9
页码：661-672
DOI：10.4230/LIPIcs.STACS.2011.661
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：quatum query complexity; quantum algorithms; lower bounds; graph minors; graph properties