2011/09/30 by Yechao Zhu · 1 citation
Physics and Astronomy · #quant-ph
paper · pdf · doi:10.1142/s0219749912500190
published as IJQI 10(3):(2012)1250019 · 14 pages, 1 figure, published under title:"Quantum Query Complexity of Constant-sized Subgraph Containment"
arxiv created 2012/07/06 · arxiv updated 2012/07/09
We study the quantum query complexity of constant-sized subgraph containment. Such problems include determining whether an 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 O(n2-(2)/(k)-g(H)) , with g(H) a strictly positive function of H . This is better than O\sn2-2/k by Magniez et al. These results are obtained in the learning graph model of Belovs.