DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.37

Quantum Time-Space Tradeoffs for Exponential Dynamic Programming

Authors: Susanna Caroppo, Jevgēnijs Vihrovs, Dārta Zajakina, and Aleksejs Zajakins

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

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.

Cite as

Susanna Caroppo, Jevgēnijs Vihrovs, Dārta Zajakina, and Aleksejs Zajakins. Quantum Time-Space Tradeoffs for Exponential Dynamic Programming. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{caroppo_et_al:LIPIcs.ESA.2026.37,
  author =	{Caroppo, Susanna and Vihrovs, Jevg\={e}nijs and Zajakina, D\={a}rta and Zajakins, Aleksejs},
  title =	{{Quantum Time-Space Tradeoffs for Exponential Dynamic Programming}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.37},
  URN =		{urn:nbn:de:0030-drops-271733},
  doi =		{10.4230/LIPIcs.ESA.2026.37},
  annote =	{Keywords: Quantum Algorithms, Time-Space Tradeoffs, NP-Hard Problems, Dynamic Programming, Divide \& Conquer}
}

Search Results

Documents authored by Zajakins, Aleksejs

Quantum Time-Space Tradeoffs for Exponential Dynamic Programming

Abstract

Cite as

Thanks for your feedback!

Could not send message