[QIP-Sem] QIP seminar, Mon 3/14, 4:00, 36-428, Andrew Childs

[Peter Shor]

MIT Quantum Information Processing seminar
Monday 3/14 at 4:00 in 36-428
-------------------------------------------------

Andrew Childs (University of Waterloo)

Quantum query complexity of minor-closed graph properties

Abstract:

We study the quantum query complexity of minor-closed graph properties, which include such problems as determining whether a 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.  This is joint work with Robin Kothari. 

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem