QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT
Yechao Zhu · International Journal of Quantum Information · 2012
We study the quantum query complexity of constant-sized subgraph containment. Such problems include determining whether a n-vertex graph contains a triangle, clique or star of some size. For a general subgraph H with k vertices, we show that H containment can be solved with quantum query complexity [Formula: see text], with g(H) a strictly positive function of H. This is better than Õ(n 2-2/k ) by Magniez et al. This result is obtained in the learning graph model of Belovs.