Quantum query complexity of subgraph isomorphism and homomorphism

Let H be a (non-empty) graph on n vertices, possibly containing isolated 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 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) = Ω(n^3/4) for any H, improving on the previously best known bound of Ω(n^2/3) [16]. Until very recently, it was believed that the quantum query complexity is at least square root of the randomized one. Our Ω(n^3/4) bound for Q(fh) matches the square root of the current best known bound for the randomized query complexity of fH, which is Ω(n^3/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 Ω(n^4/5) bound for quantum query complexity of the Subgraph Isomorphism, improving on the previously known Ω(n^3/4) bound. For the Subgraph Homomorphism, we obtain an Ω(n^3/2) bound for the same.