License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.48
URN: urn:nbn:de:0030-drops-57495
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5749/
Kulkarni, Raghav ;
Podder, Supartha
Quantum Query Complexity of Subgraph Isomorphism and Homomorphism
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 |
|
Collection: |
|
33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
16.02.2016 |
