2026-08-25T17:34:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27173 2026-08-25T13:18:16Z ddc:004 open_access

Quantum Time-Space Tradeoffs for Exponential Dynamic Programming Caroppo, Susanna Vihrovs, Jevgēnijs Zajakina, Dārta Zajakins, Aleksejs Quantum Algorithms Time-Space Tradeoffs NP-Hard Problems Dynamic Programming Divide & Conquer We investigate the quantum algorithms for dynamic programming by Ambainis et al. (SODA'19). While giving provable complexity speedups and applicable to a variety of NP-hard problems, these algorithms have a notable drawback: they require a large amount of Quantum Random Access Memory (QRAM), which potentially could be very challenging to implement in a physical quantum computer. In this work, we study how the space complexity can be improved by trading it for time, while still retaining a speedup over the classical algorithms. We show novel quantum time-space tradeoffs by combining different classical approaches with quantum techniques. For instance, we show that the Travelling Salesman Problem can be solved quantumly in Õ(1.859ⁿ) time and Õ(1.315ⁿ) QRAM space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Susanna Caroppo and Jevgēnijs Vihrovs and Dārta Zajakina and Aleksejs Zajakins 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.37 urn:nbn:de:0030-drops-271733 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.37 eng https://creativecommons.org/licenses/by/4.0/legalcode