Document Open Access Logo

Quantum Speedups for Treewidth

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

PDF
Thumbnail PDF

File

LIPIcs.TQC.2022.11.pdf
  • Filesize: 0.83 MB
  • 18 pages

Document Identifiers

Author Details

Vladislavs Kļevickis
  • Centre for Quantum Computer Science, Faculty of Computing, University of Latvia, Riga, Latvia
Krišjānis Prūsis
  • Centre for Quantum Computer Science, Faculty of Computing, University of Latvia, Riga, Latvia
Jevgēnijs Vihrovs
  • Centre for Quantum Computer Science, Faculty of Computing, University of Latvia, Riga, Latvia

Funding

Supported by the project "Quantum algorithms: from complexity theory to experiment" funded under ERDF programme 1.1.1.5.

Cite As Get BibTex

Vladislavs Kļevickis, Krišjānis Prūsis, and Jevgēnijs Vihrovs. Quantum Speedups for Treewidth. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.TQC.2022.11

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Quantum computation theory
Keywords
  • Quantum computation
  • Treewidth
  • Exact algorithms
  • Dynamic programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Andris Ambainis, Kaspars Balodis, Jānis Iraids, Martins Kokainis, Krišjānis Prūsis, and Jevgēnijs Vihrovs. Quantum speedups for exponential-time dynamic programming algorithms. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pages 1783-1793, USA, 2019. Society for Industrial and Applied Mathematics. URL: https://doi.org/10.1137/1.9781611975482.107.
  2. Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic Discrete Methods, 8(2):277-284, 1987. URL: https://doi.org/10.1137/0608024.
  3. Stefan Arnborg and Andrzej Proskurowski. Linear time algorithms for np-hard problems restricted to partial k-trees. Discrete Appl. Math., 23(1):11-24, April 1989. URL: https://doi.org/10.1016/0166-218X(89)90031-0.
  4. Richard Bellman. Dynamic programming treatment of the travelling salesman problem. J. ACM, 9(1):61-63, 1962. URL: https://doi.org/10.1145/321105.321111.
  5. Hans L. Bodlaender. Discovering treewidth. In Peter Vojtáš, Mária Bieliková, Bernadette Charron-Bost, and Ondrej Sýkora, editors, SOFSEM 2005: Theory and Practice of Computer Science, pages 1-16, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-540-30577-4_1.
  6. Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos. On exact algorithms for treewidth. ACM Trans. Algorithms, 9(1), 2012. URL: https://doi.org/10.1145/2390176.2390188.
  7. Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum, 1996. URL: http://arxiv.org/abs/quant-ph/9607014.
  8. Uriel Feige, Mohammad Taghi Hajiaghayi, and James R. Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM Journal on Computing, 38(2):629-657, 2008. URL: https://doi.org/10.1137/05064299X.
  9. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer Science & Business Media, 2010. Google Scholar
  10. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Michał Pilipczuk, and Marcin Wrochna. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Trans. Algorithms, 14(3), June 2018. URL: https://doi.org/10.1145/3186898.
  11. Fedor V. Fomin and Yngve Villanger. Treewidth computation and extremal combinatorics. Combinatorica, 32:289-308, 2012. URL: https://doi.org/10.1007/s00493-012-2536-z.
  12. Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Phys. Rev. Lett., 100:160501, 2008. URL: https://doi.org/10.1103/PhysRevLett.100.160501.
  13. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC '96, pages 212-219, New York, NY, USA, 1996. Association for Computing Machinery. URL: https://doi.org/10.1145/237814.237866.
  14. Michael Held and Richard M. Karp. A dynamic programming approach to sequencing problems. Journal of SIAM, 10(1):196-210, 1962. URL: https://doi.org/10.1145/800029.808532.
  15. Peter Høyer, Michele Mosca, and Ronald de Wolf. Quantum search on bounded-error inputs. In Automata, Languages and Programming, ICALP'03, pages 291-299, Berlin, Heidelberg, 2003. Springer-Verlag. URL: https://doi.org/10.1007/3-540-45061-0_25.
  16. Mikko Koivisto and Pekka Parviainen. A Space–Time Tradeoff for Permutation Problems, pages 484-492. SODA '10. Society for Industrial and Applied Mathematics, USA, 2010. URL: https://doi.org/10.1137/1.9781611973075.41.
  17. Tuukka Korhonen. A single-exponential time 2-approximation algorithm for treewidth, 2021. URL: http://arxiv.org/abs/2104.07463.
  18. Masayuki Miyamoto, Masakazu Iwamura, Koichi Kise, and François Le Gall. Quantum speedup for the minimum steiner tree problem. In Donghyun Kim, R. N. Uma, Zhipeng Cai, and Dong Hoon Lee, editors, Computing and Combinatorics, pages 234-245, Cham, 2020. Springer International Publishing. URL: https://doi.org/10.1007/978-3-030-58150-3_19.
  19. Kazuya Shimizu and Ryuhei Mori. Exponential-time quantum algorithms for graph coloring problems. In Yoshiharu Kohayakawa and Flávio Keidi Miyazawa, editors, LATIN 2020: Theoretical Informatics, pages 387-398, Cham, 2020. Springer International Publishing. URL: https://doi.org/10.1007/978-3-030-61792-9_31.
  20. Seiichiro Tani. Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams. In Susanne Albers, editor, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020), volume 162 of Leibniz International Proceedings in Informatics (LIPIcs), pages 36:1-36:19, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SWAT.2020.36.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact