2015/09/21 by Raghav Kulkarni, Kulkarni, Raghav, Supartha Podder +1 · 1 citation
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Quantum Computing Algorithms and Architecture #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.1509.06361
16 pages, 2 figures
arxiv created 2015/09/22 · arxiv updated 2015/09/23
Let H be a fixed graph on n vertices. Let fH(G) = 1 iff the input graph G on n vertices contains H as a (not necessarily induced) subgraph. Let αH denote the cardinality of a maximum independent set of H. In this paper we show: Q(fH) = Ω(√(αH ⋅ n)), where Q(fH) denotes the quantum query complexity of fH. As a consequence we obtain a lower bounds for Q(fH) in terms of several other parameters of H such as the average degree, minimum vertex cover, chromatic number, and the critical probability. We also use the above bound to show that Q(fH) = Ω(n3/4) for any H, improving on the previously best known bound of Ω(n2/3). Until very recently, it was believed that the quantum query complexity is at least square root of the randomized one. Our Ω(n3/4) bound for Q(fH) matches the square root of the current best known bound for the randomized query complexity of fH, which is Ω(n3/2) due to Gröger. Interestingly, the randomized bound of Ω(αH ⋅ n) for fH still remains open. We also study the Subgraph Homomorphism Problem, denoted by f[H], and show that Q(f[H]) = Ω(n). Finally we extend our results to the 3-uniform hypergraphs. In particular, we show an Ω(n4/5) bound for quantum query complexity of the Subgraph Isomorphism, improving on the previously known Ω(n3/4) bound. For the Subgraph Homomorphism, we obtain an Ω(n3/2) bound for the same.