License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.48
URN: urn:nbn:de:0030-drops-57495
URL: https://drops.dagstuhl.de/opus/volltexte/2016/5749/
Go to the corresponding LIPIcs Volume Portal


Kulkarni, Raghav ; Podder, Supartha

Quantum Query Complexity of Subgraph Isomorphism and Homomorphism

pdf-format:
49.pdf (0.7 MB)


Abstract

Let H be a (non-empty) graph on n vertices, possibly containing isolated vertices. Let f_H(G) = 1 iff the input graph G on n vertices contains H as a (not necessarily induced) subgraph. Let alpha_H denote the cardinality of a maximum independent set of H. In this paper we show: Q(f_H) = Omega( sqrt{alpha_H * n}), where Q(f_H) denotes the quantum query complexity of f_H. As a consequence we obtain lower bounds for Q(f_H) 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(f_H) = Omega(n^{3/4}) for any H, improving on the previously best known bound of Omega(n^{2/3}) [M. Santha/A. Chi-Chih Yao, unpublished manuscript]. Until very recently, it was believed that the quantum query complexity is at least square root of the randomized one. Our Omega(n^{3/4}) bound for Q(f_H) matches the square root of the current best known bound for the randomized query complexity of f_H, which is Omega(n^{3/2}) due to Groger. Interestingly, the randomized bound of Omega(alpha_H * n) for f_H still remains open. We also study the Subgraph Homomorphism Problem, denoted by f_{[H]}, and show that Q(f_{[H]}) = Omega(n). Finally we extend our results to the 3-uniform hypergraphs. In particular, we show an Omega(n^{4/5}) bound for quantum query complexity of the Subgraph Isomorphism, improving on the previously known Omega(n^{3/4}) bound. For the Subgraph Homomorphism, we obtain an Omega(n^{3/2}) bound for the same.

BibTeX - Entry

@InProceedings{kulkarni_et_al:LIPIcs:2016:5749,
  author =	{Raghav Kulkarni and Supartha Podder},
  title =	{{Quantum Query Complexity of Subgraph Isomorphism and Homomorphism}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{48:1--48:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Nicolas Ollinger and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5749},
  URN =		{urn:nbn:de:0030-drops-57495},
  doi =		{10.4230/LIPIcs.STACS.2016.48},
  annote =	{Keywords: quantum query complexity, subgraph isomorphism, monotone graph properties}
}

Keywords: quantum query complexity, subgraph isomorphism, monotone graph properties
Seminar: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Issue Date: 2016
Date of publication: 16.02.2016


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI