Quantum query complexity of minor-closed graph properties

Andrew M. Childs, Robin Kothari

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 c…