文章基本信息
- 标题：Learning graph based quantum query algorithms for finding constant-size subgraphs
- 本地全文：下载
- 作者：Troy Lee ; Frédéric Magniez ; Miklos Santha 等
- 期刊名称：Chicago Journal of Theoretical Computer Science
- 印刷版ISSN：1073-0486
- 出版年度：2012
- 卷号：2012
- 出版社：MIT Press ; University of Chicago, Department of Computer Science
- 摘要：
Let H be a fixed k-vertex graph with m edges and minimum degree d > 0. We use the learning graph framework of Belovs to show that the bounded-error quantum query complexity of determining if an n-vertex graph contains H as a subgraph is O(n^[2 - 2/k -t] ), where t = max {A, B} > 0 with A = [ k^2 -2(m+1)] / [k(k+1)(m+1)] and B = [2k -d -3]/[k(d+1)(m-d+2)]
