License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2022.11
URN: urn:nbn:de:0030-drops-165186
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16518/
Go to the corresponding LIPIcs Volume Portal

Kļevickis, Vladislavs ; Prūsis, Krišjānis ; Vihrovs, Jevgēnijs

Quantum Speedups for Treewidth

pdf-format:
LIPIcs-TQC-2022-11.pdf (0.8 MB)

Abstract

In this paper, we study quantum algorithms for computing the exact value of the treewidth of a graph. Our algorithms are based on the classical algorithm by Fomin and Villanger (Combinatorica 32, 2012) that uses O(2.616ⁿ) time and polynomial space. We show three quantum algorithms with the following complexity, using QRAM in both exponential space algorithms:
- O(1.618ⁿ) time and polynomial space;
- O(1.554ⁿ) time and O(1.452ⁿ) space;
- O(1.538ⁿ) time and space. In contrast, the fastest known classical algorithm for treewidth uses O(1.755ⁿ) time and space. The first two speed-ups are obtained in a fairly straightforward way. The first version uses additionally only Grover’s search and provides a quadratic speedup. The second speedup is more time-efficient and uses both Grover’s search and the quantum exponential dynamic programming by Ambainis et al. (SODA '19). The third version uses the specific properties of the classical algorithm and treewidth, with a modified version of the quantum dynamic programming on the hypercube. As a small side result, we give a new classical time-space tradeoff for computing treewidth in O^*(2ⁿ) time and O^*(√{2ⁿ}) space.

BibTeX - Entry

@InProceedings{klevickis_et_al:LIPIcs.TQC.2022.11,
  author =	{K\c{l}evickis, Vladislavs and Pr\={u}sis, Kri\v{s}j\={a}nis and Vihrovs, Jevg\={e}nijs},
  title =	{{Quantum Speedups for Treewidth}},
  booktitle =	{17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-237-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{232},
  editor =	{Le Gall, Fran\c{c}ois and Morimae, Tomoyuki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16518},
  URN =		{urn:nbn:de:0030-drops-165186},
  doi =		{10.4230/LIPIcs.TQC.2022.11},
  annote =	{Keywords: Quantum computation, Treewidth, Exact algorithms, Dynamic programming}
}

Keywords: Quantum computation, Treewidth, Exact algorithms, Dynamic programming
Collection: 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)
Issue Date: 2022
Date of publication: 04.07.2022

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