Abstract | ||
---|---|---|
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{\frac{k^2- 2(m+1)}{k(k+1)(m+1)}, \frac{2k - d - 3}{k(d+1)(m-d+2)}}$. The previous best algorithm of Magniez et al. had complexity $\widetilde O(n^{2-2/k})$. |
Year | Venue | Keywords |
---|---|---|
2011 | Chicago Journal of Theoretical Computer Science | data structure,quantum physics |
Field | DocType | Volume |
Discrete mathematics,Graph,Quantum,Combinatorics,Algorithm,Mathematics | Journal | abs/1109.5135 |
Citations | PageRank | References |
10 | 0.60 | 8 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Troy Lee | 1 | 29 | 4.32 |
Frédéric Magniez | 2 | 570 | 44.33 |
Miklos Santha | 3 | 728 | 92.42 |